Từ 1 tới 2 trên tổng số 2 kết quả

Đề tài: giúp chứng minh tính đúng đắn của lời giải bài toán con bò poj 3169 sử dụng bài toán đường đi ngắn nhất trên đồ thị

  1. #1
    Ngày gia nhập
    03 2016
    Bài viết
    4

    Mặc định giúp chứng minh tính đúng đắn của lời giải bài toán con bò poj 3169 sử dụng bài toán đường đi ngắn nhất trên đồ thị

    em đang tìm lời giải cho bài toán sau:
    link tiếng anh:
    http://poj.org/problem?id=3169
    link lời giải:
    http://d.hatena.ne.jp/shioshiota/20110514/1305345219
    dịch tiếng việt:
    cho N con bò,chúng được đánh số từ 1 đến N, khi đứng xếp hàng chờ được ăn thì chúng phải đứng thành 1 hàng sao cho con i phải đứng ngang hoặc phía sau con j nếu (i<j).Cũng giống như người thì 1 con bò cũng thích 1 số con bò khác và ghét một số con bò khác.Nếu con a ghét con b thì khi xếp hàng chúng phải đứng cách xa nhau 1 khoảng cho trước, ví dụ 1 ghét 3 và phải đứng xa 5 ô, 2,4 ghét nhau và phải đứng xa 10 ô ( tùy từng cặp sẽ đứng xa khác nhau ). Tương tự thì nếu chúng thích nhau phải đứng gần nhau trong 1 khoảng nào đó.Tại 1 ô có thể xếp nhiều còn tùy thích.Có những ô có thể được bỏ trống.
    Hãy tìm khoảng cách lớn nhất mà con thứ 1 và con thứ N cách nhau xa nhất nếu khoảng cách tồn tại ( có trường hợp không tồn tại cách xếp thỏa mãn và đôi khi khoảng cách xa nhất đạt được là vô cực)

    Em cần chứng minh tính đúng gắn của thuật toán trên.ai có thể hướng dẫn em được không ?

  2. #2
    Ngày gia nhập
    03 2016
    Bài viết
    4

    Chứng minh tính đúng đắn của thuật toán

    Ta cần chứng minh tính đúng đắn của thuật toán với 3 trường hợp : không có cách xếp thỏa mãn,khoảng cách đạt max là 1 số hữu hạn, khoảng cách max là vô cực . 3 trường hợp trên sẽ tương ứng với 3 kết quả đầu ra của thuật toán tìm đường đi ngắn nhất trong đồ thị( cách xây dựng đồ thị trình bày ở sau) : có chu trình âm,có đường đi ngắn nhất từ đỉnh 1 đến đỉnh n, không có đường đi từ đỉnh 1 đến n;
    Contents
    I. Cách xây dựng đồ thị để giải thuật toán 1
    II. Giải thích cách lập cạnh của đồ thị 1
    III. Chứng minh thuật toán 1


    I. Cách xây dựng đồ thị để giải thuật toán
    Đỉnh của đồ thị được đánh dấu ứng với số của con bò. Ví dụ: đỉnh số 6 ứng với con bò số 6;
    Cạnh của đồ thị:
    1. Cạnh đi từ đỉnh i đến đỉnh j( i<j ) trọng số m nếu con bò i thích con bò j và muốn đứng gần trong khoảng cách m ô.
    2. Cạnh từ đỉnh j đến đỉnh i ( i<j ) trọng số -m nếu con bò j ghét con bò i và muốn đứng xa trong khoảng cách m ô.
    3. Cạnh từ đỉnh j đến đỉnh j-1 trọng số 0 với mọi j từ 2->N
    II. Giải thích cách lập cạnh của đồ thị
    Trong bài toán tìm đường đi ngắn nhất thông thường, nếu có cạnh đi từ đỉnh A đến đỉnh B trong đồ thị với trọng số m ( bất kỳ m âm hay dương ) thì ta luôn có khoảng cách ngắn nhất từ đỉnh S đến A (dA) và khoảng cách ngắn nhất từ S đến B luôn thỏa mãn bất đẳng thức: dA+m>=dB( dấu bằng xảy ra khi A đứng trước B trong đường đi ngắn nhất từ S đến B ).
    Trong bài toán:
    Nếu con bò i thích con bò j (i<j)thì ta có dj<=di+m nên để tương ứng với suy luận trên ta có cạnh đi từ i đến j trọng số là m
    Nếu con i ghét con bò j ( i<j )thì ta có dj >=di+m  dj – m >=di nên ta thêm cạnh từ đỉnh j đến i với trọng số là -m
    Do các con bò phải đứng theo thứ tự nên ta có dj >=di nên ta thêm cạnh từ j đên i trọng số là 0
    III. Chứng minh thuật toán
    1. Chứng minh nếu trong đồ thị có chu trình âm thì ta sẽ không có cách xếp thỏa mãn
    Giả sử ta có chu trình u1,u2,u3,…,un là chu trình âm.
    Các cạnh a1,a2,a3,a4,…,an,a* là cạnh của chu trình
    Theo bất đẳng thức trong II ta có
    Du1+a1>=du2,
    Du2+a2>=du3
    .
    .
    .
    Dun-1+an-1>=dun
    Dun+a*>=du1
    Cộng tất cả các bất đẳng thức trên lại ta có
    >=0 nhưng <0 do đây là chu trình âm => không có các bộ số du1,du2…dun nào thỏa mãn được các bất thức trên hay nói cách khác không có cách xếp nào thỏa mãn.
    2. Chứng minh quãng đường ngắn nhất là giá trị lớn nhất của con bò thứ N
    Giả sử ta có đường đi P từ đỉnh 1 đến đỉnh N:u1,u2,u3,…,un
    Tương tự phần trên ta có:
    Du1+a1>=du2,
    Du2+a2>=du3
    .
    .
    .
    Dun-1+an-1>=dun
    Cộng lại ta có du1+>=dun. Mà du1=0 so đó chính là điểm xuất phát.
    Ta có >=dun ( đặt =L )
    Vậy với mỗi đường đi Pi ta có một cận trên Li của dun tương ứng.
    Nếu tối đa n đường đi thì ta có n cận trên của dun, để thỏa mãn cả n bất đẳng thức trên thì dun<=min( Li ). Hay nói cách khác dun đạt max khi dun=min(Li) ( điều phải chứng minh )
    3. Chứng minh nếu không đường đi từ đỉnh 1 đến N thì vị trí của con bò thứ N là vô cực
    Do không có đường đi nào từ đỉnh 1 đến đỉnh N nên ta không có bộ bất đẳng thức nào như sau:
    Du1+a1>=du2,
    Du2+a2>=du3
    .
    .
    .
    Dun-1+an-1>=dun
    Hay với bất kỳ giá trị đủ lớn thì dun đều thỏa mãn => khoảng cách giữa con thứ 1 và con thứ N là vô cực
    4. Chứng minh chiều ngược lại:
    Không tồn tại cách xếp => có chu trình âm
    Giá trị max là giá trị quãng đường ngắn nhất
    Khoảng cách là vô cực=> không có đường đi
    Để chứng minh ta dùng phản chứng :
    Ví dụ: chứng minh: Không tồn tại cách xếp => có chu trình âm
    Phản chứng : Không tồn tại cách xếp => không có chu trình âm
    Nhưng nếu không có chu trình âm thì đồ thị sẽ có đường đi ngắn nhất hoặc không có đường đi từ đỉnh 1 đến đỉnh N.
    TH1 nếu có đường đi ngắn nhất : theo mục 2 ta đã có lúc này sẽ tồn tại khoảng cách max giữa con bò 1 và con bò N => mẫu thuẫn giả thiết
    TH2: nếu không có đường đi: theo mục 3 thì lúc này giữa con bò 1 và con bò N sẽ có khoảng cách max là vô cực=> mãu thuẫn giả thiết
    Vậy ta có điều chứng minh, 2 vấn đề chứng minh phản chứng sau tương tự.

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn