कैनेडियन ट्रैवलर प्रॉब्लम

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

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

समस्या वर्णन

किसी दिए गए उदाहरण के लिए, छिपा हुआ ग्राफ़ कैसा दिख सकता है, इसकी कई संभावनाएँ या अनुभूति हैं। किसी उदाहरण को देखते हुए, उदाहरण का सर्वोत्तम विधि से पालन कैसे किया जाए, इसका विवरण नीति कहलाता है। सीटीपी का कार्य इष्टतम पॉलिसियों की अपेक्षित निवेश की गणना करना है। किसी इष्टतम नीति के वास्तविक विवरण की गणना करना कठिन समस्या हो सकती है।

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

वेरिएंट

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

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

तीसरा मापदंड स्टोकेस्टिक संस्करणों तक ही सीमित है और यह इस बारे में है कि हम प्राप्तियों के वितरण के बारे में क्या धारणाएँ बना सकते हैं और वितरण को इनपुट में कैसे दर्शाया जाता है। स्टोचैस्टिक कैनेडियन ट्रैवलर प्रॉब्लम और एज-इंडिपेंडेंट स्टोचैस्टिक शॉर्टेस्ट पाथ प्रॉब्लम (आई-एसएसपीपीआर) में, प्रत्येक अनिश्चित किनारे (या निवेश) के अनुभूति में होने की संबद्ध संभावना है और ग्राफ़ में किनारे होने की घटना स्वतंत्र है जिसके अन्य किनारे अनुभूति में हैं। यद्यपि यह अधिक सरलीकरण है, फिर भी समस्या तीव्र P-हार्ड है। अन्य प्रकार वितरण पर कोई धारणा नहीं बनाना है, किन्तु यह आवश्यक है कि गैर-शून्य संभावना वाले प्रत्येक अनुभूति को स्पष्ट रूप से बताया जाए (जैसे कि "किनारे समुच्चय की संभावना 0.1 {{3,4}, {1,2} }, संभावना 0.2)। ..”). इसे डिस्ट्रीब्यूशन स्टोकेस्टिक शॉर्टेस्ट पाथ प्रॉब्लम (डी-एसएसपीपीआर या आर-एसएसपीपीआर) कहा जाता है और यह एनपी-पूर्ण है। पहला संस्करण दूसरे की तुलना में कठिन है क्योंकि पहला लघुगणकीय स्थान में कुछ वितरणों का प्रतिनिधित्व कर सकता है जो बाद वाला रैखिक स्थान में दर्शाता है।

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

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

औपचारिक परिभाषा

हम 1989 से पेपर में अध्ययन किए गए संस्करण को परिभाषित करते हैं। अर्थात लक्ष्य सबसे व्यर्थ स्थिति में प्रतिस्पर्धी अनुपात को कम करना है। यह आवश्यक है कि हम कुछ शर्तों का परिचय देकर प्रारंभ करें।

किसी दिए गए ग्राफ़ और अप्रत्यक्ष ग्राफ़ के वर्ग पर विचार करें जिसे किसी दिए गए समुच्चय से एक या अधिक किनारों को जोड़कर बनाया जा सकता है। औपचारिक रूप से, मान लीजिए ${\mathcal {G}}(V,E,F)=\{(V,E+F')|F'\subseteq F\},E\cap F=\emptyset$ जहां हम E को किनारों के रूप में सोचते हैं जो ग्राफ़ में होना चाहिए और F को किनारों के रूप में जो ग्राफ़ में हो सकते हैं। हम कहते हैं कि $G\in {\mathcal {G}}(V,E,F)$ ग्राफ़ वर्ग का अनुभूति है। इसके अतिरिक्त, मान लीजिए कि W संबद्ध निवेश मैट्रिक्स है जहां $w_{ij}$ शीर्ष i से शीर्ष j तक जाने की निवेश है, यह मानते हुए कि यह बढ़त प्राप्ति में है।

V में किसी भी शीर्ष v के लिए हम V पर किनारे सेट B के संबंध में इसके घटना किनारों को $E_{B}(v,V)$ कहते हैं। इसके अतिरिक्त प्राप्ति $G\in {\mathcal {G}}(V,E,F)$ के लिए $d_{B}(s,t)$ ग्राफ़ में s से t तक के सबसे छोटे पथ की निवेश होगी। इसे ऑफ-लाइन समस्या कहा जाता है क्योंकि ऐसी समस्या के लिए एल्गोरिदम में ग्राफ़ की पूरी जानकारी होती है।

हम कहते हैं कि ऐसे ग्राफ़ को नेविगेट करने के लिए रणनीति $({\mathcal {P}}(E),{\mathcal {P}}(F),V)$ से $V$ तक मैपिंग है जहां ${\mathcal {P}}(X)$ X के पावरसेट को दर्शाता है। हम विशेष प्राप्ति $G=(V,B)$ के संबंध में रणनीति $\pi$ की निवेश $c(\pi ,B)$ को निम्नानुसार परिभाषित करते हैं।

• मान लीजिए $v_{0}=s,E_{0}=E$ और $F_{0}=F$.
• $i=0,1,2,...$, के लिए परिभाषित करना
  • $E_{i+1}=E_{i}\cup E_{B}(v_{i},V)$,
  • $F_{i+1}=F_{i}-E_{F}(v_{i},V)$, और
  • $v_{i+1}=\pi (E_{i+1},F_{i+1},v_{i})$.
• यदि कोई T ऐसा उपस्थित है $v_{T}=t$, तब $c(\pi ,B)=\sum _{i=0}^{T-1}w_{v_{i},v_{i+1}}$; अन्यथा माना $c(\pi ,B)=\infty$.

दूसरे शब्दों में, हम उन किनारों के आधार पर नीति का मूल्यांकन करते हैं जिन्हें हम वर्तमान में ग्राफ़ ($E_{i}$) में जानते हैं और जिन किनारों को हम जानते हैं वे ग्राफ़ ($F_{i}$) में हो सकते हैं जब हम ग्राफ़ में कदम उठाते हैं, तो हमारे नए स्थान पर पड़ने वाले किनारे हमें ज्ञात हो जाते हैं। वे किनारे जो ग्राफ़ में हैं, $E_{i}$ जोड़ दिए जाते हैं , और चाहे किनारे ग्राफ़ में हों या नहीं, उन्हें अज्ञात किनारों के समुच्चय $F_{i}$ से हटा दिया जाता है, यदि लक्ष्य कभी प्राप्त नहीं होता है, तो हम कहते हैं कि हमारी निवेश अनंत है। यदि लक्ष्य प्राप्त हो जाता है, तो हम चलने की निवेश को प्रमुखता के साथ पार किए गए सभी किनारों की निवेश के योग के रूप में परिभाषित करते हैं।

अंत में, हम कनाडाई ट्रैवलर समस्या को परिभाषित करते हैं।

सीटीपी उदाहरण $(V,E,F,s,t,r)$ को देखते हुए, तय करें कि क्या ऐसी कोई नीति उपस्थित है $\pi$ जो प्रत्येक प्राप्ति के लिए $(V,B)\in {\mathcal {G}}(V,E,F)$ , पॉलिसी की निवेश $c(\pi ,B)$ ऑफ-लाइन इष्टतम $d_{B}(s,t)$ के r गुना से अधिक नहीं है

पापादिमित्रीउ और यान्नाकाकिस ने कहा कि यह खेल सिद्धांत को परिभाषित करता है | दो-खिलाड़ियों का खेल, जहां खिलाड़ी अपने संबंधित पथ की निवेश पर प्रतिस्पर्धा करते हैं और किनारे का समुच्चय दूसरे खिलाड़ी (प्रकृति) द्वारा चुना जाता है।

जटिलता

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

स्टोकेस्टिक समस्या के निर्देशित संस्करण को संचालन अनुसंधान में रिकोर्स के साथ स्टोकेस्टिक शॉर्टेस्ट पाथ समस्या के रूप में जाना जाता है।

अनुप्रयोग

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

ओपन समस्याएँ

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

यह भी देखें

• ग्राफ ट्रैवर्सल
• हिटिंग समय
• सबसे छोटा पथ समस्या

संदर्भ

• C.H. Papadimitriou; M. Yannakakis (1989). "Shortest paths without a map". Lecture Notes in Computer Science. Proc. 16th ICALP. Vol. 372. Springer-Verlag. pp. 610–620.
• Dror Fried; Solomon Eyal Shimony; Amit Benbassat; Cenny Wenner (2013). "Complexity of Canadian traveler problem variants". Theoretical Computer Science. 487: 1–16. doi:10.1016/j.tcs.2013.03.016. S2CID 17810202.
• David Karger; Evdokia Nikolova (2008). "Exact Algorithms for the Canadian Traveller Problem on Paths and Trees". {{cite journal}}: Cite journal requires |journal= (help)
• Zahy Bnaya; Ariel Felner; Solomon Eyal Shimony (2009). Canadian Traveller Problem with remote sensing. International Joint Conference On Artificial Intelligence (IJCAI).