Thuật toán về người du lịch cài đặt bằng ngôn ngữ C/C++

Thuật toán về người du lịch cài đặt bằng ngôn ngữ C/C++

Bài toán: Một người du lịch muốn đi thăm 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 đúng một lần, rồi quay trở lại thành phố xuất phát. Biết cij là chi phí đi từ thành phố Ti đến thành phố Tj(i = 1, 2,.., n), hãy tìm hành trình với tổng chi phí là nhỏ nhất.

Giải: Có thể 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.

Khi tiến hành tìm kiếm lời giải bài toán người du lịch chúng ta phân tập các hành trình thành 2 tập con: Tập những hành trình chứa một cặp 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à sự phân nhánh, mỗi tập con như vậy được gọi là một nhánh hay một node của cây tìm kiếm.

Quá trình phân nhánh được minh hoạ bởi hình sau:

Thuật toán về người du lịch cài đặt bằng ngôn ngữ C/C++

Sau khi phân nhánh và tính cận dưới giá trị hàm mục tiêu trên mỗi tập con. Việc tìm kiếm sẽ tiếp tục trên tập con có giá trị cận dưới nhỏ hơn. Thủ tục này được tiếp tục cho đến khi ta nhận được một hành trình đầy đủ tức là một phương án cuả bài toán. 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ị của hàm 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 rất nhiều tập con .

1. Thủ tục rút gọn

Do người du lịch đi qua mỗi thành phố đúng một lần nên 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 hàng và đúng một phần tử của mỗi cột trong ma trận chi phí C. Do đó, nếu ta cộng hay trừ bớt mỗi phần tử của một hàng (hay 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 đều giảm đi α vì thế hành trình tối ưu cũng sẽ không bị thay đổi (vẫn là hành trình đó với chi phí giảm đi  α). Vì vậy, nếu ta tiến hành bớt đi các phần tử của mỗi hàng và mỗi cột đi một hằng số sao cho ta thu được một ma trận gồm các phần tử không âm mà trên mỗi hàng, mỗi cột đều có ít nhất một số 0, thì tổng các số trừ đó cho ta cận dưới của mọi hành trình. Thủ tục bớt này được gọi là thủ tục rút gọn, các hằng số trừ ở mỗi hàng (cột) sẽ được gọi là hằng số rút gọn theo hàng (cột), ma trận thu được được gọi là ma trận rút gọn. Thủ tục sau cho phép rút gọn ma trận một ma trận A kích thước k × k đồng thời

float Reduce(float A[][max], int k) {

 sum = 0;

 for (i = 1; i≤k; i++){

  r[i] = < phần tử nhỏ nhất của hàng i >;

  if (r[i] > 0) {

   <Bớt mỗi phần tử của hàng i đi r[i] >;

   sum = sum + r[i];

  }

 }

 for (j = 1; j≤k; j++) {

  s[j]: = <Phần tử nhỏ nhất của cột j>;

  if (s[j] > 0)

   sum = sum + S[j];

 }

 return(sum);

}

Ví dụ.Giả sử ta có ma trận chi phí với n= 6 thành phố sau:

  1 2 3 4 5 6 r[i]
1 3 93 13 33 9 3
2 4 77 42 21 16 4
3 45 17 36 16 28 16
4 39 90 80 56 7 7
5 28 46 88 33 25 25
6 3 88 18 46 92 3
s[j] 0 0 15 8 0 0  

Đầu tiên trừ bớt mỗi phần tử của các hàng 1, 2, 3, 4, 5, 6 cho các hằng số rút gọn tương ứng là ( 3, 4, 16, 7, 25, 3), sau đó trong ma trận thu được ta trừ bớt các phần tử của cột 3 và 4 tương ứng là (15, 8) ta nhận được ma trận rút gọn sau:

  1 2 3 4 5 6
1 0 75 2 30 6
2 0 58 30 17 12
3 29 1 12 0 12
4 32 83 58 49 0
5 3 21 48 0 0
6 0 85 0 35 89

Tổng các hằng số rút gọn là 3+4+16+7+25+3+15+8 = 81, vì vậy cận dưới cho tất cả các hành trình là 81 (không thể có hành trình có chi phí nhỏ hơn 81).

Bây giờ ta xét cách phân tập các phương án ra thành hai tập. Giả sử ta chọn cạnh (6, 3) để phân nhánh. Khi đó tập các hành trình được phân thành hai tập con, một tập là các hành trình đi qua cạnh này, còn một hành trình không đi qua cạnh này. Vì hành trình không đi qua cạnh (6,3) nên ta có thể cấm hành trị đi qua bằng cách đặt C[6, 3] = ∞. Do C[6, 3] = ∞ nên ma trận thu được sẽ có thể rút gọn bằng cách bớt đi mỗi phần tử của cột 3 đi 48 và không bớt gì các phần tử của hàng thứ 6. Như vậy ta thu được cận dưới của hành trình không chứa cạnh (6,3) là 81 + 48 = 129. Còn đối với tập chứa cạnh (6, 3) ta phải loại hàng 6, cột 3 khỏi ma trận tương ứng với nó, bởi vì đã đi theo cạnh (6, 3) thì không thể đi từ 6 sang bất sang bất cứ nơi nào khác và cũng không được phép đi bất cứ đâu từ 3. Kết quả nhận được là ma trận với bậc giảm đi 1. Ngoài ra, do đã đi theo cạnh (6, 3) nên không được phép đi từ 3 đến 6 nữa, vì vậy cần cấm đi theo cạnh (3, 6) bằng cách đặt C(3, 6) = ∞.

Cây tìm kiếm lúc này có dạng như trong hình.

 

Cận dưới = 81
  1 2 4 5 6
1 0 2 30 6
2 0 30 17 12
3 29 1 12 0
4 32 83 49 0
5 3 21 0 0

Hình 4

Cận dưới = 129
  1 2 3 4 5 6
1 0 27 2 30 6
2 0 10 30 17 12
3 29 1 12 0 12
4 32 83 10 49 0
5 3 21 0 0 0
6 0 85 35 89

Hình 5

Cạnh (6,3) được chọn để phân nhánh vì phân nhánh theo nó ta thu được cận dưới của nhánh bên phải là lớn nhất so với việc phân nhánh theo các cạnh khác. Qui tắc này sẽ được áp dụng ở để phân nhánh ở mỗi đỉnh của cây tìm kiếm. Trong quá trình tìm kiếm chúng ta luôn đi theo nhánh bên trái trước. Nhánh bên trái sẽ có ma trận rút gọn với bậc giảm đi 1. Trong ma trận của nhánh bên phải ta thay một số bởi ∞, và có thể rút gọn thêm được ma trận này khi tính lại các hằng số rút gọn theo dòng và cột tương ứng với cạnh phân nhánh, nhưng kích thước của ma trận vẫn giữ nguyên.

Do cạnh chọn để phân nhánh phải là cạnh làm tăng cận dưới của nhánh bên phải lên nhiều nhất, nên để tìm nó ta sẽ chọn số không nào trong ma trận mà khi thay nó bởi ∞ sẽ cho ta tổng hằng số rút gọn theo dòng và cột chứa nó là lớn nhất. Thủ tục đó có thể được mô tả như sau để chọn cạnh phân nhánh (r, c).

2. Thủ tục chọn cạnh phân nhánh (r,c).

void BestEdge(A, k, r, c, beta)

Đầu vào : Ma trận rút gọn A kích thước k ×k

Kết quảra : Cạnh phân nhánh(r, c) và tổng hằng số rút gọn theo dòng r cột c là beta.

{

 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) {

     beta = total;

     r = i; /* Chỉ số dòng tốt nhất*/

     c = j; /* Chỉ số cột tốt nhất*/

    }

   }

  }

 }

}

Trong ma trận rút gọn 5 ×5 của nhánh bên trái hình 4, số không ở vị trí (4, 6) sẽ cho tổng hằng số rút gọn là 32 ( theo hàng 4 là 32, cột 6 là 0). Đây là hệ số rút gọn có giá trị lớn nhất đối với các số không của ma trận này. Việc phân nhánh tiếp tục sẽ dựa vào cạnh (4, 6). Khi đó cận dưới của nhánh bên phải tương ứng với tập hành trình đi qua cạnh (6,3) nhưng không đi qua cạnh (4, 6) sẽ là 81 + 32 = 113. Còn nhánh bên trái sẽ tương ứng với ma trận 4 ×4 (vì ta phải loại bỏ dòng 4 và cột 6). Tình huống phân nhánh này được mô tả trong hình 5.

Nhận thấy rằng vì cạnh (4, 6) và (6, 3) đã nằm trong hành trình nên cạnh (3, 4) không thể đi qua được nữa (nếu đi qua ta sẽ có một hành trình con từ những thành phố này). Để ngăn cấm việc tạo thành các hành trình con ta sẽ gán cho phần tử ở vị trí (3, 4) giá trị ∞.

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

Tổng quát hơn, khi phân nhánh dựa vào cạnh (iu, iv) ta phải thêm cạnh này vào danh sách các cạnh của node bên trái nhất. Nếu iu là đỉnh cuối của một đường đi (i1, i2,.., iu) và jv là đỉnh đầu của đường đi (j1, j2,.., jk) thì để ngăn ngừa khả năng tạo thành hành trình con ta phải ngăn ngừa khả năng tạo thành hành hành trình con ta phải cấm cạnh (jk, i1). Để tìm i1 ta đi ngược từ iu, để tìm jk ta đi xuôi từ j1 theo danh sách các cạnh đã được kết nạp vào hành trình.

Tiếp tục phân nhánh từ đỉnh bên trái bằng cách sử dụng cạnh (2,1) vì số không ở vị trí này có hằng số rút gọn lớn nhất là 17 + 3 = 20 ( theo dòng 2 là 17, theo cột 1 là 3). Sau khi phân nhánh theo cạnh (2, 1) ma trận của nhánh bên trái có kích thước là 3 ×3. Vì đã đi qua (2, 1) nên ta cấm cạnh (2, 1) bằng cách đặt C[1, 2] = ∞, ta thu được ma trận sau:

  2 4 5
1 2 30
3 1 0
5 21 0

Ma trận này có thể rút gọn được bằng cách bớt 1 tại cột 1 và bớt 2 đi ở dòng 1 để nhận được ma trận cấp 3:

  2 4 5
1 0 28
3 0 0
5 20 0

Ta có cận dưới của nhánh tương ứng là 81 + 1 + 2 = 84. Cây tìm kiếm cho đến bước này được thể hiện trong hình 6.
Chú ý rằng, sau khi đã chấp nhận n-2 cạnh vào hành trình thì ma trận còn lại sẽ có kích thước là 2 ×2. Hai cạnh còn lại của hành trình sẽ không phải chọn lựa nữa mà được kết nạp ngay vào chu trình (vì nó chỉ còn sự lựa chọn duy nhất). Trong ví dụ trên sau khi đã có các cạnh (6, 3), (4,6), (2, 1), (1,4) ma trận của nhánh bên trái nhất có dạng:

  2 5
3 0
5 0

Vì vậy ta kết nạp nốt cạnh (3, 5), (5, 2) vào chu trình và thu được hành trình: 1, 4, 6, 3, 5, 2, 1 với chi phí là 104.

Trong quá trình tìm kiếm, mỗi node của cây tìm kiếm sẽ tương ứng với một ma trận chi phí A. Ở bước đầu tiên ma trận chi phí tương ứng với gốc chính là ma trận C. Khi chuyển động từ gốc xuống nhánh bên trái xuống phĩa dưới, kích thước của các ma trận chi phí A sẽ giảm dần. Cuối cùng khi ma trận A có kích thước 2×2 thì ta 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. Dễ dàng nhận thấy ma trận cuối cùng rút gọn chỉ có thể ở một trong hai dạng sau:

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

Trong đó u, v, x, y có thể là 4 đỉnh khác nhau hoặc 3 đỉnh khác nhau. Để xác định xem hai cạnh nào cần được nạp vào hành trình ta chỉ cần xét một phần tử của ma trận A:

if A[1, 1] = ∞ then

 <Kết nạp cạnh (u, x), (v, w)>

else

 < Kết nạp cạnh (u, w), ( v, x) >;

Bây giờ tất cả các node có cận dưới lớn hơn 104 có thể bị loại bỏ vì chúng không chứa hành trình rẻ hơn 104. Trên hình 6 chúng ta thấy chỉ có node có cận dưới là 101 < 104 là cần phải xét tiếp. Node này chứa các cạnh (6, 3), (4, 6) và không chứa cạnh (2, 1). Ma trận chi phí tương ứng với đỉnh này có dạng:

  1 2 4 5
1 0 2 30
2 13 0
3 26 1 0
5 0 21 0

Việc phân nhánh sẽ dựa vào cạnh (5, 1) với tổng số rút gọn là 26. Quá trình rẽ nhánh tiếp theo được chỉ ra như trong hình

Hành trình 1, 4, 6, 3, 2, 5, 1 ; Độ dài 104.

Như vậy chúng ta thu được hai hành trình tối ưu với chi phí là 104. Ví dụ trên cho thấy bài toán người du lịch có thể có nhiều phương án tối ưu. Trong ví dụ này hành trình đầu tiên nhận được đã là tối ưu, tuy nhiên điều này không thể mong đợi đối với những trường hợp tổng quát. Trong ví dụ trên chúng ta chỉ cần xét tới 13 node, trong khi tổng số hành trình của người du lịch là 120.

3. Thuật toán nhánh cận giải bài toán người du lịch.

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 thể hiện trong thủ tục TSP. Thủ tục TSP xét hành trình bộ phận với Edges là cạnh đã được chọn và tiến hành tìm kiếm tiếp theo. Các biến được sử dụng trong thủ tục này là:

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.

Hàm Reduce(A, k), BestEgde(A, k, r, c,beta) đã được xây dựng ở trên.

void TSP(Edges, cost, A) {

 cost = cost + Reduce(A, n - Edges);

 if (cost < MinCost){

  if (edges == n - 2){

   <bổxung nốt hai cạnh còn lại>;

  MinCost: = Cost;

  }

  else {

   BestEdge(A, n - eges, r, 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ách bổxung dòng r cột c>;

   if (LowerBound < MinCost){

    /* đi theo nhánh phải*/

    A[r, c] = ∞;

    TSP(edges, cost, A);

    A[r, c]: = 0;

   }

  }

  < 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ột tương ứng*/

 }

}/* end of TSP*/;
Bạn thấy bài viết này như thế nào?: 
Average: 7 (3 votes)
Ảnh của Tommy Tran

Tommy owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
First module in Symfony and Frameworks, Drupal 8

First module in Symfony and Frameworks, Drupal 8

Having recently started working with Drupal in module development and published my first public Module, my interests have gravitated around the next version of Drupal (v8) and what it holds in store.

Apple iPhone 5 và iPad 3 lộ diện trong iOS 5.1 beta

Apple iPhone 5 và iPad 3 lộ diện trong iOS 5.1 beta

Apple đã để rò rỉ một ít thông tin bí mật về một số các thiết bị di động sắp tới của mình như iPhone 5 và iPad 3, trong phiên bản thử nghiệm iOS 5.1 beta vừa mới được giới thiệu hồi đầu tuần.

Giới thiệu the state of ReST API trong Headless Drupal 8

Giới thiệu the state of ReST API trong Headless Drupal 8

This allows you to use all the Drupal 8 features to edit your content but present the content not only on a Drupal frontend but also on mobile apps or anything else that can work with JSON data.

Công ty diệt chuột T&C

 

Diet con trung