ปัญหาพ่อค้าเดินทาง (Travelling Salesman Problem - TSP)

บทนำ

พ่อค้าคนหนึ่งอยู่ในเมืองหนึ่ง เขาต้องไปเยี่ยมชมเมืองอื่นๆ ทั้งหมดที่ระบุในรายการ ต้นทุนการเดินทางจากเมืองหนึ่งไปอีกเมืองหนึ่งก็ได้รับการให้มา หาเส้นทางที่ต้นทุนต่ำที่สุดเพื่อเยี่ยมชมเมืองทั้งหมดครั้งเดียวและกลับมาที่เมืองเริ่มต้น

กราฟต้องเป็น Complete Graph สำหรับกรณีนี้ เพื่อให้พ่อค้าสามารถไปจากเมืองไหนก็ได้ไปอีกเมืองไหนก็ได้โดยตรง

ที่นี่เราต้องหา Hamiltonian Cycle ที่มีน้ำหนักต่ำสุด (Minimum Weighted Hamiltonian Cycle)

อินพุตและเอาต์พุต

Input: Cost matrix:
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
Output: Distance of Travelling Salesman: 80

อัลกอริทึม

travellingSalesman(mask, pos)
มีตาราง dp, และค่า VISIT_ALL เพื่อทำเครื่องหมายว่าทุกโหนดถูกเยี่ยมชมแล้ว

Input: mask value สำหรับ masking บางเมือง, position
Output: หาเส้นทางสั้นที่สุดเพื่อเยี่ยมชมทุกเมือง

Begin
    if mask = VISIT_ALL, then  // เมื่อเยี่ยมชมทุกเมืองแล้ว
        return cost[pos, 0]
    if dp[mask, pos] ≠ -1, then
        return dp[mask, pos]
    finalCost := ∞
    for ทุกเมือง i, do
        tempMask := (shift 1 left i times)
        if mask AND tempMask = 0, then
            tempCost := cost[pos, i] + travellingSalesman(mask OR tempMask, i)
            finalCost := minimum ของ finalCost และ tempCost
    done
    dp[mask, pos] = finalCost
    return finalCost
End

ตัวอย่างโค้ด (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];  // สร้างอาเรย์ขนาด (2^n, n)

int travellingSalesman(int mask, int pos) {
    if (mask == VISIT_ALL)  // เมื่อทุกเมืองถูกทำเครื่องหมายว่าเยี่ยมชมแล้ว
        return cost[pos][0];  // จากเมืองปัจจุบันกลับสู่ต้นทาง
    if (dp[mask][pos] != -1)  // เมื่อถูกพิจารณาแล้ว
        return dp[mask][pos];
    int finalCost = INF;
    for (int i = 0; i < CITY; i++) {
        if ((mask & (1 << i)) == 0) {  // ถ้าบิตที่ i ของผลลัพธ์เป็น 0 แสดงว่ายังไม่ได้เยี่ยมชม
            int tempCost = cost[pos][i] + travellingSalesman(mask | (1 << i), i);  // เนื่องจากเมือง i ถูกเยี่ยมชม
            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;  // initialize dp array เป็น -1
    cout << "Distance of Travelling Salesman: ";
    cout << travellingSalesman(1, 0);  // เริ่มต้น mask คือ 0001, เพราะเมือง 0 ถูกเยี่ยมชมแล้ว
}

ผลลัพธ์

Distance of Travelling Salesman: 80