हेल्ड और कार्प एल्गोरिदम

Question

के साथ ट्रैवलिंग सेल्समैन मैं यात्रा विक्रेता की समस्या के डीपी समाधान से अच्छी तरह से अवगत हूं; टीएसपी के लिए हेल्ड और कार्प एल्गोरिदम के रूप में भी जाना जाता है।

मैं bitmask के साथ लागू किया है, और यह कुछ इस तरह है:

int TSP(int pos, int bitmask) { 
    if (bitmask == (1<<(K+1))-1) 
     return dist[pos][0];    // Completing the round trip 

    if (memo[pos][bitmask] != -1) 
     return memo[pos][bitmask]; 

    int answer = INF; 
    for (int i = 0; i <= K; i++) { 
     if (i != pos && (bitmask & (1 << i)) == 0) 
      answer = Math.min(answer, dist[pos][i] + TSP(i, bitmask | (1 << i))); 
    } 

    return memo[pos][bitmask] = answer;  // Storing the best dist for the set of traveled cities and untraveled ones. 

}

इस एल्गोरिथ्म काफी तेज है; 15 शहरों की गणना अपेक्षाकृत तेज़ है। हालांकि, मुझे लगता है कि लगभग 20 शहरों को समायोजित करने के लिए इसे और बेहतर किया जा सकता है।

1) यदि डिस्ट मैट्रिक्स सममित है, तो शायद हम बार-बार गणनाओं को रोकने के लिए इस संपत्ति का उपयोग कर सकते हैं। (उदाहरण के लिए ए-> बी-> सी-> डी-> ए == ए-> डी-> सी-> बी-> ए)

2) ऊपरी और निचले बाउंड दोनों का उपयोग करने के लिए। उपर्युक्त एल्गोरिदम बहुत ही कम समय में अपना पहला संभावित इष्टतम समाधान प्राप्त करने में सक्षम है, इसका उपयोग करने में सक्षम हो सकता है।

मैंने उपर्युक्त दो सिद्धांतों के आधार पर एल्गोरिदम सुधारने की कोशिश की है। हालांकि, मुझे एक बेहतर एल्गोरिदम नहीं मिलता है।

क्या मैं कुछ असंभव सुधारने के लिए एक व्यर्थ प्रयास कर रहा हूं? तुम क्या सोचते हो?

Answer 1

मुझे लगता है कि आप सही हैं। आपकी विधि के तहत, अधिकतम संख्या में शहर 20,21 या 22 हो सकते हैं, लेकिन 25 भी नहीं हो सकते हैं। ऐसा इसलिए है क्योंकि आपके एल्गोरिदम में स्थिति की संख्या n * (2^n) है, जब n = 20, यह लगभग 10 है^7, जब एन = 25, यह लगभग 10^9 है, जो एक बहुत बड़ी संख्या है। आधुनिक कंप्यूटर के साथ, यह 1 सेकंड के भीतर लगभग 10^7 गणना संसाधित कर सकता है। लेकिन 10^9 गणना को संसाधित करने में लगभग 100 सेकंड लगेंगे।

तो मुझे लगता है कि अगर अधिक शहरों को संभालना चाहते हैं, तो कुछ अनुमानित एल्गोरिदम उपयोगी हो सकते हैं, जैसे नकली एनीलिंग एल्गोरिदम, जेनेटिक एल्गोरिदम, आदि या आप कई मशीनों का उपयोग कर सकते हैं और समस्या को कम कर सकते हैं।