Bài giảng Thuật toán ứng dụng - Bài 3 - Đỗ Phan Thuận

cố định thành phố xuất phát là 71. Bài toán Ngưòi du lịch được đưa về bài toán: Tìm cực tiêu của hàm f(x2,x3,.,xn) = c[l,x2] + c[x2,x3] + . + c[x„_i,x„] + c[xn,Xi] -> min Gọi: Cmin = min {c[7, j], i,j = l,2,.,n,i / j} là chi phí đi lại nhỏ nhất giữa các thành phố. Giả sử ta đang có phương án bộ phận (ưi, Ư2. Uk) tương ứng vói hành trình bộ phận qua k thành phố: 71 —> 7"(Ư2) T(uk-1) —ì T(uk). vói chi phí phải trả theo hành trình bộ phận này là ơ = c[l, u2] + c[u2, ừ3] + . . . + c[xfc_1; U/J. Do chi phí phải trả cho việc đi qua mỗi một trong số n — k 4-1 đoạn đưòng còn lại đều không nhiều hơn Cmin => cận dưới cho phương án bộ phận (ơi, í/2,., Uk)'. g(u!, u2,., uk) = ơ + (n - k + l)cmin