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

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

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

समस्या वर्णन

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

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

वेरिएंट

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

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

तीसरा पैरामीटर स्टोकेस्टिक संस्करणों तक ही सीमित है और यह इस बारे में है कि हम प्राप्तियों के वितरण के बारे में क्या धारणाएँ बना सकते हैं और वितरण को इनपुट में कैसे दर्शाया जाता है। स्टोचैस्टिक कैनेडियन ट्रैवलर प्रॉब्लम और एज-इंडिपेंडेंट स्टोचैस्टिक शॉर्टेस्ट पाथ प्रॉब्लम (i-SSPPR) में, प्रत्येक अनिश्चित किनारे (या लागत) के अहसास में होने की एक संबद्ध संभावना है और ग्राफ़ में एक किनारे होने की घटना स्वतंत्र है जिसके अन्य किनारे अहसास में हैं। यद्यपि यह काफी सरलीकरण है, फिर भी समस्या तीव्र P|#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 के लिए, हम कॉल करते हैं $E_{B}(v,V)$ इसके घटना किनारों को किनारे सेट बी के संबंध में वी पर सेट किया गया है। इसके अलावा, एक अहसास के लिए $G\in {\mathcal {G}}(V,E,F)$, होने देना $d_{B}(s,t)$ ग्राफ़ में s से t तक के सबसे छोटे पथ की लागत हो। इसे ऑफ-लाइन समस्या कहा जाता है क्योंकि ऐसी समस्या के लिए एक एल्गोरिदम में ग्राफ़ की पूरी जानकारी होगी।

हम कहते हैं कि एक रणनीति $\pi$ ऐसे ग्राफ़ को नेविगेट करने के लिए एक मैपिंग है $({\mathcal {P}}(E),{\mathcal {P}}(F),V)$ को $V$, कहाँ ${\mathcal {P}}(X)$ X के सत्ता स्थापित को दर्शाता है। हम लागत को परिभाषित करते हैं $c(\pi ,B)$ एक रणनीति का $\pi$ किसी विशेष अनुभूति के संबंध में $G=(V,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}$. यदि लक्ष्य कभी प्राप्त नहीं होता है, तो हम कहते हैं कि हमारी लागत अनंत है। यदि लक्ष्य प्राप्त हो जाता है, तो हम चलने की लागत को प्रमुखता के साथ पार किए गए सभी किनारों की लागत के योग के रूप में परिभाषित करते हैं।

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

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

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

जटिलता

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

अनुप्रयोग

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

खुली समस्याएँ

समस्या की उम्र और इसके कई संभावित अनुप्रयोगों के बावजूद, कई स्वाभाविक प्रश्न अभी भी खुले हैं। क्या कोई स्थिर-कारक सन्निकटन है या समस्या APX-कठिन है? क्या यह i-SSPPR #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).