Vấn đề nhân viên bán hàng đi du lịch: Python, C++ Thuật toán
Sarah Chen
Vấn đề nhân viên bán hàng du lịch (TSP) là gì?
Bài toán người bán hàng du lịch (TSP) là một bài toán tổ hợp kinh điển của khoa học máy tính lý thuyết. Bài toán yêu cầu tìm đường đi ngắn nhất trong biểu đồ với điều kiện chỉ truy cập tất cả các nút một lần và quay trở lại thành phố xuất phát.
Báo cáo bài toán đưa ra danh sách các thành phố cùng với khoảng cách giữa mỗi thành phố.
Mục tiêu: Để bắt đầu từ thành phố ban đầu, chỉ ghé thăm các thành phố khác một lần và quay lại thành phố ban đầu. Mục tiêu của chúng tôi là tìm ra con đường ngắn nhất có thể để hoàn thành lộ trình khứ hồi.
Ví dụ về TSP
Ở đây, một biểu đồ được đưa ra trong đó 1, 2, 3 và 4 đại diện cho các thành phố và trọng số liên quan đến mỗi cạnh biểu thị khoảng cách giữa các thành phố đó.
Mục tiêu là tìm ra con đường ngắn nhất có thể cho chuyến tham quan bắt đầu từ thành phố xuất phát, đi qua biểu đồ trong khi chỉ ghé thăm các thành phố hoặc nút khác một lần và quay trở lại thành phố xuất phát.
Đối với biểu đồ trên, lộ trình tối ưu là đi theo đường dẫn chi phí tối thiểu: 1-2-4-3-1. Và tuyến đường ngắn nhất này sẽ có giá 10+25+30+15 =80
Các giải pháp khác nhau cho vấn đề nhân viên bán hàng khi đi du lịch
Bài toán người bán hàng du lịch (TSP) được phân loại là bài toán NP-khó do không có thuật toán thời gian đa thức. Độ phức tạp tăng theo cấp số nhân khi số lượng thành phố tăng.
Có nhiều cách để giải bài toán người bán hàng du lịch (tsp). Một số giải pháp phổ biến là:
Cách tiếp cận vũ phu là phương pháp ngây thơ để giải quyết vấn đề nhân viên bán hàng du lịch. Trong phương pháp này, trước tiên chúng ta tính toán tất cả các đường đi có thể và sau đó so sánh chúng. Số đường đi trong đồ thị gồm n thành phố là n! Về mặt tính toán, việc giải quyết vấn đề nhân viên bán hàng du lịch theo cách tiếp cận bạo lực này là rất tốn kém về mặt tính toán.
Phương pháp nhánh và giới hạn: Vấn đề được chia thành các vấn đề phụ theo cách tiếp cận này. Giải pháp cho các vấn đề phụ riêng lẻ đó sẽ mang lại giải pháp tối ưu.
Hướng dẫn này sẽ trình bày cách tiếp cận lập trình động, phiên bản đệ quy của phương pháp rẽ nhánh và giới hạn này, để giải quyết vấn đề nhân viên bán hàng lưu động.
Lập trình năng động là một phương pháp tìm kiếm giải pháp tối ưu bằng cách phân tích tất cả các tuyến đường có thể. Đây là một trong những phương pháp giải chính xác giúp giải quyết các vấn đề của người bán hàng du lịch với chi phí tương đối cao hơn so với phương pháp tham lam đó đưa ra giải pháp gần tối ưu.
Độ phức tạp tính toán của phương pháp này là O(N^2 * 2^N) sẽ được thảo luận ở phần sau của bài viết này.
Phương pháp hàng xóm gần nhất là một phương pháp tiếp cận tham lam dựa trên phương pháp heuristic, trong đó chúng ta chọn nút lân cận gần nhất. Phương pháp này ít tốn kém hơn về mặt tính toán so với phương pháp động. Nhưng nó không đảm bảo giải pháp tối ưu. Phương pháp này được sử dụng cho các giải pháp gần tối ưu.
Thuật toán giải bài toán nhân viên bán hàng du lịch
Chúng ta sẽ sử dụng phương pháp lập trình động để giải Bài toán Người bán hàng du lịch (TSP).
Trước khi bắt đầu thuật toán, chúng ta hãy làm quen với một số thuật ngữ:
- Đồ thị G=(V, E), là tập hợp các đỉnh và cạnh.
- V là tập hợp các đỉnh.
- E là tập hợp các cạnh.
- Các đỉnh được kết nối thông qua các cạnh.
- Dist(i,j) biểu thị khoảng cách không âm giữa hai đỉnh i và j.
Giả sử S là tập con của các thành phố và thuộc về {1, 2, 3, …, n} trong đó 1, 2, 3…n là các thành phố và i, j là hai thành phố trong tập con đó. Bây giờ cost(i, S, j) được xác định theo cách như độ dài của nút truy cập đường đi ngắn nhất trong S, chính xác là điểm này có điểm bắt đầu và điểm kết thúc tương ứng là i và j.
Ví dụ: chi phí (1, {2, 3, 4}, 1) biểu thị độ dài của đường đi ngắn nhất trong đó:
- Thành phố bắt đầu là 1
- Thành phố 2, 3 và 4 chỉ được ghé thăm một lần
- Điểm kết thúc là 1
Thuật toán lập trình động sẽ là:
- Đặt cost(i, , i) = 0, nghĩa là chúng ta bắt đầu và kết thúc tại i và chi phí là 0.
- Khi |S| > 1, chúng ta xác định cost(i, S, 1) = ∝ trong đó i !=1 . Bởi vì ban đầu, chúng tôi không biết chính xác chi phí để đi từ thành phố i đến thành phố 1 qua các thành phố khác.
- Bây giờ, chúng ta cần bắt đầu từ số 1 và hoàn thành chuyến tham quan. Chúng ta cần chọn thành phố tiếp theo theo cách như vậy-
cost(i, S, j)=chi phí tối thiểu (i, S−{i}, j)+dist(i,j) trong đó i∈S và i≠j
Đối với hình vẽ cho sẵn, ma trận kề sẽ như sau:
| quận(i,j) | 1 | 2 | 3 | 4 |
| 1 | 0 | 10 | 15 | 20 |
| 2 | 10 | 0 | 35 | 25 |
| 3 | 15 | 35 | 0 | 30 |
| 4 | 20 | 25 | 30 | 0 |
Hãy xem thuật toán của chúng tôi hoạt động như thế nào:
Bước 1) Chúng tôi đang xem xét hành trình của mình bắt đầu từ thành phố 1, ghé thăm các thành phố khác một lần và quay lại thành phố 1.
Bước 2) S là tập con của các thành phố. Theo thuật toán của chúng tôi, đối với mọi |S| > 1, chúng tôi sẽ đặt chi phí khoảng cách(i, S, 1) = ∝. Ở đây, chi phí(i, S, j) có nghĩa là chúng tôi bắt đầu từ thành phố i, ghé thăm các thành phố của S một lần và bây giờ chúng tôi đang ở thành phố j. Chúng tôi đặt chi phí đường đi này là vô cực vì chúng tôi chưa biết khoảng cách. Vì vậy, các giá trị sẽ như sau:
Chi phí (2, {3, 4}, 1) = ∝ ; ký hiệu biểu thị chúng ta đang bắt đầu ở thành phố 2, đi qua các thành phố 3, 4 và đến 1. Và chi phí đường đi là vô cùng. Tương tự-
chi phí(3, {2, 4}, 1) = ∝
chi phí(4, {2, 3}, 1) = ∝
Bước 3) Bây giờ, đối với mọi tập hợp con của S, chúng ta cần tìm những điều sau:
cost(i, S, j)=chi phí tối thiểu (i, S−{i}, j)+dist(i,j), trong đó j∈S và i≠j
Điều đó có nghĩa là đường đi có chi phí tối thiểu để bắt đầu từ i, đi qua tập hợp con các thành phố một lần và quay trở lại thành phố j. Xét rằng hành trình bắt đầu ở thành phố 1, chi phí đường đi tối ưu sẽ là= cost(1, {other city}, 1).
Hãy cùng tìm hiểu làm thế nào chúng ta có thể đạt được điều đó:
Bây giờ S = {1, 2, 3, 4}. Có bốn yếu tố. Do đó số lượng tập hợp con sẽ là 2^4 hoặc 16. Những tập hợp con đó là-
1) |S| = Không:
{Φ}
2) |S| = 1:
{{1}, {2}, {3}, {4}}
3) |S| = 2:
{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}
4) |S| = 3:
{{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}}
5) |S| = 4:
{{1, 2, 3, 4}}
Khi chúng ta bắt đầu từ 1, chúng ta có thể loại bỏ các tập con chứa thành phố 1.
Thuật toán tính toán:
1) |S| = Φ:
chi phí (2, Φ, 1) = khoảng cách (2, 1) = 10
chi phí (3, Φ, 1) = khoảng cách (3, 1) = 15
chi phí (4, Φ, 1) = khoảng cách (4, 1) = 20
2) |S| = 1:
chi phí (2, {3}, 1) = khoảng cách (2, 3) + chi phí (3, Φ, 1) = 35+15 = 50
chi phí (2, {4}, 1) = khoảng cách (2, 4) + chi phí (4, Φ, 1) = 25+20 = 45
chi phí (3, {2}, 1) = khoảng cách (3, 2) + chi phí (2, Φ, 1) = 35+10 = 45
chi phí (3, {4}, 1) = khoảng cách (3, 4) + chi phí (4, Φ, 1) = 30+20 = 50
chi phí (4, {2}, 1) = khoảng cách (4, 2) + chi phí (2, Φ, 1) = 25+10 = 35
chi phí (4, {3}, 1) = khoảng cách (4, 3) + chi phí (3, Φ, 1) = 30+15 = 45
3) |S| = 2:
chi phí (2, {3, 4}, 1) = phút [ dist[2,3]+Cost(3,{4},1) = 35+50 = 85,
dist[2,4]+Cost(4,{3},1) = 25+45 = 70 ] = 70
chi phí (3, {2, 4}, 1) = phút [ dist[3,2]+Cost(2,{4},1) = 35+45 = 80,
dist[3,4]+Cost(4,{2},1) = 30+35 = 65 ] = 65
chi phí (4, {2, 3}, 1) = phút [ dist[4,2]+Cost(2,{3},1) = 25+50 = 75
dist[4,3]+Cost(3,{2},1) = 30+45 = 75 ] = 75
4) |S| = 3:
chi phí (1, {2, 3, 4}, 1) = phút [ dist[1,2]+Cost(2,{3,4},1) = 10+70 = 80
dist[1,3]+Cost(3,{2,4},1) = 15+65 = 80
dist[1,4]+Cost(4,{2,3},1) = 20+75 = 95 ] = 80
Vậy giải pháp tối ưu sẽ là 1-2-4-3-1
Mã giả
Algorithm: Traveling-Salesman-Problem
Cost (1, {}, 1) = 0
for s = 2 to n do
for all subsets S belongs to {1, 2, 3, … , n} of size s
Cost (s, S, 1) = Infinity
for all i Є S and i ≠ 1
Cost (i, S, j) = min {Cost (i, S – {i}, j) + dist(i, j) for j Є S and i ≠ j}
Return min(i) Cost (i, {1, 2, 3, …, n}, j) + d(j, i)
Triển khai bằng C/C++
Đây là cách thực hiện trong C++:
#include <bits/stdc++.h>
using namespace std;
#define V 4
#define MAX 1000000
int tsp(int graph[][V], int s)
{
vector<int> vertex;
for (int i = 0; i < V; i++)
if (i != s)
vertex.push_back(i);
int min_cost = MAX;
while(next_permutation(vertex.begin(), vertex.end()))
{
int current_cost = 0;
int j = s;
for (int i = 0; i < vertex.size(); i++) {
current_cost += graph[j][vertex[i]];
j = vertex[i];
}
current_cost += graph[j][s];
min_cost = min(min_cost, current_cost);
return min_cost;
}
}
int main()
{
int graph[][V] = { { 0, 10, 15, 20 },{ 10, 0, 35, 25 },{ 15, 35, 0, 30 },{ 20, 25, 30, 0 } };
int s = 0;
cout << tsp(graph, s) << endl;
return 0;
}
Đầu ra:
80
Triển khai tại Python
from sys import maxsize
from itertools, import permutations
V = 4
def tsp(graph, s):
vertex = []
for i in range(V):
if i != s:
vertex.append(i)
min_cost = maxsize
next_permutation=permutations(vertex)
for i in next_permutation:
current_cost = 0
k = s
for j in i:
current_cost += graph[k][j]
k = j
current_cost += graph[k][s]
min_cost = min(min_cost, current_cost)
return min_cost
graph = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
s = 0
print(tsp(graph, s))
Đầu ra:
80
Giải pháp học thuật cho TSP
Các nhà khoa học máy tính đã dành nhiều năm để tìm kiếm thuật toán thời gian đa thức cải tiến cho Bài toán Người bán hàng du lịch. Cho đến nay, bài toán này vẫn là NP-khó.
Mặc dù một số giải pháp sau đây đã được công bố trong những năm gần đây đã làm giảm độ phức tạp ở một mức độ nhất định:
- TSP đối xứng cổ điển được giải bằng Phương pháp Zero Suffix.
- Thuật toán tối ưu hóa dựa trên địa lý sinh học dựa trên chiến lược di chuyển để giải quyết các vấn đề tối ưu hóa có thể được lên kế hoạch dưới dạng TSP.
- Thuật toán tiến hóa đa mục tiêu được thiết kế để giải quyết nhiều TSP dựa trên NSGA-II.
- Hệ thống đa tác nhân giải quyết TSP của N thành phố bằng tài nguyên cố định.
Ứng dụng bài toán nhân viên du lịch
Bài toán Người bán hàng du lịch (TSP) được áp dụng trong thế giới thực ở cả dạng thuần túy nhất và dạng sửa đổi. Một số trong số đó là:
- Lập kế hoạch, hậu cần và sản xuất vi mạch: Các vấn đề về chèn chip phát sinh một cách tự nhiên trong ngành vi mạch. Những vấn đề đó có thể được lên kế hoạch như những vấn đề của người bán hàng du lịch.
- trình tự DNA: Có thể áp dụng một chút sửa đổi của bài toán người bán hàng du lịch trong giải trình tự DNA. Ở đây, các thành phố đại diện cho các đoạn DNA và khoảng cách đại diện cho thước đo độ giống nhau giữa hai đoạn DNA.
- Thiên văn học: Bài toán Người bán hàng du lịch được các nhà thiên văn áp dụng để giảm thiểu thời gian quan sát các nguồn khác nhau.
- Bài toán điều khiển tối ưu: Việc xây dựng bài toán nhân viên bán hàng du lịch có thể được áp dụng trong các bài toán điều khiển tối ưu. Có thể có một số ràng buộc khác được thêm vào.
Phân tích độ phức tạp của TSP
- Độ phức tạp về thời gian: Có tổng cộng 2N các vấn đề con cho mỗi nút. Vì vậy tổng số bài toán con sẽ là N*2N. Mỗi vấn đề phụ đòi hỏi thời gian tuyến tính để giải quyết. Nếu nút gốc không được chỉ định, chúng ta phải chạy vòng lặp cho N nút.
Vì vậy, tổng độ phức tạp thời gian cho một giải pháp tối ưu sẽ là Số lượng nút * Số lượng bài toán con * thời gian để giải quyết từng bài toán con. Độ phức tạp thời gian có thể được định nghĩa là O(N2 * 2^N).
- Không gian phức tạp: Phương pháp lập trình động sử dụng bộ nhớ để lưu trữ C(S, i), trong đó S là tập con của tập đỉnh. Có tổng cộng 2N tập con cho mỗi nút. Vì vậy, độ phức tạp của không gian là O(2^N).
Tiếp theo, bạn sẽ tìm hiểu về Sàng thuật toán Eratosthenes
