Home » LẬP TRÌNH » Bài toán người du lịch

Bài toán người du lịch

BÀI TOÁN NGƯỜI DU LỊCH

Cho n thành phố đánh số từ 1 đến n và m tuyến đường giao thông hai chiều giữa chúng, mạng

lưới giao thông này được cho bởi bảng C cấp nxn, ở đây C[i, j] = C[j, i] = Chi phí đi đoạn

đường trực tiếp từ thành phối đến thành phốj. Giảthiết rằng C[i, i] = 0 với ∀i, C[i, j] = +∞

nếu không có đường trực tiếp từ thành phối đến thành phốj.

Một người du lịch xuất phát từ thành phố1, muốn đi thăm tất cả các thành phố còn lại mỗi

thành phố đúng 1 lần và cuối cùng quay lại thành phố1. Hãy chỉ ra cho người đó hành trình

với chi phí ít nhất. Bài toán đó gọi là bài toán người du lịch hay bài toán hành trình của một

thương gia (Traveling Salesman)

 

Cách giải Bài toán người du lịch:

 

Hành trình cần tìm có dạng x[1..n + 1] trong đó x[1] = x[n + 1] = 1 ở đây giữa x[i] và x[i+1]:

hai thành phố liên tiếp trong hành trình phải có đường đi trực tiếp (C[i, j] ≠+∞) và ngoại trừ

thành phố 1, không thành phố nào được lặp lại hai lần. Có nghĩa là dãy x[1..n] lập thành 1

hoán vị của (1, 2, …, n).

Duyệt quay lui: x[2] có thể chọn một trong các thành phố mà x[1] có đường đi tới (trực tiếp),

với mỗi cách thử chọn x[2] như vậy thì x[3] có thể chọn một trong các thành phố mà x[2] có

đường đi tới (ngoài x[1]). Tổng quát: x[i] có thể chọn 1 trong các thành phố chưa đi qua mà

từx[i-1] có đường đi trực tiếp tới (1 ≤i ≤n).

Nhánh cận: Khởi tạo cấu hình BestConfig có chi phí = +∞. Với mỗi bước thửchọn x[i] xem

chi phí đường đi cho tới lúc đó có < Chi phí của cấu hình BestConfig?, nếu không nhỏ hơn thì

thử giá trị khác ngay bởi có đi tiếp cũng chỉ tốn thêm. Khi thử được một giá trịx[n] ta kiểm

tra xem x[n] có đường đi trực tiếp về1 không ? Nếu có đánh giá chi phí đi từ thành phố1 đến

thành phố x[n] cộng với chi phí từ x[n] đi trực tiếp về1, nếu nhỏ hơn chi phí của đường đi

BestConfig thì cập nhật lại BestConfig bằng cách đi mới.

Sau thủ tục tìm kiếm quay lui mà chi phí của BestConfig vẫn bằng +∞thì có nghĩa là nó

không tìm thấy một hành trình nào thoả mãn điều kiện đề bài đểcập nhật BestConfig, bài toán

không có lời giải, còn nếu chi phí của BestConfig < +∞thì in ra cấu hình BestConfig – đó là

hành trình ít tốn kém nhất tìm được

(Tham khảo: Giải thuật và lập trình – Lê Minh Hoàng)

 

Code Bài toán người du lịch:

 

Input ví dụ:

4 6
1 2 3
1 3 2
1 4 1
2 3 1
2 4 2
3 4 4

Output:

1->3->2->4->1
Cost: 6

(Nếu không hiện code thì click đúp chuột vào bên dưới nhé !!!)

 

Share
  • havuong

    k chay dc ban oi

    • Tung Nguyen

      Mình đã test và chạy vẫn bình thường bạn nhé

  • DCong Nguyen

    Bạn có thể chỉnh sửa thành đọc file từ máy không bạn.Nếu chạy được file Eil51.TSP thì hay khỏi nói 😀

  • trumtintac

    bạn có thể code trên java được ko
    trên java mình ko bk đánh dấu sao cho đúng

Share
Free WordPress Themes - Download High-quality Templates