2008-09-09 23 views
7

मैं कुछ असामान्य गुणों के साथ ग्राफ एल्गोरिदम की तलाश में हूं।ग्राफ खोज एल्गोरिदम

ग्राफ में प्रत्येक किनारा या तो "अप" एज या "डाउन" एज है।

एक मान्य पथ "अप" की अनिश्चित संख्या के बाद अनिश्चित संख्या में "डाउन" या इसके विपरीत अनिश्चित संख्या के बाद जा सकता है। हालांकि यह एक से अधिक बार दिशा नहीं बदल सकता है।

जैसे, एक मान्य पथ हो सकता है एक "ऊपर" "नीचे" "ऊपर" सी बी ई 'नीचे' एफ गलत रास्ता हो सकता है एक "ऊपर" "नीचे" सी बी डी "ऊपर"

दो नोड्स के बीच सबसे कम वैध पथ खोजने के लिए एक अच्छा एल्गोरिदम क्या है? सभी बराबर लंबाई सबसे कम पथ खोजने के बारे में क्या?

उत्तर

11

मान लें कि आपके पास कोई हेरिस्टिक्स नहीं है, dijkstra's algorithm की विविधता काफी अच्छी तरह से पर्याप्त होनी चाहिए। हर बार जब आप एक नया किनारा मानते हैं, तो अपने "पूर्वजों" के बारे में जानकारी संग्रहीत करें। फिर, इनवेरिएंट (केवल एक दिशा परिवर्तन) की जांच करें, और बैकट्रैक अगर इसका उल्लंघन किया जाता है।

यहां पर पूर्वजों को सभी किनारों हैं जो सबसे कम पथ के साथ वर्तमान नोड तक पहुंचने के लिए घुमाए गए थे। पूर्वजों की जानकारी को स्टोर करने का एक अच्छा तरीका संख्याओं की एक जोड़ी होगी। यदि यू ऊपर है, और डी नीचे है, तो एक विशेष किनारे के पूर्वजों UUUDDDD हो सकते हैं, जो जोड़ी 3, 4 होगी। इनवेरिएंट की वजह से आपको तीसरे नंबर की आवश्यकता नहीं होगी।

चूंकि हमने डिजस्ट्रा के एल्गोरिदम का उपयोग किया है, इसलिए कई छोटे पथों को ढूंढने से पहले ही इसका ख्याल रखा जा रहा है।

+0

दरअसल, आपको अप और डाउन की संख्या को स्टोर करने की भी आवश्यकता नहीं है (जब तक कि आप बाद में इसका उपयोग नहीं करना चाहते)। ऐसा लगता है कि आप केवल दिशा परिवर्तनों की संख्या को स्टोर करने में सक्षम होना चाहिए। इस विशेष उदाहरण में, एक स्वीकार्य पथ एक दिशा निर्देश के साथ एक है। – jbl

4

शायद आप अपने ग्राफ को एक सामान्य निर्देशित ग्राफ में बदल सकते हैं और फिर मौजूदा एल्गोरिदम का उपयोग कर सकते हैं।

एक तरीका ग्राफ को दो ग्राफों में विभाजित करना होगा, एक ऊपर के किनारों के साथ एक और सभी नीचे किनारों के साथ और ग्राफ़ एक के सभी नोड्स और ग्राफ़ दो पर संबंधित नोड के बीच निर्देशित किनारों के साथ।

पहला ग्राफ में शुरू करने और ग्राफ दो में समाप्त होने के लिए हल करें और फिर दूसरी तरफ, फिर सबसे छोटा समाधान जांचें।

2

कोई आपको लगता है कि आपका मानक BFS यहां काम करना चाहिए। जब भी आप खुली सूची में नोड जोड़ते हैं, तो आप इसे एक ऐसे स्ट्रक्चर में लपेट सकते हैं जो यह रखता है कि यह किस दिशा में (ऊपर या नीचे) और एक बूलियन ध्वज का उपयोग कर रहा है यह दर्शाता है कि क्या उसने अभी तक निर्देशों को स्विच किया है या नहीं। इन्हें निर्धारित करने के लिए उपयोग किया जा सकता है कि उस नोड से कौन से आउटगोइंग किनारे मान्य हैं।

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

2

A* विशेष रूप से तैयार की गई लागत (जी स्कोर) और हेरिस्टिक (एच स्कोर) फ़ंक्शन इसे संभाल सकता है।

लागत के लिए आप पथ में दिशा परिवर्तनों की संख्या का ट्रैक रख सकते हैं और दूसरे परिवर्तन पर असीमित लागत जोड़ सकते हैं (यानी उन शाखाओं की खोज को काट दें)।

हेरिस्टिक कुछ और विचार लेता है, खासकर जब आप हेरिस्टिक स्वीकार्य रखना चाहते हैं (लक्ष्य तक न्यूनतम दूरी को कभी भी अधिक महत्व नहीं देते) और मोनोटोनिक। (ए * गारंटी देने का एकमात्र तरीका एक इष्टतम समाधान पाता है।)

शायद हेरिस्टिक बनाने के लिए उपलब्ध डोमेन के बारे में अधिक जानकारी है? (यानी x, y ग्राफ में नोड्स के y निर्देशांक?)

बेशक, जिस ग्राफ को आप हल करना चाहते हैं उसके आकार के आधार पर, आप पहली बार चौड़ाई पहली खोज या डिजस्ट्रा के एल्गोरिदम जैसे सरल एल्गोरिदम का प्रयास कर सकते हैं: मूल रूप से प्रत्येक खोज एल्गोरिदम करेगा, और हर किसी के लिए आपको एक लागत समारोह (या इसी तरह) की आवश्यकता होगी।

1

आप एक मानक ग्राफ खोज समारोह है, तो एक पुस्तकालय में Graph.shortest(from, to) कहते हैं, आप पाश कर सकते हैं और कम से कम, सी #/स्यूडोकोड में:

[ (fst.shortest(A, C) + nxt.shortest(C, B)) 
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(min) 

आप कम से कम पथ/रास्तों और यह इतना याद करने की जरूरत है होता यह है कि अपने मानक समारोह आप डेटा देता है, तो आप भी उच्चारण कर सकता है

[ [fst, nxt, C, fst.shortest(A, C), nxt.shortest(C,B)] 
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(myMin) 

जहां myMin दो [fst, nxt, C, AC, BD] tuples की तुलना करनी चाहिए और एक कम दूरी है, या दोनों औरसंभालने छोड़एक स्मार्ट समारोह है।

यदि हमारे ग्राफ बड़े हैं और स्मृति का उपयोग नहीं करते हैं (जो संभव है कि वे गतिशील रूप से उत्पन्न होते हैं), लेकिन वास्तव में कोई भी गति ओवरहेड नहीं है, तो यह कुछ मेमोरी ओवरहेड है।

संबंधित मुद्दे