algorithm
यात्रा सेल्समैन

टिप्पणियों

जानवर बल एल्गोरिथम

प्रत्येक वर्टेक्स के माध्यम से एक रास्ता बिल्कुल वैसा ही होता है जैसे किसी तरह से वर्टेक्स को ऑर्डर करना। इस प्रकार, हर बार एक बार प्रत्येक शीर्ष के माध्यम से यात्रा करने की न्यूनतम लागत की गणना करने के लिए, हम N! हर एक को मजबूर कर सकते हैं N! 1 से N तक की संख्याओं का क्रमचय।

Psuedocode

minimum = INF
for all permutations P

    current = 0                                

    for i from 0 to N-2
        current = current + cost[P[i]][P[i+1]]  <- Add the cost of going from 1 vertex to the next
    
    current = current + cost[P[N-1]][P[0]]      <- Add the cost of going from last vertex to the first

    if current < minimum                        <- Update minimum if necessary
        minimum = current
    
output minimum

समय जटिलता

N! के माध्यम से जाने की अनुमति और प्रत्येक पथ की लागत की गणना O(N) , इस प्रकार यह एल्गोरिदम सटीक उत्तर को आउटपुट करने के लिए O(N * N!) समय लेता है।

डायनेमिक प्रोग्रामिंग एल्गोरिथम

ध्यान दें कि यदि हम पथ पर विचार करते हैं (क्रम में):

(1,2,3,4,6,0,5,7)

और पथ

(1,2,3,5,0,6,7,4) 

वर्टेक्स 1 से वर्टेक्स 2 से वर्टेक्स 3 तक जाने की लागत समान रहती है, इसलिए इसे पुनर्गणना क्यों किया जाना चाहिए? इस परिणाम को बाद में उपयोग के लिए बचाया जा सकता है।

dp[bitmask][vertex] उन सभी चक्करों के माध्यम से यात्रा करने की न्यूनतम लागत का प्रतिनिधित्व करते हैं, जिनके bitmask में संबंधित बिट्स vertex पर 1 अंत पर सेट होती हैं। उदाहरण के लिए:

dp[12][2] 

   12   =   1 1 0 0
            ^ ^ 
vertices:   3 2 1 0

चूँकि 12 बाइनरी में 1100 का प्रतिनिधित्व करता है, dp[12][2] ग्राफ 2 वर्टिक्स 2 और 3 से गुजरने का प्रतिनिधित्व करता है और शीर्ष 2 पर समाप्त होता है।

इस प्रकार हम निम्नलिखित एल्गोरिथ्म (C ++ कार्यान्वयन) कर सकते हैं:

int cost[N][N];                        //Adjust the value of N if needed
int memo[1 << N][N];                   //Set everything here to -1
int TSP(int bitmask, int pos){
    int cost = INF;
    if (bitmask == ((1 << N) - 1)){      //All vertices have been explored
        return cost[pos][0];             //Cost to go back
    }
    if (memo[bitmask][pos] != -1){       //If this has already been computed
        return memo[bitmask][pos];       //Just return the value, no need to recompute
    }
    for (int i = 0; i < N; ++i){         //For every vertex 
        if ((bitmask & (1 << i)) == 0){  //If the vertex has not been visited
            cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]);   //Visit the vertex
        } 
    }
    memo[bitmask][pos] = cost;           //Save the result
    return cost;
}
//Call TSP(1,0)

यह रेखा थोड़ी भ्रामक हो सकती है, इसलिए इसे धीरे से गुजरने दें:

cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]);

यहाँ, bitmask | (1 << i) bitmask के ith बिट को 1 पर सेट करता है, जो यह दर्शाता है कि ith वर्टेक्स का दौरा किया गया है। अल्पविराम के बाद i उस फ़ंक्शन कॉल में नए pos का प्रतिनिधित्व करता है, जो नए "अंतिम" वर्टेक्स का प्रतिनिधित्व करता है। cost[pos][i] शीर्ष स्तर pos से शीर्ष i तक यात्रा की लागत को जोड़ना है।

इस प्रकार, इस लाइन का मान अपडेट है cost हर दूसरे शिखर कि अभी तक का दौरा किया नहीं किया गया है के लिए यात्रा की न्यूनतम संभव मूल्य के लिए।

समय जटिलता

फ़ंक्शन TSP(bitmask,pos) में bitmask लिए 2^N मान और pos लिए N मान हैं। प्रत्येक फ़ंक्शन को चलाने के for O(N) समय लगता है O(N) लूप के for )। इस प्रकार यह कार्यान्वयन सटीक उत्तर को आउटपुट करने के लिए O(N^2 * 2^N) समय लेता है।