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

     

Bài toán: Một fan du ngoạn mong muốn đi thăm quan và du lịch n thành thị T1, T2, …, Tn. Xuất phân phát xuất phát điểm từ 1 thành phố làm sao đó, tín đồ du ngoạn muốn đi qua toàn bộ các thành thị sót lại, từng thành phố trải qua đúng một đợt, rồi quay lại thành phố căn nguyên. Biết cij là ngân sách đi từ bỏ thị thành Ti mang lại thị trấn Tj(i = 1, 2,.., n), hãy search hành trình dài cùng với tổng chi phí là nhỏ tuyệt nhất.

Bạn đang xem: Bài toán người du lịch

Giải: Có thể viết lại dưới dạng: (π(1), π(2), π(2), π(3),..., π(n-1), π(n), π(n), π(1) Trong số đó mỗi thành phần: π(j-1), π(j) sẽ tiến hành Hotline là 1 trong cạnh của hành trình.

khi thực hiện tìm tìm giải thuật bài bác toán thù fan phượt họ phân tập các hành trình thành 2 tập con: Tập phần lớn hành trình đựng một cặp cạnh (i, j) nào này còn tập cơ có phần nhiều hành trình dài ko đựng cạnh này. Ta Điện thoại tư vấn Việc làm cho đó là sự phân nhánh, từng tập bé điều này được Call là 1 trong những nhánh hay là 1 node của cây tìm kiếm kiếm.

Quá trình phân nhánh được minch hoạ vì hình sau:

*

Sau lúc phân nhánh với tính cận bên dưới giá trị hàm mục tiêu bên trên mỗi tập bé. Việc kiếm tìm tìm đã tiếp tục bên trên tập nhỏ có giá trị cận dưới nhỏ rộng. Thủ tục này được liên tiếp cho tới lúc ta cảm nhận một hành trình dài không thiếu tức là một phương án cuả bài xích tân oán. lúc đó ta chỉ cần xét hồ hết tập con những phương án làm sao bao gồm cận bên dưới nhỏ tuổi hơn quý giá của hàm mục tiêu trên cách thực hiện đang tìm kiếm được. Quá trình phân nhánh và tính cận bên trên tập các cách thực hiện của bài xích tân oán thông thường cho phép rút ngắn một biện pháp đáng chú ý quá trình tìm kiếm tìm vì ta nhiều loại được rất nhiều tập nhỏ .

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

Do bạn phượt đi qua từng thành phố đúng một lượt yêu cầu tổng chi phí của một hành trình của fan du lịch đang chứa đúng một phần tử của từng mặt hàng với đúng một phần tử của mỗi cột trong ma trận chi phí C. Do kia, trường hợp ta cộng hay trừ sút từng thành phần của một hàng (xuất xắc cột) của ma trận C đi cùng một số α thì độ lâu năm của toàn bộ các hành trình phần đông sụt giảm α chính vì như vậy hành trình dài buổi tối ưu cũng trở thành không trở nên biến hóa (vẫn chính là hành trình dài đó với chi phí giảm xuống α). Vì vậy, trường hợp ta tiến hành tiết kiệm hơn các thành phần của từng mặt hàng cùng từng cột đi một hằng số làm thế nào để cho ta chiếm được một ma trận tất cả các bộ phận ko âm mà lại bên trên từng sản phẩm, từng cột đều phải có ít nhất một trong những 0, thì tổng các số trừ kia mang đến ta cận dưới của phần lớn hành trình dài. Thủ tục giảm này được Gọi là thủ tục rút ít gọn gàng, các hằng số trừ sống mỗi hàng (cột) sẽ được Gọi là hằng số rút gọn gàng theo mặt hàng (cột), ma trận chiếm được được Gọi là ma trận rút ít gọn. Thủ tục sau được cho phép rút ít gọn gàng ma trận một ma trận A kích cỡ k × k đồng thời

float Reduce(float A<>, int k) sum = 0; for (i = 1; i≤k; i++) r = ; if (r > 0) ; sum = sum + r; for (j = 1; j≤k; j++) s: = ; if (s > 0) sum = sum + S; return(sum);

lấy một ví dụ.Giả sử ta bao gồm ma trận chi phí với n= 6 thị thành sau:


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


Tổng những hằng số rút gọn là 3+4+16+7+25+3+15+8 = 81, bởi vậy cận dưới cho tất cả những hành trình là 81 (quan yếu bao gồm hành trình có ngân sách bé dại hơn 81).

Bây giờ ta xét giải pháp phân tập những giải pháp ra thành nhị tập. Giả sử ta chọn cạnh (6, 3) để phân nhánh. lúc kia tập các hành trình được tạo thành nhì tập bé, một tập là những hành trình trả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 dài không trải qua cạnh (6,3) nên ta có thể cnóng hành trị đi qua bằng cách đặt C<6, 3> = ∞. Do C<6, 3> = ∞ phải ma trận nhận được vẫn rất có thể rút ít gọn gàng bằng cách ít hơn mỗi bộ phận của cột 3 đi 48 cùng ko sút gì những bộ phận của mặt hàng sản phẩm công nghệ 6. Vậy nên ta thu được cận bên dưới của hành trình ko cất cạnh (6,3) là 81 + 48 = 129. Còn đối với tập chứa cạnh (6, 3) ta buộc phải nhiều loại sản phẩm 6, cột 3 ngoài ma trận khớp ứng cùng với nó, bởi vì đã đi được theo cạnh (6, 3) thì quan trọng đi từ 6 lịch sự bất sang bất cứ chỗ nào khác và cũng không được phnghiền đi bất kể đâu tự 3. Kết trái nhận ra là ma trận với bậc giảm xuống 1. Dường như, vị đã đi được theo cạnh (6, 3) yêu cầu không được phnghiền đi tự 3 cho 6 nữa, bởi vì vậy cần cnóng đi theo cạnh (3, 6) bằng phương pháp đặt C(3, 6) = ∞.

Cây search kiếm hôm nay bao gồm dạng nhỏng vào hình.

*

 


Hình 5

Cạnh (6,3) được chọn nhằm phân nhánh vị phân nhánh theo nó ta thu được cận dưới của nhánh bên buộc phải là lớn số 1 so với bài toán phân nhánh theo các cạnh không giống. Qui tắc này sẽ được áp dụng sinh hoạt để phân nhánh làm việc mỗi đỉnh của cây tra cứu kiếm. Trong quy trình tìm kiếm kiếm họ luôn luôn đi theo nhánh bên trái trước. Nhánh phía trái sẽ sở hữu ma trận rút ít gọn gàng cùng với bậc giảm xuống 1. Trong ma trận của nhánh mặt đề xuất ta thay là 1 số do ∞, và rất có thể rút gọn thêm được ma trận này lúc tính lại những hằng số rút gọn gàng theo chiếc và cột tương ứng với cạnh phân nhánh, tuy thế form size của ma trận vẫn giữ nguyên.

Xem thêm: " Lẩu Nấm Ashima Huỳnh Thúc Kháng, Ashima Mushroom Hotpot 17 Huỳnh Thúc Kháng

Do cạnh chọn để phân nhánh phải là cạnh có tác dụng tăng cận bên dưới của nhánh mặt buộc phải lên những tốt nhất, đề nghị nhằm tìm kiếm nó ta đang chọn số không như thế nào vào ma trận mà Khi cầm nó bởi vì ∞ sẽ cho ta tổng hằng số rút ít gọn theo cái với cột chứa nó là lớn số 1. Thủ tục kia rất có thể được biểu thị nhỏng sau để lựa 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 ít gọn gàng A size k ×kKết quảra : Cạnh phân nhánh(r, c) với tổng hằng số rút ít gọn theo mẫu r cột c là beta. beta = -∞; for (i = 1; i≤k; i++) for (j = 1; j≤k; j++) if (A == 0) minr = beta) beta = total; r = i; /* Chỉ số mẫu tốt nhất*/ c = j; /* Chỉ số cột giỏi nhất*/ Trong ma trận rút ít gọn gàng 5 ×5 của nhánh phía bên trái hình 4, số ko tại vị trí (4, 6) đã mang đến tổng hằng số rút ít gọn là 32 ( theo sản phẩm 4 là 32, cột 6 là 0). Đây là thông số rút ít gọn gàng có giá trị lớn nhất so với những số ko của ma trận này. Việc phân nhánh liên tục sẽ phụ thuộc vào cạnh (4, 6). khi kia cận dưới của nhánh bên đề xuất tương xứng cùng với tập hành trình dài trải qua cạnh (6,3) cơ mà không trải qua cạnh (4, 6) đang là 81 + 32 = 113. Còn nhánh phía trái sẽ tương xứng với ma trận 4 ×4 (vày ta cần đào thải mẫu 4 với cột 6). Tình huống phân nhánh này được diễn tả trong hình 5.

Nhận thấy rằng vì chưng cạnh (4, 6) và (6, 3) đang nằm trong hành trình nên cạnh (3, 4) cần thiết trải qua được nữa (nếu đi qua ta sẽ sở hữu một hành trình con tự hầu hết thị thành này). Để ngăn cnóng Việc tạo ra thành những hành trình dài con ta sẽ gán cho phần tử tại đoạn (3, 4) cực hiếm ∞.

*

Ngăn uống cnóng chế tạo ra thành hành trình dài con:

Tổng quát hơn, Khi phân nhánh phụ thuộc vào cạnh (iu, iv) ta đề nghị thêm cạnh này vào danh sách các cạnh của node phía trái nhất. Nếu iu là đỉnh cuối của một lối đi (i1, i2,.., iu) và jv là đỉnh đầu của lối đi (j1, j2,.., jk) thì nhằm ngnạp năng lượng đề phòng khả năng tạo ra thành hành trình bé ta đề xuất ngnạp năng lượng đề phòng kỹ năng tạo thành hành hành trình dài con ta bắt buộc cnóng cạnh (jk, i1). Để search i1 ta đi ngược trường đoản cú iu, để search jk ta đi xuôi từ bỏ j1 theo list các cạnh đã được hấp thụ vào hành trình dài.

Tiếp tục phân nhánh trường đoản cú đỉnh phía trái bằng phương pháp sử dụng cạnh (2,1) vị số không ở trong phần này có hằng số rút gọn gàng lớn số 1 là 17 + 3 = trăng tròn ( 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 phía bên trái bao gồm size là 3 ×3. Vì vẫn trải qua (2, 1) phải ta cấm cạnh (2, 1) bằng phương pháp đặt C<1, 2> = ∞, ta chiếm được ma trận sau:


Ma trận này rất có thể rút ít gọn gàng được bằng cách bớt 1 trên cột 1 và giảm 2 đi nghỉ ngơi dòng 1 nhằm nhận thấy ma trận cấp 3:


Ta gồm cận bên dưới của nhánh tương ứng là 81 + 1 + 2 = 84. Cây tìm tìm cho tới công đoạn này được biểu đạt vào hình 6.

Xem thêm: Bật Mí 2 Cách Nấu Canh Khoai Sọ Nấu Sườn Khoai Sọ, Canh Sườn Khoai Sọ

Chú ý rằng, sau thời điểm sẽ đồng ý n-2 cạnh vào hành trình thì ma trận còn lại sẽ có được kích thước là 2 ×2. Hai cạnh còn sót lại của hành trình dài đã không phải chọn lựa nữa nhưng mà được tiếp thu ngay vào quy trình (vày nó chỉ còn sự tuyển lựa duy nhất). Trong ví dụ bên trên sau khi vẫn gồm những cạnh (6, 3), (4,6), (2, 1), (1,4) ma trận của nhánh phía trái tốt nhất bao gồm dạng:


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

Trong quá trình search kiếm, mỗi node của cây kiếm tìm kiếm vẫn khớp ứng với một ma trận chi phí A. Tại bước trước tiên ma trận chi phí khớp ứng với nơi bắt đầu chính là ma trận C. Khi hoạt động tự cội xuống nhánh phía bên trái xuống phĩa dưới, kích cỡ của các ma trận ngân sách A sẽ sút dần dần. Cuối cùng lúc ma trận A có form size 2×2 thì ta kết thúc Việc phân nhánh với tiếp thụ hai cạnh còn sót lại để thu được hành trình của fan phượt. Dễ dàng nhận ra ma trận sau cùng rút ít gọn chỉ hoàn toàn có thể sinh hoạt 1 trong các nhì dạng sau:


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

if A<1, 1> = ∞ then else ;Bây giờ đồng hồ toàn bộ những node có cận bên dưới lớn hơn 104 hoàn toàn có thể bị loại bỏ vị chúng ko đựng hành trình dài rẻ rộng 104. Trên hình 6 họ thấy chỉ có node có cận dưới là 101  12451∞02302∞∞1303261∞050210∞