Bài toán Người bán hàng du lịch (Travelling Salesman Problem)

Giới thiệu

Một người bán hàng ở một thành phố, anh ta phải ghé thăm tất cả các thành phố khác được liệt kê, chi phí di chuyển từ thành phố này đến thành phố khác cũng được cung cấp. Tìm lộ trình chi phí tối thiểu để ghé thăm tất cả các thành phố một lần và quay lại thành phố xuất phát.

Đồ thị phải là đồ thị hoàn chỉnh (complete graph) cho trường hợp này, để người bán hàng có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào trực tiếp.

Ở đây ta phải tìm Chu trình Hamilton (Hamiltonian Cycle) có trọng số tối thiểu.

Đầu vào và Đầu ra

Đầu vào: Ma trận chi phí.
0 20 42 25 30
20 0 30 34 15
42 30 0 10 10
25 34 10 0 25
30 15 10 25 0
Đầu ra: Khoảng cách Người bán hàng du lịch: 80

Thuật toán

travellingSalesman(mask, pos)
Có một bảng dp, và giá trị VISIT_ALL để đánh dấu tất cả nút đã được thăm

Đầu vào: Giá trị mask để che một số thành phố, vị trí.
Đầu ra: Tìm lộ trình ngắn nhất để thăm tất cả các thành phố.

Begin
    if mask = VISIT_ALL, then // khi tất cả thành phố đã được thăm
        return cost[pos, 0]
    if dp[mask, pos] ≠ -1, then
        return dp[mask, pos]
    finalCost := ∞
    for all cities i, do
        tempMask := (dịch 1 trái i lần)
        if mask AND tempMask = 0, then
            tempCost := cost[pos, i] + travellingSalesman(mask OR tempMask, i)
            finalCost := minimum of finalCost and tempCost
    done
    dp[mask, pos] = finalCost
    return finalCost
End

Ví dụ (C++)

#include <iostream>
#define CITY 5
#define INF 9999
using namespace std;

int cost[CITY][CITY] = {
    {0, 20, 42, 25, 30},
    {20, 0, 30, 34, 15},
    {42, 30, 0, 10, 10},
    {25, 34, 10, 0, 25},
    {30, 15, 10, 25, 0}
};

int VISIT_ALL = (1 << CITY) - 1;
int dp[16][4];  // mảng kích thước (2^n, n)

int travellingSalesman(int mask, int pos) {
    if(mask == VISIT_ALL)  // khi tất cả thành phố đã được đánh dấu thăm
        return cost[pos][0];  // từ thành phố hiện tại về gốc
    if(dp[mask][pos] != -1)  // khi đã được xem xét
        return dp[mask][pos];
    int finalCost = INF;
    for(int i = 0; i < CITY; i++) {
        if((mask & (1 << i)) == 0) {  // nếu bit i của kết quả là 0, thì chưa thăm
            int tempCost = cost[pos][i] + travellingSalesman(mask | (1 << i), i);  // vì thành phố i đã được thăm
            finalCost = min(finalCost, tempCost);
        }
    }
    return dp[mask][pos] = finalCost;
}

int main() {
    int row = (1 << CITY), col = CITY;
    for(int i = 0; i < row; i++)
        for(int j = 0; j < col; j++)
            dp[i][j] = -1;  // khởi tạo mảng dp bằng -1
    cout << "Distance of Travelling Salesman: "; cout << travellingSalesman(1, 0);  // ban đầu mask là 0001, vì thành phố 0 đã thăm
}

Kết quả

Distance of Travelling Salesman: 80