नोड ग्राफ़ में यादृच्छिक पथ के लिए तेज़ और स्थिर एल्गोरिदम क्या है?

Question

मेरे पास एक ग्राफ है जिसमें नोड्स शामिल हैं और मुझे एक तेज़ एल्गोरिदम की आवश्यकता है जो दो नोड्स के बीच एक यादृच्छिक पथ उत्पन्न करता है। मैंने इसके लिए स्क्रैच से कई एल्गोरिदम तैयार किए हैं लेकिन यह सही नहीं लग रहा है।

या तो एल्गोरिदम लूप में फंस जाता है, या जब मैं देखे गए नोड्स का रिकॉर्ड रखता हूं तो कभी-कभी विज़िट नोड्स के बीच फंस जाता है। एक और समस्या का सामना करना पड़ा यह है कि मेरा एल्गोरिदम प्रदर्शन में बहुत अस्थिर था।

तो मेरा सवाल है; क्या किसी को अप्रत्यक्ष ग्राफ में दो पहुंचने योग्य नोड्स के बीच यादृच्छिक पथ के लिए तेज़ और स्थिर एल्गोरिदम पता है?

Answer 1

अपने ग्राफ को G=(V,E) पर जाने दें। V का U = { u | there is a path from u to the target } का सबसेट U बनाएं।

• ध्यान दें कि यह सबसेट U खोजना आसान है - और लक्ष्य से उलट किनारों पर DFS या BFS का उपयोग कर रैखिक समय में किया जा सकता।

इस उपसमूह का उपयोग करना, एक ग्राफ G'=(U,E') जहां U ऊपर और E' = E [intersection] UxU परिभाषित किया गया है बनाने के [एक ही किनारों, लेकिन U में कोने पर ही लागू]।

यादृच्छिक चलाएं (DFSG' पर जब तक आप लक्ष्य तक नहीं पहुंच जाते हैं, तो यादृच्छिक रूप से चलाएं।

• नोट - विचार के लिए एक रास्ता मिल रहा है - necesseraly सरल नहीं, और इस तरह आप एक visited सेट बनाए रखने के नहीं करना चाहिए।
• आप "ब्रेक नियम" जोड़ सकते हैं कि यदि आप किसी निश्चित गहराई तक पहुंचते हैं, तो आप सर्किलों में अनंत लूप से बचने के लिए लक्ष्य - अनारक्षित, खोज लेंगे।
• perofrmance अलग होने की उम्मीद है, क्योंकि यह पाया पथ है, जो बहुत लंबे समय या बहुत ही कम हो सकता है की लंबाई में रैखिक है ...

Answer 2

यह आप यादृच्छिक से क्या मतलब है पर निर्भर करता है। यदि आपको कोई परवाह नहीं है कि इसका क्या अर्थ है, तो आपने monte-carlo method?

अंधेरे, छद्म कोड में मेरा जंगली स्टैब, यह मानते हुए कि लक्ष्य बिल्कुल पहुंच योग्य है, और आपके पास एक अप्रत्यक्ष ग्राफ है।

1. s <- start node 
2. Choose a random neighbor of s, call that neighbor n. 
3. Add the edge from s to n to the path. 
4. Set s <- n. 
5. Go to 2, unless you've reached the target. 

amit की चेतावनियां यहाँ भी पकड़,:

• आप एक "तोड़ नियम" है कि अगर आप एक निश्चित गहराई तक पहुँचते हैं, आप लक्ष्य तलाश करेंगे जोड़ सकते हैं -, unrandomised अनंत छोरों से बचने के लिए गोल - गोल।
• perofrmance अलग होने की उम्मीद है, क्योंकि यह पाया पथ की लंबाई, जो बहुत लंबे समय या बहुत ही कम हो सकता है में रैखिक है ...

Answer 3

अगर मैं आपके सवाल का सही ढंग से समझ, आप की कोशिश कर रहे uniform spanning tree उत्पन्न करें।