ट्रैवलिंग सेल्समैन समस्या

परिचय

एक विक्रेता एक शहर में है, उसे उन सभी अन्य शहरों का दौरा करना है जो सूचीबद्ध हैं, एक शहर से दूसरे शहर की यात्रा की लागत भी प्रदान की गई है। वह मार्ग ढूंढें जहां लागत न्यूनतम हो ताकि सभी शहरों का एक बार दौरा किया जा सके और अपने प्रारंभिक शहर वापस आया जा सके।

ग्राफ इस मामले के लिए पूर्ण होना चाहिए, ताकि विक्रेता किसी भी शहर से किसी भी शहर में सीधे जा सके।

यहां हमें न्यूनतम भारित हैमिल्टनियन चक्र ढूंढना है।

इनपुट और आउटपुट

इनपुट: मैट्रिक्स की लागत मैट्रिक्स।
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
आउटपुट: ट्रैवलिंग सेल्समैन की दूरी: 80

एल्गोरिदम

travellingSalesman(mask, pos)
एक तालिका dp है, और VISIT_ALL मान सभी नोड्स के विज़िट किए जाने को चिह्नित करने के लिए

इनपुट: कुछ शहरों को मास्क करने के लिए मास्क मान, स्थिति।
आउटपुट: सभी शहरों का दौरा करने के लिए सबसे छोटा मार्ग ढूंढें।

Begin
    यदि mask = VISIT_ALL, तो // जब सभी शहर विज़िट हो चुके हों
        cost[pos, 0] लौटाएं
    यदि dp[mask, pos] ≠ -1, तो
        dp[mask, pos] लौटाएं
    finalCost := ∞
    सभी शहरों i के लिए, करें
        tempMask := (1 को बाएं i बार शिफ्ट करें)
        यदि mask AND tempMask = 0, तो
            tempCost := cost[pos, i] +
            travellingSalesman(mask OR tempMask, i)
            finalCost := finalCost और tempCost का न्यूनतम
    done
    dp[mask, pos] = finalCost
    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; // dp सरणी को -1 से आरंभ करें
    cout << "Distance of Travelling Salesman: ";
    cout << travellingSalesman(1, 0); // प्रारंभ में मास्क 0001 है, क्योंकि 0वां शहर पहले से विज़िटेड है
}

आउटपुट

Distance of Travelling Salesman: 80