1. घर
  2. सवाल और जवाब
  3. एक ग्रिड पर सभी गैर अवरुद्ध वर्गों का दौरा करने के कम से कम पथ ढूँढना

एक ग्रिड पर सभी गैर अवरुद्ध वर्गों का दौरा करने के कम से कम पथ ढूँढना

2010-05-20 9 views
14

मान लीजिए कि आप इस तरह एक ग्रिड (बेतरतीब ढंग से बनाया) करते हैं जबकि बक्से के बक्से, सफेद बॉक्स में से प्रत्येक के माध्यम से जाने के लिए सबसे कम पथ क्या होगा? आप जितनी बार चाहें उतनी बार प्रत्येक श्वेत बॉक्स पर जा सकते हैं और काले बक्से पर कूद नहीं सकते हैं। काले बक्से दीवारों की तरह हैं। सरल शब्दों में आप केवल सफेद बॉक्स से सफेद बॉक्स में स्थानांतरित कर सकते हैं।एक ग्रिड पर सभी गैर अवरुद्ध वर्गों का दौरा करने के कम से कम पथ ढूँढना

आप किसी भी दिशा में, यहां तक ​​कि तिरछे भी स्थानांतरित कर सकते हैं।

दो subquestions:

  1. आप जाने से पहले सभी ब्लैक बॉक्स की स्थिति पता मान लें।
  2. मान लें कि जब आप इसके आस-पास के श्वेत बॉक्स में हों तो आपको केवल काले बॉक्स की स्थिति पता है।

स्रोत

2010-05-20 Laz

+0

"सफेद बक्से में से प्रत्येक के माध्यम से जाने का सबसे छोटा रास्ता क्या होगा"? तुम यहाँ क्या पूछ रहे हो क्या आपका मतलब है "सफेद बक्से में से प्रत्येक को जाना"? – naiad

+0

हाँ .. आपको बस सभी सफेद बक्से के माध्यम से पार करने की जरूरत है। – Laz

+0

सबसे छोटा रास्ता खोजने के लिए, आपको एक ब्रूट फोर्स सर्च करना होगा। यह वास्तव में कोई फर्क नहीं पड़ता कि आप सामने वाले काले बक्से जानते हैं या नहीं। – mdma

उत्तर

-1

एक ग्राफ (जहां प्रत्येक नोड पर सबसे 8 अन्य नोड है) के रूप में यह निर्माण की कोशिश करो और http://en.wikipedia.org/wiki/Travelling_salesman_problem

स्रोत

2010-05-20 16:57:42 corsiKa

+0

-1 से अधिक बार देखा जा सकता है -1 तथ्य यह है कि इसे एनपी-पूर्ण समस्या में कम किया जा सकता है (जिसे आपने भी नहीं दिखाया है) उसे बलपूर्वक बल देने के लिए कहने से ज्यादा मदद नहीं है। –

+0

@ ब्लूराजा: केवल इसलिए कि आपको जवाब पसंद नहीं है, यह गलत नहीं है। मैंने ग्लोकोडर को -1 दिया होगा क्योंकि उसका जवाब इस तथ्य को अनदेखा करता है कि टीएसपी को आम तौर पर हर बार एक शहर का दौरा करने की ज़रूरत होती है, जो यहां उपयुक्त मॉडल नहीं है, क्योंकि किसी को एक से अधिक सफेद बक्से देखने की जरूरत है। –

+0

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

0

यह शूरवीरों टूर समस्या है, जहां एक विशिष्ट समाधान के लिए सभी संभव मार्गों का मूल्यांकन करता है के समान है जैसे कि यह इलाज शुरुआती वर्ग से उत्पन्न। जब कोई भ्रमण पूरा नहीं किया जा सकता है, तो बैकट्रैकिंग का उपयोग पिछले निर्णयों पर बैक अप लेने के लिए किया जाता है। आपकी समस्या अधिक आराम से है क्योंकि आप एक से अधिक बार वर्गों पर जा सकते हैं। नाइट्स टूर और ट्रेवलिंग सेलमैन समस्याओं को आम तौर पर एक बार में प्रत्येक वर्ग में जाने की आवश्यकता होती है।

देखें http://en.wikipedia.org/wiki/Knight's_tour

स्रोत

2010-05-20 16:59:43 mdma

+0

यदि आप एक से अधिक बार वर्गों पर जा सकते हैं, तो आप कैसे निर्धारित कर सकते हैं कि कोई दौरा पूरा नहीं हो सकता है (और इसलिए बैकट्रैकिंग शुरू करने का समय है)? आम तौर पर यह निर्धारित किया जाता है जब सभी पास के वर्गों का पहले से ही दौरा किया जा चुका है - लेकिन यदि आप उन्हें दो बार देख सकते हैं तो यह अब लागू नहीं होता है :-) – psmears

+0

आप स्क्वायर से स्क्वायर तक पहुंच योग्यता विश्लेषण कर सकते हैं - उदा। स्रोत वर्ग से लक्ष्य पथ तक सभी पथों का मूल्यांकन करें। यहां, आप चक्र से बचते हैं, हमें बस एक पथ की आवश्यकता होती है, इसलिए प्रत्येक वर्ग को केवल एक बार देखा जाता है। उदाहरण के तौर पर, एक बोर्ड पर विचार करें जहां केंद्र के नीचे काले वर्ग इसे दो हिस्सों में विभाजित करते हैं। आपके द्वारा शुरू किए गए आधा भाग वर्ग पहुंच योग्य हैं, दूसरे छमाही के वर्ग नहीं हैं। – mdma

4

आप एक पूरा ग्राफ जहां दो नोड्स (सफेद बॉक्स) के बीच की दूरी उन नोड्स के बीच कम से कम पथ की लंबाई के रूप में समस्या मॉडल चाहिए। उन पथ की लंबाई की गणना Floyd-Warshall एल्गोरिदम द्वारा की जा सकती है। फिर, आप इसे "Traveling salesman" के रूप में देख सकते हैं, जैसे ग्लोकोडर ने लिखा था।

संपादित करें: इसे और स्पष्ट करने के लिए: आप सफेद बक्से के अनुक्रम से भूलभुलैया के माध्यम से प्रत्येक "रोचक" पथ का वर्णन कर सकते हैं। क्योंकि यदि आपके पास प्रत्येक श्वेत बॉक्स पर जाने के लिए मनमाने ढंग से पथ है, तो आप इसे उप-पथों में विभाजित कर सकते हैं जो प्रत्येक एक नए सफेद बॉक्स पर समाप्त होता है जो अब तक नहीं आया है। सफेद बॉक्स ए से बी के इस उप-पथों में से प्रत्येक को ए से बी के सबसे छोटे उप-पथ द्वारा प्रतिस्थापित किया जा सकता है, यही कारण है कि आपको सबसे कम-पथ-के-ऑल-जोड़े-ऑफ-नोड्स मैट्रिक्स की आवश्यकता होती है।

स्रोत

2010-05-20 17:10:34

+0

यह बहुत ही मजबूत है। टीएसपी सीधे लागू होता है। फ़्लॉइड-वॉर्शल के माध्यम से क्यों जाना है?-1 जब तक आप आगे विस्तार नहीं करते। –

+0

@ मॉरॉन: विकिपीडिया से, पहला वाक्य: "कार्य एक छोटा सा संभावित दौरा ढूंढना है जो प्रत्येक शहर * बिल्कुल एक बार * पर जाता है।" यही मेरा सुझाव है: समस्या को उस तरह की टीएसपी समस्या के रूप में देखने की इजाजत देता है, भले ही आपको प्रत्येक वर्ग को एक से अधिक बार जाना है। –

+0

@ डॉक्टर: मैं देखता हूं कि आप क्या प्राप्त कर रहे हैं। मैं -1 को हटा दूंगा। हालांकि अभी भी बहुत मजबूत है। मैंने -1 को पूर्ववत करने की अनुमति देने के लिए एक जगह हटा दी। –

1

यह एक एनपी-पूर्ण समस्या प्रतीत होता है।

ग्रिड ग्राफ में हैमिल्टनियन पथ एनपी-पूर्ण यहां दिखाया गया है: Hamilton Paths in Grid Graphs।

नोट ग्रिड ग्राफ = पूर्ण ग्रिड का सबग्राफ नोट करें।

बेशक, मैंने उस पेपर को नहीं पढ़ा है, इसलिए पहले इसकी पुष्टि करें, विशेष रूप से विकर्ण आंदोलन ने भाग की अनुमति दी है।

स्रोत

2010-05-20 18:16:42

+0

यह हैमिल्टनियन पथ खोजने के लिए कैसे कम करता है? वह स्पष्ट रूप से कहता है कि आप जितनी बार चाहें उतने सफेद बॉक्स पर जा सकते हैं, जो हैमिल्टनियन पथ में मामला नहीं है। – bnaul

+0

@bnaul: http://stackoverflow.com/questions/2359345/non-cycle-path-to-all-nodes/2360303#2360303 के समान एक कमी शायद काम करेगी। –

1

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

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

स्रोत

2010-05-20 20:09:37 Grembo

1

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

स्रोत

2010-06-30 20:56:42 Suresh

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

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