DAA - Vấn đề nhân viên bán hàng đi du lịch

Báo cáo vấn đề

Một khách du lịch cần phải đến thăm tất cả các thành phố từ một danh sách, nơi có khoảng cách giữa tất cả các thành phố và mỗi thành phố chỉ nên đến thăm một lần. Con đường ngắn nhất có thể mà anh ta đến thăm mỗi thành phố đúng một lần và trở về thành phố gốc là gì?

Giải pháp

Bài toán nhân viên bán hàng đi du lịch là bài toán tính toán khét tiếng nhất. Chúng tôi có thể sử dụng phương pháp tiếp cận bạo lực để đánh giá mọi chuyến tham quan có thể có và chọn chuyến tham quan tốt nhất. Đối vớin số đỉnh trong một đồ thị, có (n - 1)! số khả năng.

Thay vì sử dụng cách tiếp cận lập trình động, giải pháp có thể thu được trong thời gian ngắn hơn, mặc dù không có thuật toán thời gian đa thức.

Hãy để chúng tôi xem xét một đồ thị G = (V, E), Ở đâu V là một tập hợp các thành phố và Elà tập hợp các cạnh có trọng số. Một cạnhe(u, v) đại diện cho các đỉnh đó u và vđược kết nối. Khoảng cách giữa các đỉnhu và v Là d(u, v), không được âm.

Giả sử chúng ta đã bắt đầu ở thành phố 1 và sau khi thăm một số thành phố, chúng tôi đang ở thành phố j. Do đó, đây là một chuyến tham quan một phần. Chúng tôi chắc chắn cần biếtj, vì điều này sẽ xác định thành phố nào thuận tiện nhất để ghé thăm tiếp theo. Chúng tôi cũng cần biết tất cả các thành phố đã ghé thăm cho đến nay, để chúng tôi không lặp lại bất kỳ thành phố nào trong số đó. Do đó, đây là một vấn đề phụ thích hợp.

Đối với một tập hợp con các thành phố S Є {1, 2, 3, ... , n} bao gồm 1và j Є S, để cho C(S, j) là độ dài của đường đi ngắn nhất truy cập vào mỗi nút trong S chính xác một lần, bắt đầu từ 1 và kết thúc ở j.

Khi nào |S| > 1, chúng tôi xác địnhC(S, 1) = ∝ vì đường dẫn không thể bắt đầu và kết thúc tại 1.

Bây giờ, hãy bày tỏ C(S, j)xét về các vấn đề phụ nhỏ hơn. Chúng ta cần bắt đầu lúc1 và kết thúc ở j. Chúng ta nên chọn thành phố tiếp theo theo cách

$$ C (S, j) = min \: C (S - \ lbrace j \ rbrace, i) + d (i, j) \: where \: i \ in S \: and \: i \ neq jc ( S, j) = minC (s- \ lbrace j \ rbrace, i) + d (i, j) \: where \: i \ in S \: and \: i \ neq j $$

Algorithm: Traveling-Salesman-Problem 
C ({1}, 1) = 0 
for s = 2 to n do 
   for all subsets S Є {1, 2, 3, … , n} of size s and containing 1 
      C (S, 1) = ∞ 
   for all j Є S and j ≠ 1 
      C (S, j) = min {C (S – {j}, i) + d(i, j) for i Є S and i ≠ j} 
Return minj C ({1, 2, 3, …, n}, j) + d(j, i)

Phân tích

Có nhiều nhất $ 2 ^ nn $ bài toán con và mỗi bài toán cần thời gian tuyến tính để giải. Do đó, tổng thời gian chạy là $ O (2 ^ nn ^ 2) $.

Thí dụ

Trong ví dụ sau, chúng tôi sẽ minh họa các bước để giải quyết vấn đề nhân viên bán hàng đi du lịch.

Từ đồ thị trên, lập bảng sau.

	1	2	3	4
1	0	10	15	20
2	5	0	9	10
3	6	13	0	12
4	số 8	số 8	9	0

S = Φ

$$ \ small Cost (2, \ Phi, 1) = d (2,1) = 5 \ small Cost (2, \ Phi, 1) = d (2,1) = 5 $$

$$ \ small Cost (3, \ Phi, 1) = d (3,1) = 6 \ small Cost (3, \ Phi, 1) = d (3,1) = 6 $$

$$ \ small Cost (4, \ Phi, 1) = d (4,1) = 8 \ small Cost (4, \ Phi, 1) = d (4,1) = 8 $$

S = 1

$$ \ small Cost (i, s) = min \ lbrace Cost (j, s - (j)) + d [i, j] \ rbrace \ small Cost (i, s) = min \ lbrace Cost (j, s ) - (j)) + d [i, j] \ rbrace $$

$$ \ small Cost (2, \ lbrace 3 \ rbrace, 1) = d [2,3] + Cost (3, \ Phi, 1) = 9 + 6 = 15cost (2, \ lbrace3 \ rbrace, 1) = d [2,3] + chi phí (3, \ Phi, 1) = 9 + 6 = 15 $$

$$ \ small Cost (2, \ lbrace 4 \ rbrace, 1) = d [2,4] + Cost (4, \ Phi, 1) = 10 + 8 = 18cost (2, \ lbrace4 \ rbrace, 1) = d [2,4] + chi phí (4, \ Phi, 1) = 10 + 8 = 18 $$

$$ \ small Cost (3, \ lbrace 2 \ rbrace, 1) = d [3,2] + Cost (2, \ Phi, 1) = 13 + 5 = 18cost (3, \ lbrace2 \ rbrace, 1) = d [3,2] + chi phí (2, \ Phi, 1) = 13 + 5 = 18 $$

$$ \ small Cost (3, \ lbrace 4 \ rbrace, 1) = d [3,4] + Cost (4, \ Phi, 1) = 12 + 8 = 20cost (3, \ lbrace4 \ rbrace, 1) = d [3,4] + chi phí (4, \ Phi, 1) = 12 + 8 = 20 $$

$$ \ small Cost (4, \ lbrace 3 \ rbrace, 1) = d [4,3] + Cost (3, \ Phi, 1) = 9 + 6 = 15cost (4, \ lbrace3 \ rbrace, 1) = d [4,3] + chi phí (3, \ Phi, 1) = 9 + 6 = 15 $$

$$ \ small Cost (4, \ lbrace 2 \ rbrace, 1) = d [4,2] + Cost (2, \ Phi, 1) = 8 + 5 = 13cost (4, \ lbrace2 \ rbrace, 1) = d [4,2] + chi phí (2, \ Phi, 1) = 8 + 5 = 13 $$

S = 2

$$ \ small Cost (2, \ lbrace 3, 4 \ rbrace, 1) = \ begin {case} d [2, 3] + Cost (3, \ lbrace 4 \ rbrace, 1) = 9 + 20 = 29 \ \ d [2, 4] + Chi phí (4, \ lbrace 3 \ rbrace, 1) = 10 + 15 = 25 = 25 \ small Cost (2, \ lbrace 3,4 \ rbrace, 1) \\\ lbrace d [ 2,3] + \ chi phí nhỏ (3, \ lbrace4 \ rbrace, 1) = 9 + 20 = 29d [2,4] + \ small Cost (4, \ lbrace 3 \ rbrace, 1) = 10 + 15 = 25 \ end {case} = 25 $$

$$ \ small Cost (3, \ lbrace 2, 4 \ rbrace, 1) = \ begin {case} d [3, 2] + Cost (2, \ lbrace 4 \ rbrace, 1) = 13 + 18 = 31 \ \ d [3, 4] + Chi phí (4, \ lbrace 2 \ rbrace, 1) = 12 + 13 = 25 = 25 \ small Cost (3, \ lbrace 2,4 \ rbrace, 1) \\\ lbrace d [ 3,2] + \ chi phí nhỏ (2, \ lbrace4 \ rbrace, 1) = 13 + 18 = 31d [3,4] + \ small Cost (4, \ lbrace 2 \ rbrace, 1) = 12 + 13 = 25 \ end {case} = 25 $$

$$ \ small Cost (4, \ lbrace 2, 3 \ rbrace, 1) = \ begin {case} d [4, 2] + Cost (2, \ lbrace 3 \ rbrace, 1) = 8 + 15 = 23 \ \ d [4, 3] + Chi phí (3, \ lbrace 2 \ rbrace, 1) = 9 + 18 = 27 = 23 \ small Cost (4, \ lbrace 2,3 \ rbrace, 1) \\\ lbrace d [ 4,2] + \ chi phí nhỏ (2, \ lbrace3 \ rbrace, 1) = 8 + 15 = 23d [4,3] + \ small Cost (3, \ lbrace 2 \ rbrace, 1) = 9 + 18 = 27 \ end {case} = 23 $$

S = 3

$$ \ small Chi phí (1, \ lbrace 2, 3, 4 \ rbrace, 1) = \ begin {case} d [1, 2] + Chi phí (2, \ lbrace 3, 4 \ rbrace, 1) = 10 + 25 = 35 \\ d [1, 3] + Chi phí (3, \ lbrace 2, 4 \ rbrace, 1) = 15 + 25 = 40 \\ d [1, 4] + Chi phí (4, \ lbrace 2, 3 \ rbrace, 1) = 20 + 23 = 43 = 35 cost (1, \ lbrace 2,3,4 \ rbrace), 1) \\ d [1,2] + cost (2, \ lbrace 3,4 \ rbrace , 1) = 10 + 25 = 35 \\ d [1,3] + chi phí (3, \ lbrace 2,4 \ rbrace, 1) = 15 + 25 = 40 \\ d [1,4] + chi phí (4 , \ lbrace 2,3 \ rbrace, 1) = 20 + 23 = 43 = 35 \ end {case} $$

Đường dẫn chi phí tối thiểu là 35.

Bắt đầu từ chi phí {1, {2, 3, 4}, 1}, chúng tôi nhận được giá trị tối thiểu cho d [1, 2]. Khi nàos = 3, chọn đường dẫn từ 1 đến 2 (chi phí là 10) sau đó quay ngược lại. Khi nàos = 2, chúng tôi nhận được giá trị tối thiểu cho d [4, 2]. Chọn con đường từ 2 đến 4 (chi phí là 10) sau đó đi ngược lại.

Khi nào s = 1, chúng tôi nhận được giá trị tối thiểu cho d [4, 3]. Chọn đường dẫn 4 đến 3 (chi phí là 9), sau đó chúng ta sẽ đi đếns = Φbươc. Chúng tôi nhận được giá trị tối thiểu chod [3, 1] (chi phí là 6).