2 डी सरणी में Belman-फोर्ड एल्गोरिथ्म

Question

मैं 2 डी सरणी के लिए एक Bellman- फोर्ड एल्गोरिथ्म को लागू करने के साथ एक समस्या मिल गया है (ग्राफ़ बनाने के लिए नहीं)

इनपुट सरणी मीटर एक्स n आयाम:

  s[1,1] s[1,2] ... s[1,n] -> Exit 
      s[2,1] s[2,2] ... s[2,n] 
      ... 
Entry -> s[m,1] s[m,2] ... s[m,n] 

और यह कमरे के समान है (प्रत्येक प्रविष्टि एस [x, y] प्रवेश की लागत) है। प्रत्येक कमरे में नकारात्मक लागत हो सकती है, और हमें से सबसे सस्ता पथ ढूंढना होगा कमरे चुनने के लिए प्रवेश करें और से बाहर निकलें।

उदाहरण के लिए, हम कमरे और लागत के इस सरणी मिल गया है:

1 5 6 
2 -3 4 
5 2 -8 

और हम कमरे पर चलने के लिए चाहते हैं [3,2], रों [3,2] = 4। हम प्रपत्र [1,3] पर शुरू कर रहे हैं और अधिक [3,2] चलना इससे पहले कि हम करने के लिए [3,3] जाना चाहिए।

और मेरा सवाल यह है कि बेलमैन-फोर्ड एल्गोरिदम में इसे लागू करने का सबसे अच्छा तरीका क्या है? मुझे पता है कि डिजस्ट्री एल्गोरिदम नकारात्मक लागत के कारण काम नहीं करेगा।

प्रत्येक कमरे के लिए [0, maxHeight] से है और सभी पड़ोसियों को सही आराम से? इस तरह:

for (int i = height-1; i >= 0; --i) { 
     for (int j = 0; j < width; ++j) { 
      int x = i; 
      int y = j; 
      if (x > 0) // up 
       Relax(x, y, x - 1, y); 
      if (y + 1 < width) // right 
       Relax(x, y, x, y + 1); 
      if (y > 0) // left 
       Relax(x, y, x, y - 1); 
      if (x + 1 < height) // down 
       Relax(x, y, x + 1, y); 
     } 
    } 

लेकिन फिर मैं कमरे को चुनने और कमरे से बाहर निकलने के लिए लागत कैसे पढ़ सकता हूं?

Answer 1

यदि आप जानते हैं कि किसी सरणी से ग्राफ़ को कैसे स्थानांतरित किया जाए, तो आप अतिरिक्त शर्त पैराग्राफ पर स्क्रॉल कर सकते हैं। अगले अनुच्छेद भी पढ़ें।

वास्तव में, आप उस इमारत को ग्राफ पर देख सकते हैं।

आप देख सकते हैं की तरह: (, मैं दूसरी पंक्ति में दरवाजे भूल गया क्षमा करें।)

तो, यह कैसे संभव है को लागू किया जाना है। पल अतिरिक्त स्थिति के लिए अनदेखा करें (जाने से पहले एक विशेष कशेरुका पर जाएं)।
वजन समारोह:
S[][] प्रवेश लागत की एक सरणी बनें। ध्यान दें, कि किनारे के वजन के बारे में अंत में केवल vertex का फैसला करता है। इससे कोई फर्क नहीं पड़ता कि यह (1, 2) -> (1,3) या (2,3) -> (1, 3) है। लागत दूसरे चरम द्वारा परिभाषित किया गया है।

cost_type cost(vertex v, vertex w) { 
    return S[w.y][w.x]; 
} 
//As you can see, first argument is unnecessary. 

किनारों:
वास्तव में आप कुछ सरणी में सभी किनारों रखने के लिए की जरूरत नहीं है तो समारोह की तरह लग सकता है। जब भी आपको आवश्यकता हो, आप उन्हें फ़ंक्शन में गणना कर सकते हैं। vertex (x, y) के लिए पड़ोसियों (x+1, y), (x-1, y), (x, y+1), (x, y-1), यदि उस नोड मौजूद हैं। आपको इसे जांचना है, लेकिन यह आसान है। (जांचें कि new_x> 0 & & new_x < max_x।) ऐसा नहीं है कि की तरह लग रहे हो सकता है:

//Size of matrix is M x N 
is_correct(vertex w) { 
    if(w.y < 1 || w.y > M || w.x < 1 || w.x > N) { 
     return INCORRECT; 
    } 
    return CORRECT; 
} 

जनरेट कर रहा है पड़ोसियों की तरह देख सकते हैं:

std::tie(x, y) = std::make_tuple(v.x, v.y); 
for(vertex w : {{x+1, y}, {x-1, y}, {x, y+1}, {x, y-1}}) { 
    if(is_correct(w) == CORRECT) {//CORRECT may be true 
     relax(v, w); 
    } 
} 

मेरा मानना ​​है कि यह है कि यह चार किनारों के लिए अतिरिक्त स्मृति नहीं लेना चाहिए। यदि आप std::tie नहीं जानते हैं, तो cppreference देखें। जाहिर है (अतिरिक्त चर x, y अधिक स्मृति ले, लेकिन मुझे विश्वास है कि इसे यहाँ अधिक पठनीय है। अपने कोड में यह दिखाई न दें।)

आप दूरी के साथ अन्य 2 डी सरणी और (यदि आवश्यक हो) पूर्ववर्ती के लिए है, लेकिन मुझे लगता है कि यह स्पष्ट है और मुझे इसका वर्णन करने की ज़रूरत नहीं है।

अतिरिक्त शर्त:
आप जानना चाहते हैं बाहर निकलने के लिए प्रवेश से लागत चाहते हैं, लेकिन आप कुछ शीर्ष compulsory यात्रा करने के लिए की है। इसकी गणना करने का सबसे आसान तरीका enter से compulsory और compulsory से exit तक की गणना करना है। (दो अलग-अलग गणना होगी।) यह big O समय नहीं बदलेगा। इसके बाद आप केवल परिणाम जोड़ सकते हैं।

आपको सिर्फ यह गारंटी देना है कि compulsory से पहले जाना असंभव है। यह आसान है, आप is_correct फ़ंक्शन में अतिरिक्त पंक्ति जोड़कर exit से आउटगोइंग किनारों को मिटा सकते हैं, (फिर vertex v आवश्यक होगा।) या पड़ोसी कोड खंड उत्पन्न करने में।

अब आप इसे basing on wikipedia लागू कर सकते हैं। आपके पास ग्राफ है

आपको क्यों नहीं सुनना चाहिए?
अन्य चरम से बेलमैन फोर्ड एल्गोरिदम का उपयोग करने का बेहतर तरीका है। ध्यान दें, कि यदि आप ए से बी के इष्टतम पथ को जानते हैं, तो आप बी से ए के इष्टतम पथ को भी जानते हैं क्यों? हमेशा आपको अंतिम कशेरुक के लिए भुगतान करना होगा और आप पहले भुगतान नहीं करते हैं, इसलिए आप उनकी लागतों को अनदेखा कर सकते हैं। बाकी स्पष्ट है।
अब, यदि आप जानते हैं कि आप पथ ए-> बी और बी-> सी जानना चाहते हैं, तो आप बी-> ए और बी-> सी की गणना एनओडी बी से एक बार बीएफ और रिवर्स पथ बी-> ए से कर सकते हैं। खत्म हो गया।
आपको entry और exit नोड्स से आउटगोइंग किनारों को मिटाना होगा।

हालांकि, अगर आपको बहुत तेज एल्गोरिदम की आवश्यकता है, तो आपको इसे अनुकूलित करना होगा। लेकिन यह एक और विषय के लिए है, मुझे लगता है। साथ ही, ऐसा लगता है कि कोई भी हार्ड ऑप्टिमाइज़ेशन में रुचि नहीं रखता है।
मैं जल्दी से उस छोटे और आसान अनुकूलन अड्डों को जोड़ सकता हूं, कि आप संगत दूर-दूर के शिखर से छूट को अनदेखा कर सकते हैं। सरणी में आप आसानी से दूरी की गणना कर सकते हैं, इसलिए यह सुखद अनुकूलन है।
मैंने अच्छी तरह से अनुकूलन का उल्लेख नहीं किया है, क्योंकि मेरा मानना ​​है कि वे सभी वेब के यादृच्छिक पाठ्यक्रम में हैं।