Vấn đề nhân viên bán hàng đi du lịch: Python, C++ Thuật toán

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ối ưu tổ hợp kinh điển trong khoa học máy tính lý thuyết. Cho một đồ thị các thành phố, TSP yêu cầu tìm đường đi ngắn nhất đi qua mọi nút đúng một lần và quay trở lại thành phố xuất phát.

Đề bài cung cấp một danh sách các thành phố cùng với khoảng cách giữa mỗi cặp thành phố.

Mục tiêu: Bắt đầu từ thành phố xuất phát, ghé thăm mỗi thành phố khác đúng một lần, rồi quay trở lại thành phố xuất phát. Mục tiêu là tìm ra tuyến đường khứ hồi ngắn nhất có thể.

Ví dụ về TSP

Hãy xem đồ thị bên dưới, trong đó 1, 2, 3 và 4 đại diện cho các thành phố, và trọng số trê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 lộ trình ngắn nhất có thể, bắt đầu từ thành phố xuất phát, ghé thăm mỗi thành phố khác đúng một lần và quay trở lại thành phố xuất phát.

Với đồ thị ở trên, tuyến đường tối ưu là 1-2-4-3-1Chi phí cho chuyến đi ngắn nhất là 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 rong được xếp vào loại NP-khó vì không có thuật toán nào giải được nó chính xác trong thời gian đa thức. Độ phức tạp tăng theo cấp số mũ với số lượng thành phố.

Có nhiều cách để tấn công TSP. Các phương pháp phổ biến nhất là:

Phương pháp vét cạn: Phương pháp đơn giản tính toán mọi lộ trình có thể và so sánh chúng. Số lượng lộ trình trong một đồ thị có n thành phố là n!Điều này khiến việc sử dụng phương pháp vét cạn trở nên rất tốn kém về mặt tính toán đối với bất kỳ quy mô nào vượt quá khoảng mười thành phố.

Phương pháp nhánh và cận: Bài toán được chia thành các bài toán con, và các giải pháp của những bài toán con đó được kết hợp lại thành một giải pháp tối ưu. Việc cắt tỉa hiệu quả sẽ loại bỏ các lộ trình một phần không thể vượt qua chi phí tốt nhất hiện tại.

Bài hướng dẫn này trình bày cách tiếp cận lập trình động, đây là phiên bản ghi nhớ của thuật toán nhánh và cận, tương ứng với thuật toán Bellman-Held-Karp.

Lập trình năng động: Đây là một phương pháp chính xác nhằm tìm kiếm giải pháp tối ưu bằng cách tái sử dụng sự chồng chéo.ping kết quả của bài toán con. Nó chậm hơn so với phương pháp gần tối ưu. phương pháp tham lamnhưng nó luôn trả về một lộ trình tối ưu toàn cục.

Độ phức tạp tính toán của phương pháp này là O(N² × 2^N)mà chúng ta sẽ thảo luận chi tiết hơn ở phần sau của bài viết.

Phương pháp lân cận gần nhất: Một phương pháp tham lam dựa trên kinh nghiệm luôn nhảy đến thành phố chưa được ghé thăm gần nhất. Phương pháp này rẻ hơn nhiều so với lập trình động nhưng không đảm bảo lộ trình tối ưu, vì vậy nó được sử dụng cho các giải pháp gần tối ưu khi tốc độ quan trọng hơn việc tìm giá trị cực tiểu chính xác.

Thuật toán giải bài toán nhân viên bán hàng du lịch

Chúng tôi sử dụng phương pháp lập trình động để giải quyết bài toán TSP. Trước khi bắt đầu thuật toán, hãy cùng làm rõ một vài thuật ngữ:

• Một đồ thị G = (V, E) là một 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) ký hiệu này biểu thị khoảng cách không âm giữa các đỉnh i và j.

Giả sử S là một tập con các thành phố được chọn từ tập hợp {1, 2, 3, …, n}, trong đó i và j là hai thành phố thuộc tập con đó. Khi đó, cost(i, S, j) là độ dài của con đường ngắn nhất bắt đầu từ i, đi qua mọi thành phố trong S đúng một lần và kết thúc tại j.

Ví dụ, cost(1, {2, 3, 4}, 1) ký hiệu này biểu thị con đường 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

Công thức truy hồi trong quy hoạch động là:

• Thiết lập cost(i, {}, i) = 0Điều này có nghĩa là chúng ta bắt đầu và kết thúc tại điểm i với chi phí bằng không.
• Thời Gian |S| > 1, định nghĩa cost(i, S, 1) = ∞ cho i ≠ 1Vì chi phí thực tế của chuyến đi vẫn chưa được xác định.
• Bắt đầu từ thành phố 1, hãy chọn thành phố tiếp theo sao cho... cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] cho i ∈ S và i ≠ j.

Đối với đồ thị trên, ma trận kề có dạng như sau:

Thuật toán hoạt động như sau:

Bước 1) Hành trình bắt đầu từ thành phố 1, ghé thăm mỗi thành phố khác một lần, và quay trở lại thành phố 1.

Bước 2) S là một tập con của các thành phố. Với mọi |S| > 1, hãy khởi tạo cost(i, S, 1) = ∞. Đây cost(i, S, j) Ký hiệu này biểu thị một hành trình bắt đầu từ i, đi qua các thành phố trong tập S một lần và đến j. Chúng ta bắt đầu từ vô cực vì khoảng cách chưa được biết tại thời điểm này. Vì vậy, các giá trị là:

cost(2, {3, 4}, 1) = ∞ Điều đó có nghĩa là chúng ta bắt đầu từ thành phố 2, đi qua thành phố 3 và 4, rồi đến thành phố 1, với chi phí chưa xác định. Tương tự như vậy:

cost(3, {2, 4}, 1) = ∞

cost(4, {2, 3}, 1) = ∞

Bước 3) Với mỗi tập con của S, hãy tính toán:

cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ], Nơi j ∈ S và i ≠ j.

Đó là hành trình có chi phí tối thiểu bắt đầu từ i, ghé thăm tập hợp con các thành phố một lần và quay trở lại j. Vì hành trình bắt đầu từ thành phố 1, nên chi phí tối ưu là cost(1, {other cities}, 1).

Xử lý sự lặp lại từng bước một

Bây giờ S = {1, 2, 3, 4}. Có bốn phần tử, vì vậy số tập con là 2^4 = 16Các tập con đó là:

1) |S| = 0: {Φ}

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}}

Vì hành trình bắt đầu từ thành phố 1, chúng ta có thể loại bỏ mọi tập hợp con chứa thành phố 1 khi tính toán chi phí trung gian.

Quá trình tính toán thuật toán diễn ra như sau:

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) = min [ khoảng cách(2, 3) + chi phí(3, {4}, 1) = 35 + 50 = 85, khoảng cách(2, 4) + chi phí(4, {3}, 1) = 25 + 45 = 70 ] = 70
• chi phí(3, {2, 4}, 1) = min [ khoảng cách(3, 2) + chi phí(2, {4}, 1) = 35 + 45 = 80, khoảng cách(3, 4) + chi phí(4, {2}, 1) = 30 + 35 = 65 ] = 65
• chi phí(4, {2, 3}, 1) = min [ khoảng cách(4, 2) + chi phí(2, {3}, 1) = 25 + 50 = 75, khoảng cách(4, 3) + chi phí(3, {2}, 1) = 30 + 45 = 75 ] = 75

4) |S| = 3:

• chi phí(1, {2, 3, 4}, 1) = min [ khoảng cách(1, 2) + chi phí(2, {3, 4}, 1) = 10 + 70 = 80, khoảng cách(1, 3) + chi phí(3, {2, 4}, 1) = 15 + 65 = 80, khoảng cách(1, 4) + chi phí(4, {2, 3}, 1) = 20 + 75 = 95 ] = 80

Vậy giải pháp tối ưu 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 in S and i != 1
        Cost (i, S, j) = min {Cost (i, S - {i}, j) + dist(i, j) for j in 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à phần triển khai trong C++Phiên bản bên dưới khắc phục lỗi khởi tạo sớm của mã nguồn. return Lỗi này xuất hiện trở lại sau hoán vị đầu tiên thay vì liệt kê tất cả các hành trình.

#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;
    do {
        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);
    } while (next_permutation(vertex.begin(), vertex.end()));

    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

Python việc triển khai phản ánh C++ Phiên bản này sửa lỗi của nguồn. from itertools, import lỗi dấu phẩy, đặt sai vị trí return bên trong vòng lặp bên trong và vết lõm lạc lõng trên s = 0.

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
    for perm in permutations(vertex):
        current_cost = 0
        k = s
        for j in perm:
            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 hàng thập kỷ để tìm kiếm các thuật toán cải tiến có thời gian thực hiện đa thức cho bài toán người bán hàng du lịch (Traveling Salesman Problem - TSP). Cho đến nay, TSP vẫn là bài toán NP-khó.

Một số kỹ thuật đã được công bố giúp giảm độ phức tạp thực tế đối với các nhóm bài toán TSP cụ thể:

• Bài toán TSP đối xứng cổ điển được giải quyết bằng cách... Phương pháp hậu tố số không.
• Thuật toán tối ưu hóa dựa trên địa lý sinh học Sử dụng các chiến lược di chuyển để giải quyết các bài toán tối ưu hóa tương ứng với bài toán người bán hàng du lịch (TSP).
• Thuật toán tiến hóa đa mục tiêu Được thiết kế cho bài toán TSP đa mục tiêu và dựa trên thuật toán NSGA-II.
• Hệ thống đa tác nhân Phương pháp này giải quyết bài toán TSP cho N thành phố với nguồn tài nguyên tính toán cố định.
• phương pháp heuristic Lin-Kernighan và người kế vị của nó LKH Cung cấp các tour du lịch với độ chính xác trong vòng 2-3% so với mức tối ưu, ví dụ như đối với các thành phố có hàng triệu dân.
• Hòa thuận Sử dụng mặt phẳng cắt và phương pháp nhánh-cắt để tính toán các giá trị tối ưu chính xác cho các trường hợp chuẩn với hàng chục nghìn thành phố.

Ứng dụng bài toán nhân viên du lịch

Bài toán người bán hàng rong xuất hiện trong thế giới thực dưới cả dạng thuần túy và dạng biến thể. Một số ứng dụng chính là:

• Lập kế hoạch, hậu cần và sản xuất vi mạch: Các bài toán lắp chip trong ngành công nghiệp vi mạch được mô phỏng dưới dạng các biến thể của TSP nhằm giảm thiểu thời gian di chuyển của cánh tay robot.
• Xét nghiệm DNA: Một thuật toán TSP cải tiến được sử dụng trong giải trình tự DNA, trong đó các thành phố đại diện cho các đoạn DNA và khoảng cách đại diện cho sự tương đồng giữa các đoạn.
• Thiên văn học: Các nhà thiên văn học sử dụng TSP để giảm thiểu thời gian xoay kính viễn vọng giữa các mục tiêu quan sát.
• Điều khiển tối ưu: Các mô hình TSP mô phỏng các bài toán điều khiển tối ưu, trong đó nhiều ràng buộc phải được tuân thủ đồng thời giảm thiểu chi phí di chuyển.
• Giao hàng chặng cuối: AmazonCác ứng dụng như UPS và giao đồ ăn giải quyết các biến thể TSP động để sắp xếp thứ tự các điểm dừng cho tài xế.
• Lấy hàng trong kho: Robot và người vận chuyển hàng hóa di chuyển theo các tuyến đường được tối ưu hóa bằng thuật toán TSP, giúp rút ngắn thời gian di chuyển bên trong các trung tâm phân phối.

Phân tích độ phức tạp của TSP

• Độ phức tạp về thời gian: Phương pháp lập trình động Held-Karp giải quyết 2^N các tập con cho mỗi nút bắt đầu, cung cấp N × 2^N các bài toán con. Mỗi bài toán con mất thời gian tuyến tính để kết hợp. Nếu nút gốc không được chỉ định, cần một vòng lặp ngoài qua N nút. Độ phức tạp thời gian tổng cộng là O(N² × 2^N).
• Không gian phức tạp: Bảng DP lưu trữ C(S, i) đối với mỗi tập con S của tập đỉnh. Có 2^N các tập con trên mỗi nút, do đó độ phức tạp về không gian là O(N × 2^N), thường được viết là O(2^N) khi N được coi là cố định.

Tiếp theo, tìm hiểu về Sàng thuật toán Eratosthenes.

Câu Hỏi Thường Gặp