Thiết kế và đánh giá thuật toán - 16

for(j = 1; j <= n; j++) if(Cmin>C[i][j])

Cmin = C[i][j]; f* = maxint;//Gia tri toi uu f*

S = 0; // Chi phi

x[1] = 1; // Xuat phat tu dinh 1

}

Try(i)

/* xác định thành phố đến thứ i*/

{

for (j = 2; j <= n; j++) if(!Daxet[j])

{

x[i] = j;

Daxet[j] = 1;

S = S + C[x[i-1]][x[i]]; // cap nhat chi phi if(i==n)//Cap nhat hanh trinh toi uu

{

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

if(Tong < f*)

{

}

else

{

x*=x;// phuong an tot nhat hien co f* = Tong;// f* = f(x*)

}

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

Try(i+1);

}

// Hoan tra trang thai S = S - C[x[i-1]][x[i]];

Daxet[j] = 0;

}

}

Ví dụ 5.1.

Giải bài toán người du lịch theo thuật toán trình bày trên với ma trận chi phí:

0	3	14	18	15
3	0	4	22	20
C =	17	9	0	16	4
	6	5	7	0	12
	9	15	11	5	0

Có thể bạn quan tâm!

• Thiết kế và đánh giá thuật toán - 13
• Thiết kế và đánh giá thuật toán - 14
• Thiết kế và đánh giá thuật toán - 15
• Trọng Lượng Và Giá Trị Của 4 Loại Đồ Vật
• Thiết kế và đánh giá thuật toán - 18
• Quy Tắc Tam Giác Pascal O(N,k) Chính Là Comb(N,k) Và Ta Có Giải Thuật Như Sau:

Xem toàn bộ 205 trang tài liệu này.

Ta có cmin = 3. Quá trình thực hiện thật toán được mô tả bởi cây tìm kiếm lời giải cho trong hình dưới đây:

f* = + ∞

= 18

g = 30

(4)

= 23

g = 32

(2,5)

Các nhánh này bị loại vì có cận dưới g > f*= 22

Hành trình x*= (1,2,3,4,5) Chi phí là 44. Đặt f*=44

Hành trình x*= (1,2,3,5,4) Chi phí là 22. Đặt f*=22

=3 g=15

(2)

= 14

g= 16

(3)

= 15

g = 27

(5)

= 7

(2,3)

g = 16

= 25

g = 34

(2,4)

= 23

g = 29

(2,3,4)

= 11

g = 17

(2,3,5)

(2,3,4,5)

= 35

g = 38

(2,3,5,4)

= 16

g = 19

Hình 5.1. Cây tìm kiếm lời giải

Thông tin về một phương án bộ phận trên cây được ghi trong các ô ở trên hình vẽ tuơng ứng theo thứ tự sau: Đầu tiên là các thành phần của phương án, tiếp đến  là chi phí theo hành trình bộ phận và g – cận duới.

Kết thúc thuật toán , ta thu đựơc phương án tối ưu (1, 2, 3, 5, 4) tương ứng với hành trình

1 -> 2 -> 3 -> 4 ->5->1 với chỉ nhỏ nhất là 22.

Một cải tiến của kỹ thuật nhánh cận giải bài toán người du lịch

Ở trên chúng ta đã xem xét một cách xây dựng cận dưới khá đơn giản cho bài toán người du lịch. Chương trình được cài đặt theo các thuật toán đó, tuy rằng làm việc tốt hơn nhiều so với duyệt toàn bộ, nhưng cũng chỉ có thể áp dụng để giải các bài toán với kích thước nhỏ. Muốn giải được bài toán người du lịch với kích thước lớn cần có cách đánh giá cận tốt hơn. Dưới đây ta sẽ xem xét một trong những phương pháp xây dựng thuật toán theo kỹ thuật nhánh cho phép giải bài toán người du lịch với kích thước lớn hơn.

Mỗi hành trình của người du lịch (1 , 2,.. , n) có thể là viết lại dưới dạng (1, 2), (2, (3),… (n-1, n), (n, 1)

Trong đó mỗi thành phần (j-1, j) sẽ được gọi là một cạnh của hành trình.

Trong bài toán người du lịch khi tiến hành tìm kiếm lời giải chúng ta sẽ phân tập các hành trình ra thành hai tập con: một tập gồm những hành trình chứa một cạnh(i,j) nào đó còn tập kia gồm những hành trình không chứa cạnh này. Ta gọi việc làm đó là phân nhánh và mỗi tập con nói trên sẽ được gọi là nhánh hay một nút tìm kiếm. Việc phân nhánh được minh hoạ bởi cây tìm kiếm:

Tập tất cả các hành trình

hành trình chứa (i,j)

HT không chứa ((i,j)

Hình 5.2. Phân nhánh bởi cạnh (i,j)

Việc phân nhánh sẽ được thực hiện trên một quy tắc Ơristic nào đó cho phép ta rút ngắn quá trình tìm kiếm phương án tối ưu. Sau khi phân nhánh chúng ta sẽ tính cận dưới của giá trị hàm mục tiêu trên mỗi một trong hai tập con nói trên. Việc

tìm kiếm sẽ được tiếp tục trên tập con có giá trị cận dưới nhỏ hơn. Thủ tục này sẽ được tiếp tục cho đến khi thu đươc một hành trình đầy đủ, tức là một phương án của bài toán người du lịch. Khi đó ta chỉ cần xét những tập con các phương án nào có cận dưới nhỏ hơn giá trị mục tiêu tại phương án đã tìm được. Quá trình phân nhánh và tính cận trên tập các phương án của bài toán thông thường cho phép rút ngắn một cách đáng kể quá trình tìm kiếm do ta loại được khá nhiều tập con chắc chắn không chứa phương án tối ưu.

Rút gọn ma trận (tính chi phí cận dưới)

Rò ràng tổng chi phí của một hành trình của người du lịch sẽ chứa đúng một phần tử của mỗi dòng và một phần tử của mỗi cột trong ma trận chi phí C Do đó, nếu ta trừ bớt mỗi phần tử của một dòng (hay một cột) của ma trận C đi cùng một số  thì độ dài của tất cả các hành trình sẽ cùng giảm đi . Vì thế hành trình tối ưu cũng sẽ không thay đổi. Vì vậy nếu ta tiến hành trừ bớt các phần tử của mỗi dòng và mỗi cột đi một hằng số sao cho thu được ma trận gồm các phần tử không âm mà trong mỗi dòng và mỗi cột của nó đều có ít nhất một số không thì tổng các hằng số trừ đó sẽ cho ta cận dưới của mọi hành trình. Thủ tục trừ bớt này sẽ được gọi là thủ tục rút gọn. Các hằng số trừ ở mỗi dòng (cột) sẽ được gọi là hằng số rút gọn theo mỗi dòng (cột) còn ma trận thu được sẽ gọi là ma trận rút gọn.

Reduce(A,k)

/* Hàm này rút gon ma trận A có kích thước k*/

{

sum:= 0 for(i=1;i<=k;i++)

{

r[i]= <phần tử nhỏ nhất trong dòng i>; if r[i]>0 then

{

<bớt mỗi phần tử của dòng i đi r[i] >; sum := sum +r[i];

}

}

for(j=1;j<=k;j++)

{

s[j] =<phần tử nhỏ nhất trong cột j >; if s[j] >0 then

{

<bớt mỗi phần tử của cột j đi s[j] > ; sum := sum +s[j] ;

}

}

return(sum);

}

Chọn cạnh phân nhánh và phân nhánh

Để phân các hành trình thành hai nhánh, ta phải chọn một cạnh (i, j) từ đó phân các hành trình thành hai nhánh: một nhánh gồm những hành trình có chứa cạnh (i, j), một nhánh gồm những hành trình không chứa canh (i, j).

Để chọn cạnh (i, j) trong ma trận rút gọn ta tìm số 0 nào mà khi ta thay nó bằng  thì sẽ được tổng các hằng số rút gọn là lớn nhất khi đó cạnh (i, j) cần chọn sẽ chính là cạnh ứng với số 0 này.

Intput: Ma trận rút gọn A kích thước k k

Output: Cạnh phân nhánh (r,c) tổng hằng số rút gọn theo dòng r cột c là beta. BestEage (A,k,r,c,beta)

/* Hàm tìm cạnh phân nhánh*/

{

Beta:=-; for(i=1;i<=k;i++) for(j=1;j<=k;j++)

If (a[i,j] ==0)

{

Minr = < phần tử nhỏ nhất trên dòng i khác với a[i;j] >;

Minc =< phần tử nhỏ nhất trên cột j khác với a[i;j] >; Total = minr + minc;

If total > beta then

{

Beta = total:

r = i ; /* chỉ số dòng của cạnh tốt nhất */ c = j ; /* chỉ số cột của cạnh tốt nhất */

}

}

return(i,j);

}

Khi chọn được cạnh phân nhánh (i, j) ta sẽ phân các hành trình thành hai

nhánh:

- Với nhánh gồm các hành trình có chứa cạnh (i, j) ta thay số 0 ở hàng i cột j

bằng  và tiến hành rút gọn ma trận, cận dưới của nhánh này sẽ được cộng thêm tổng các hằng số rút gọc ở hàng i cột j.

- Với nhánh gồm những hành trình không chứa cạnh (i, j) ta xoá khỏi ma trận hàng i cột j, ngăn cấm việc tạo thành hành trình con và rút gọn ma trận (nếu được)

Ngăn cấm tạo thành hành trình con

Trong quá trình phân nhánh (theo nhánh có cận dưới nhỏ hơn) luôn phải chú ý ngăn cấm việc tạo thanh hành trình con. Đó là hành trình chưa đi qua tất cả các thành phố. Khi phân nhánh dựa vào cạnh (i, j) ta phải thêm cạnh này vào hành trình. ở mỗi bước khi lựa chọn cạnh để kết nạp ta cần phải xét xem nó có tạo với các cạnh đã có một hành trình con không, nếu có cần phải loại bỏ cạnh này và chọn cạnh có độ ưu tiên tiếp theo.

Việc ngăn cấm tạo thành hành trình con có thể thực hiện như sau: Input S danh sách các cạnh đã chọn, (i, j) cạnh mới.

Nếu N(S) < n thì:

- Sắp xếp lại các cạnh trong tập S’ = S  (i, j) theo dạng danh sách

- Nếu đỉnh đầu trùng với đỉnh cuối trong S’ thì kt=1, ngược lại kt=0 và S = S’

Output kt, S.

Tiếp tục việc chọn cạnh phân nhánh (và ngăn cấm việc tạo thành hành trình con) thì kích thước của ma trận chi phí C sẽ giảm dần theo một nhánh (nhánh trái). Cuối cùng ma trận sẽ còn kích thước 2 x 2 thì chấm dứt việc phân nhánh và kết nạp hai cạnh còn lại để thu được hành trình của người du lịch. Ma trận rút gọn cuối cùng này chỉ có thể có một trong hai dạng sau:

w	x		w	x
u	0		u		0
v		0	v	0	

trong đó u,v,w, x có thể là bốn đỉnh khác nhau hoặc chỉ có 3 đỉnh khác nhau. Khi đó ta sẽ chọn đưa vào hành trình các cạnh tương ứng với các phần tử 0 và ta được một hành trình T với chi phí thực tế là G. Nếu giá trị G nhỏ hơn tất cả các cận dưới của các nhánh đã bỏ qua thì hành trình nhận được là hành trình tối ưu, nếu không thì G lớn hơn giá trị cận dưới của một nhánh nào đó và khi đó thì hành trình nhận được chưa phải là hành trình tối ưu, ta tiếp tục áp dụng thuật toán nhánh cận cho nhánh này để tìm hành trình mới.

Các bước chính của thuật toán nhánh cận giải bài toán người du lịch được mô tả trong hàm đệ qui TSP sau đây. Hàm TSP xét hành trình bộ phận với Edges cạnh đã được chọn và tiến hành tìm kiếm tiếp theo. Ta sử dụng các biến:

Edges - số cạnh trong hành trình bộ phận ;

A - ma trận chi phí tương ứng với kích thước (n-edges) (n-edges); cost -chi phí của hành trình bộ phận.

Mincost - chi phí của hành trình tốt nhất đã tìm được.

Trong hàm sử dụng hàm Reduce(A, K) và hàm BestEdge(A, k, r, c, beta) TSP(edges, cost, A)

{

cost= cost +reduce(A, n-edges); if(edges == n-2)

{

<bổ sung nốt hai cạnh còn lại>; Mincost = cost;

<Ghi nhận hành trình tốt nhất>;

}

else

{

BestEdge(A,n-edges,g,c,beta); lowerBound= cost + beta;

<Ngăn cấm tạo thành hành trình con>; newA=<A loại bỏ dòng r cột c>

TSP(edges+1, cost, newA); /* đi theo nhánh trái */

<Khôi phục A bằng cánh bổ sung lại dòng r cột k>; If(LowerBound <Mincost)

{ /*đi theo nhánh phải*/ A[r,c]= ;

TSP(edges, cost, A); A[r,c]=0 ;

}

}

}

Ví dụ 5.2.

<khôi phục ma trận A>; /* thêm lại các hằng số rút gọn

vào các dòng và các cột tương ứng */

1 2			3	4	5
1		7	11	6	8
2	4		9	12	7
3	16	8		5	10
4	6	7	9		16
5	15	9	18	5	

Dùng thuật toán nhánh cận (bằng cách chọn cạnh phân nhánh) tìm hành trình tối ưu cho bài toán người du lịch với ma trận chi phí như sau:

C =

- Rút gọn ma trận