चक्रीय ग्राफ

Question

में सबसे लंबी पथ समस्या के लिए अनुकूलन चक्रीय ग्राफ में सबसे लंबा रास्ता खोजने की कोशिश करने के लिए कौन से अनुकूलन मौजूद हैं?

चक्रीय ग्राफ में सबसे लंबा रास्ता एनपी-पूर्ण माना जाता है। क्या ऑप्टिमाइज़ेशन या हेरिस्टिक्स पूरे ग्राफ को डीएफएसिंग से सबसे लंबा रास्ता तेज कर सकता है? क्या कोई संभाव्य दृष्टिकोण है?

मेरे पास विशिष्ट गुणों वाला ग्राफ है, लेकिन मैं सामान्य मामले में इसका उत्तर ढूंढ रहा हूं। कागजात से जुड़ा होना शानदार होगा। यहां आंशिक उत्तर दिया गया है:

1. पुष्टि करें कि यह चक्रीय है। गतिशील प्रोग्रामिंग का उपयोग करके विश्वकोश ग्राफ में सबसे लंबा रास्ता आसानी से गणना की जाती है।

2. पता लगाएं कि ग्राफ प्लानर है (कौन सा एल्गोरिदम सर्वोत्तम है?)। यदि ऐसा है, तो आप देख सकते हैं कि यह एक ब्लॉक ग्राफ, टॉलेमेमिक ग्राफ, या कैक्टि ग्राफ है और this paper में पाए गए तरीकों को लागू करें।

3. पता लगाएं कि Donald B Johnson's algorithm (Java implementation) का उपयोग करके कितने सरल चक्र हैं। आप एक सरल चक्र में किनारे को हटाकर किसी भी चक्रीय ग्राफ को एक विश्वकोश में बदल सकते हैं। फिर आप the Wikipedia page पर पाए गए गतिशील प्रोग्रामिंग समाधान को चला सकते हैं। पूर्णता के लिए, आपको प्रत्येक चक्र के लिए यह एन बार करना होगा, जहां एन चक्र की लंबाई है। इस प्रकार, पूरे ग्राफ के लिए, आपको डीपी समाधान चलाने के लिए कितनी बार सभी चक्रों की लंबाई के उत्पाद के बराबर है।

4. यदि आपको पूरे ग्राफ को डीएफएस करना है, तो आप प्रत्येक नोड की "पहुंच क्षमता" की गणना करके कुछ पथों को पूर्ववत कर सकते हैं। यह पहुंच क्षमता, जो मुख्य रूप से निर्देशित ग्राफ पर लागू होती है, नोड्स की संख्या प्रत्येक नोड पुनरावृत्ति के बिना पहुंच सकती है। यह संभवतः उस नोड से सबसे लंबा रास्ता हो सकता है। इस जानकारी के साथ, यदि आपका वर्तमान पथ प्लस नोड की पहुंचने योग्यता सबसे लंबे समय से कम है, तो उस शाखा को लेने में कोई बात नहीं है क्योंकि यह असंभव है कि आपको लंबा रास्ता मिल जाएगा।

Answer 1

यहाँ एक O (n * 2^n) गतिशील प्रोग्रामिंग दृष्टिकोण है कि संभव 20 कोने कहने के लिए होना चाहिए:

m(b, U) = b में समाप्त होने और केवल पर जाकर किसी भी पथ की अधिकतम लंबाई (कुछ) U में शिखर।

प्रारंभ में, m(b, {b}) = 0 सेट करें।

फिर, m(b, U) = अधिकतम U ऐसी है कि x में सभी x से अधिक m(x, U - x) + d(x, b) का मूल्य b और एक बढ़त (x, b) मौजूद नहीं है। U = V (शीर्षकों का पूरा सेट) के साथ, इन सभी मानों को अधिकतम अंतराल b के लिए लें। यह किसी भी पथ की अधिकतम लंबाई होगी।

निम्नलिखित सी कोड d[N][N] में दूरी मैट्रिक्स मानता है। यदि आपका ग्राफ़ असीमित है, तो आप इस सरणी में निरंतर 1 पर प्रत्येक पढ़ने की पहुंच को बदल सकते हैं। एक ट्रेसबैक जो अक्षरों का इष्टतम अनुक्रम दिखाता है (एक से अधिक हो सकता है) सरणी p[N][NBITS] में भी गणना की जाती है।

#define N 20 
#define NBITS (1 << N) 

int d[N][N];  /* Assumed to be populated earlier. -1 means "no edge". */ 
int m[N][NBITS]; /* DP matrix. -2 means "unknown". */ 
int p[N][NBITS]; /* DP predecessor traceback matrix. */ 

/* Maximum distance for a path ending at vertex b, visiting only 
    vertices in visited. */ 
int subsolve(int b, unsigned visited) { 
    if (visited == (1 << b)) { 
     /* A single vertex */ 
     p[b][visited] = -1; 
     return 0; 
    } 

    if (m[b][visited] == -2) { 
     /* Haven't solved this subproblem yet */ 
     int best = -1, bestPred = -1; 
     unsigned i; 
     for (i = 0; i < N; ++i) { 
      if (i != b && ((visited >> i) & 1) && d[i][b] != -1) { 
       int x = subsolve(i, visited & ~(1 << b)); 
       if (x != -1) { 
        x += d[i][b]; 
        if (x > best) { 
         best = x; 
         bestPred = i; 
        } 
       } 
      } 
     } 

     m[b][visited] = best; 
     p[b][visited] = bestPred; 
    } 

    return m[b][visited]; 
} 

/* Maximum path length for d[][]. 
    n must be <= N. 
    *last will contain the last vertex in the path; use p[][] to trace back. */ 
int solve(int n, int *last) { 
    int b, i; 
    int best = -1; 

    /* Need to blank the DP and predecessor matrices */ 
    for (b = 0; b < N; ++b) { 
     for (i = 0; i < NBITS; ++i) { 
      m[b][i] = -2; 
      p[b][i] = -2; 
     } 
    } 

    for (b = 0; b < n; ++b) { 
     int x = subsolve(b, (1 << n) - 1); 
     if (x > best) { 
      best = x; 
      *last = b; 
     } 
    } 

    return best; 
} 

मेरे पीसी पर, इस बढ़त वजन बेतरतीब ढंग से 7s बारे में में रेंज [0, 1000) चुना के साथ एक 20x20 पूरा ग्राफ को हल करती है और (उसमें से आधे पूर्ववर्ती पता लगाने के लिए है) 160MB के बारे में की जरूरत है।