Bài Toán Người Du Lịch - .vn

Phân tích, thiết kế thuật toán

Gọi ∏ là một hoán vị của {1,.., n} thì một thành phố thỏa mãn yêu cầu bài toán có dạng : T∏(1) → T∏(2) → … → T∏(n) .

Nếu ta cố định một thành phố xuất phát, chẳng hạn T1, thì có (n-1)! Hành trình

Bài toán chuyển về dạng :

Tìm Min{f(a2,.., an ) : (a2,.., an ) là hoán vị của {2,..,n}}.

Với f(a1,…, an) = C1, a2 + Ca2,a3+…+ Can-1,an + Can,1

Cách giải bài toán sẽ kết hợp đánh giá nhánh cận trong quá trình liệt kê phương án của thuật toán quay lui.

Thiết kế thuật toán:

Input C = (Cij )

Output - x* = (x1,...,xn) // Hành trình tối ưu

- f* = f(x*) // Giá trị tối ưu

Try (i)

for (j = 1 -> n)

if( Chấp nhận được )

{

Xác định xi theo j;

Ghi nhận trạng thái mới;

if(i == n)

Cập nhật lời giải tối ưu;

else

{

Xác định cận g(x1,.., xi)

If g(x1,.., xi)≤ f* )

Try (i+1);

}

// Trả bài toán về trạng thái cũ

}

o Nếu ta cố định xuất phát tư T1, ta duyệt vòng lặp từ j = 2.

o Đánh giá nhánh cận :

Đặt : CMin = Min{Cij : i, j € {1,..,n}

Giả sử vào bước i ta tìm được lời giải bộ phận cấp i là (x1,..,xi ), tức là đã đi

qua đoạn đường T1 -> T2 -> . . . ->Ti , tương ứng với chi phí :

Si = C1, x2 + Cx2,x3+…+ Cxn-1,xn + Cxn,1

Để phát triển hành trình bộ phận này thành một hành trình đầy đủ, ta còn phải đi qua n-i+1 đoạn đường nữa, gồm n-i thành phố còn lại và đoạn quay lại T1. Do chi phí mỗi một trong n-i+1 đoạn còn lại không nhỏ hơn CMin, nên hàm đánh giá cận có thể xác định như sau :

g ( x1 ,…, xi ) = Si + (n - i + 1)CMin

o Điều kiện chấp nhận được của j là thành phố Tj chưa đi qua.

Ta dùng một mảng logic Daxet[] để biểu diễn trạng thài này

Daxet[ j] = ? 1 ; T j đã được đi qua

0 ; T j chưa được đi qua

Mảng Daxet[ ] phải được bằng 0 tất cả.

o Xác định xi theo j bằng câu lệnh gán : xi = j

Cập nhật trạng thái mới : Daxet[j] = 1.

Cập nhật lại chi phí sau khi tìm được xi : S = S+ C

o Cập nhật lời giải tối ưu :

Tính chi phí hành trình vừa tìm được :

Tong = S + Cxn,1 ;

Nếu (Tong < f*) thì

Lgtu = x;

f* = Tong;

o Thao tác huỷ bỏ trạng thái : Daxet[j] = 0.

Trả lại chi phí cũ : S = S- Cx-1xi

Thủ tục nhánh cận viết lại như sau :

Try(i)

for (j = 2 -> n)

if(!Daxet[j])

{

x[i] = j; Daxet[j] = 1;

S = S + C[x[i-1]][x[i]];

if(i==n)

{

//Cap nhat toi uu

Tong = S + C[x[n]][x[1]];

if(Tong < f*)

{

Lgtu = x;

f* = Tong;

}

}

else

{

g = S + (n-i+1)*Cmin; //Danh gia can

if ( g < f*)

Try(i+1);

}

S = S - C[x[i-1]][x[i]];

Daxet[j] = 0;

}

Minh họa

Ma trận chi phí: