Cài đặt code bài toán người du lịch cài đặt bằng C++, Java

Bài toán người du lịch: Một nguời du lịch muốn đi tham quan n thành phố T1,T2…, Tn . Xuất phát từ một thành phố nào đó, người du lịch muốn đi qua tất cả các thành phố còn lại, mỗi thành phố đi qua duy nhất 1 lần rối quay trở trở lại thành phố xuất phát.

Gọi Cij là chi phí đi từ thành phố Ti đến Tj . Hãy tìm một hành trình thỏa yêu cầu bài toán sao cho chi phí là nhỏ nhất.

Hãy cùng Lập trình không khó đi giải quyết bài toán này nhé các bạn

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

Chúng ta sẽ lưu ma trận chi phí đi từ Ti đến Tja[i][j]. Như vậy, tại đường chéo của ma trận thì chi phí sẽ bằng 0. Giả sử với ma trận sau:

Chúng ta giả sử có 4 thành phố: T0, T1, T2, T3. Như vậy thì hàng đầu tiên là chi phí đi từ T0 đến T0, T1, T2, T3 lần lượt là 0, 10, 15, 20. Tương tự với các hàng phía sau.

Mình xin 5 phút quảng cáo nha =))

Lưu ý: cost = 999999 ngầm hiểu ở đây là khai báo giá trị cost khởi tạo là vô cùng lớn.

Source code C/C++:

> Lời giải tham khảo tại: sanfoundry.com

Kết quả chạy:

Source code Java:

> Lời giải tham khảo tại : sanfoundry.com

Kết quả chạy thử:

 

avatar
  Subscribe  
Notify of