Bài toán:

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

Gọi C _ij là chi phí đi từ thành phố Ti đến thành phố 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.

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(a₂,.., a_n ) : (a₂,.., a_n ) là hoán vị của {2,..,n}}.

Với f(a1,…, an) = C₁, _a2 + C_a2,a3+…+ C_an-1,an + C_an,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 x_i 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(x₁,.., x_i)

If g(x₁,.., x_i)≤ 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í :

S_i = C₁, _x2 + C_x2,x3+…+ C_xn-1,xn + C_xn,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 ( x₁ ,…, x_i ) = S_i + (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 + C_xn,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- C_x-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í: