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

Revision as of 09:00, 5 July 2023

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

यह अनुकूलन समस्या 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,...$ $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 कठिन समस्या है।^[1] इस अंतर को पाटना ओपन समस्या थी, किन्तु तब से निर्देशित और अप्रत्यक्ष दोनों संस्करणों को पीएसपीएसीई-हार्ड दिखाया गया था।^[2]

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

अनुप्रयोग

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

ओपन समस्याएँ

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

यह भी देखें

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

↑ Papadimitriou and Yannakakis, 1989, p. 148
↑ Fried, Shimony, Benbassat, and Wenner 2013
↑ Briggs, Amy J.; Detweiler, Carrick; Scharstein, Daniel (2004). "लैंडमार्क-आधारित रोबोट नेविगेशन के लिए अपेक्षित सबसे छोटा पथ". International Journal of Robotics Research. 23 (7–8): 717–718. CiteSeerX 10.1.1.648.3358. doi:10.1177/0278364904045467. S2CID 15681481.
↑ Karger and Nikolova, 2008, p. 1

संदर्भ

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).

[1] Papadimitriou and Yannakakis, 1989, p. 148

[2] Fried, Shimony, Benbassat, and Wenner 2013

[briggs04-3] Briggs, Amy J.; Detweiler, Carrick; Scharstein, Daniel (2004). "लैंडमार्क-आधारित रोबोट नेविगेशन के लिए अपेक्षित सबसे छोटा पथ". International Journal of Robotics Research. 23 (7–8): 717–718. CiteSeerX 10.1.1.648.3358. doi:10.1177/0278364904045467. S2CID 15681481.

[4] Karger and Nikolova, 2008, p. 1

[1]

[2]

[3]

[4]

@@ Line 1: / Line 1: @@
-[[कंप्यूटर विज्ञान]] और [[ग्राफ सिद्धांत]] में, कैनेडियन ट्रैवलर समस्या (सीटीपी) उन ग्राफ़ के लिए सबसे छोटी पथ समस्या का सामान्यीकरण है जो ''आंशिक रूप से देखने योग्य'' हैं। दूसरे शब्दों में, ग्राफ़ पर किसी दिए गए बिंदु पर यात्री पूरा ग्राफ़ नहीं देख सकता है, केवल आसन्न नोड्स या निश्चित प्राप्ति प्रतिबंध नहीं देख सकता है।
+[[कंप्यूटर विज्ञान]] और [[ग्राफ सिद्धांत]] में, '''कैनेडियन ट्रैवलर समस्या (सीटीपी)''' उन ग्राफ़ के लिए सबसे छोटी पथ समस्या का सामान्यीकरण है जो ''आंशिक रूप से देखने योग्य'' हैं। दूसरे शब्दों में, ग्राफ़ पर किसी दिए गए बिंदु पर ट्रैवलर पूरा ग्राफ़ नहीं देख सकता है, केवल आसन्न नोड्स या निश्चित प्राप्ति प्रतिबंध नहीं देख सकता है।
-यह [[अनुकूलन समस्या]] 1989 में [[क्रिस्टोस पापादिमित्रियोउ]] और [[माइकलिस यानाकाकिस]] द्वारा पेश की गई थी और तब से समस्या के कई प्रकारों का अध्ययन किया गया है। माना जाता है कि यह नाम उन लेखकों की बातचीत से आया है, जिन्हें [[कनाडाई]] ड्राइवरों की कठिनाई के बारे में पता चला था: बर्फबारी के कारण बेतरतीब ढंग से अवरुद्ध होने वाली सड़कों के साथ शहरों के नेटवर्क की यात्रा करना। स्टोकेस्टिक संस्करण, जहां प्रत्येक किनारा ग्राफ़ में स्वतंत्र रूप से होने की संभावना से जुड़ा हुआ है, को स्टोकेस्टिक [[सबसे छोटा पथ समस्या]] विद रिकोर्स (एसएसपीपीआर) नाम के तहत संचालन अनुसंधान में काफी ध्यान दिया गया है।
+यह [[अनुकूलन समस्या]] 1989 में [[क्रिस्टोस पापादिमित्रियोउ]] और [[माइकलिस यानाकाकिस]] द्वारा प्रस्तुत की गई थी और तब से समस्या के कई प्रकारों का अध्ययन किया गया है। माना जाता है कि यह नाम उन लेखकों की वार्तालाप से आया है, जिन्हें [[कनाडाई]] ड्राइवरों की कठिनाई के बारे में पता चला था: बर्फबारी के कारण अनियमित विधि से अवरुद्ध होने वाली सड़कों के साथ शहरों के नेटवर्क की यात्रा करना कठिन था। स्टोकेस्टिक संस्करण, जहां प्रत्येक किनारा ग्राफ़ में स्वतंत्र रूप से होने की संभावना से जुड़ा हुआ है, जिसको स्टोकेस्टिक [[सबसे छोटा पथ समस्या]] विद रिकोर्स (एसएसपीपीआर) नाम के अनुसार संचालन अनुसंधान में अधिक ध्यान दिया गया है।
 == समस्या वर्णन ==
@@ Line 7: / Line 7: @@
 {{expand section|date=February 2017}}
-किसी दिए गए उदाहरण के लिए, छिपा हुआ ग्राफ़ कैसा दिख सकता है, इसकी कई संभावनाएँ या अहसास हैं। किसी उदाहरण को देखते हुए, उदाहरण का सर्वोत्तम तरीके से पालन कैसे किया जाए, इसका विवरण नीति कहलाता है। CTP का कार्य इष्टतम पॉलिसियों की अपेक्षित लागत की गणना करना है। किसी इष्टतम नीति के वास्तविक विवरण की गणना करना कठिन समस्या हो सकती है।
+किसी दिए गए उदाहरण के लिए, छिपा हुआ ग्राफ़ कैसा दिख सकता है, इसकी कई संभावनाएँ या अनुभूति हैं। किसी उदाहरण को देखते हुए, उदाहरण का सर्वोत्तम विधि से पालन कैसे किया जाए, इसका विवरण नीति कहलाता है। सीटीपी का कार्य इष्टतम पॉलिसियों की अपेक्षित निवेश की गणना करना है। किसी इष्टतम नीति के वास्तविक विवरण की गणना करना कठिन समस्या हो सकती है।
-उदाहरण के लिए उदाहरण और नीति को देखते हुए, प्रत्येक अहसास ग्राफ़ में अपना स्वयं का (नियतात्मक) वॉक उत्पन्न करता है। ध्यान दें कि वॉक आवश्यक रूप से [[ग्राफ़ सिद्धांत की शब्दावली]] नहीं है क्योंकि सबसे अच्छी रणनीति यह हो सकती है, उदाहरण के लिए, चक्र के प्रत्येक शीर्ष पर जाएँ और शुरुआत में वापस लौटें। यह सबसे छोटी पथ समस्या (पूरी तरह से सकारात्मक भार के साथ) से भिन्न है, जहां चलने में दोहराव का अर्थ है कि बेहतर समाधान मौजूद है।
+उदाहरण के लिए उदाहरण और नीति को देखते हुए, प्रत्येक अनुभूति ग्राफ़ में अपना स्वयं का (नियतात्मक) वॉक उत्पन्न करता है। ध्यान दें कि वॉक आवश्यक रूप से [[ग्राफ़ सिद्धांत की शब्दावली]] नहीं है क्योंकि सबसे अच्छी रणनीति यह हो सकती है, उदाहरण के लिए, चक्र के प्रत्येक शीर्ष पर जाएँ और प्रारंभ में वापस लौटें। यह सबसे छोटी पथ समस्या (पूरी तरह से सकारात्मक भार के साथ) से भिन्न है, जहां चलने में दोहराव का अर्थ है कि उत्तम समाधान उपस्थित है।
 == वेरिएंट ==
-कैनेडियन ट्रैवलर समस्या के प्रकारों की संख्या को अलग करने वाले मुख्य रूप से पांच पैरामीटर हैं। पहला पैरामीटर यह है कि किसी दिए गए उदाहरण और प्राप्ति के लिए पॉलिसी द्वारा उत्पादित वॉक को कैसे महत्व दिया जाए। रिकोर्स के साथ स्टोकेस्टिक शॉर्टेस्ट पाथ प्रॉब्लम में, लक्ष्य बस चलने की लागत को कम करना है (किनारे की लागत के सभी किनारों पर उस किनारे को लेने की संख्या के योग के रूप में परिभाषित किया गया है)। कनाडाई यात्री समस्या के लिए, कार्य पैदल यात्रा के [[प्रतिस्पर्धी अनुपात]] को कम करना है; यानी, उत्पादित चलने की संख्या को कम से कम करने के लिए अहसास में सबसे छोटा रास्ता है।
+कैनेडियन ट्रैवलर समस्या के प्रकारों की संख्या को अलग करने वाले मुख्य रूप से पांच मापदंड हैं। पहला मापदंड यह है कि किसी दिए गए उदाहरण और प्राप्ति के लिए पॉलिसी द्वारा उत्पादित वॉक को कैसे महत्व दिया जाए। रिकोर्स के साथ स्टोकेस्टिक शॉर्टेस्ट पाथ प्रॉब्लम में, लक्ष्य बस चलने की निवेश को कम करना है (किनारे की निवेश के सभी किनारों पर उस किनारे को लेने की संख्या के योग के रूप में परिभाषित किया गया है)। कनाडाई ट्रैवलर समस्या के लिए, कार्य पैदल यात्रा के [[प्रतिस्पर्धी अनुपात]] को कम करना है; अर्थात, उत्पादित चलने की संख्या को कम से कम करने के लिए अनुभूति में सबसे छोटा पथ है।
-दूसरा पैरामीटर यह है कि विचाराधीन उदाहरण के अनुरूप विभिन्न प्राप्तियों के संबंध में किसी नीति का मूल्यांकन कैसे किया जाए। कैनेडियन ट्रैवलर समस्या में, कोई सबसे खराब मामले का अध्ययन करना चाहता है और एसएसपीपीआर में, औसत मामले का अध्ययन करना चाहता है। औसत मामले के विश्लेषण के लिए, किसी को प्राप्तियों पर [[एक प्राथमिकता और एक पश्चवर्ती|प्राथमिकता और पश्चवर्ती]] वितरण निर्दिष्ट करना होगा।
+दूसरा मापदंड यह है कि विचाराधीन उदाहरण के अनुरूप विभिन्न प्राप्तियों के संबंध में किसी नीति का मूल्यांकन कैसे किया जाए। कैनेडियन ट्रैवलर समस्या में, कोई सबसे व्यर्थ स्थिति का अध्ययन करना चाहता है और एसएसपीपीआर में, औसत स्थिति का अध्ययन करना चाहता है। औसत स्थिति के विश्लेषण के लिए, किसी को प्राप्तियों पर [[एक प्राथमिकता और एक पश्चवर्ती|प्राथमिकता और पश्चवर्ती]] वितरण निर्दिष्ट करना होता है।
-<nowiki>तीसरा पैरामीटर स्टोकेस्टिक संस्करणों तक ही सीमित है और यह इस बारे में है कि हम प्राप्तियों के वितरण के बारे में क्या धारणाएँ बना सकते हैं और वितरण को इनपुट में कैसे दर्शाया जाता है। स्टोचैस्टिक कैनेडियन ट्रैवलर प्रॉब्लम और एज-इंडिपेंडेंट स्टोचैस्टिक शॉर्टेस्ट पाथ प्रॉब्लम (i-SSPPR) में, प्रत्येक अनिश्चित किनारे (या लागत) के अहसास में होने की संबद्ध संभावना है और ग्राफ़ में किनारे होने की घटना स्वतंत्र है जिसके अन्य किनारे अहसास में हैं। यद्यपि यह काफी सरलीकरण है, फिर भी समस्या तीव्र P|#P-हार्ड है। अन्य प्रकार वितरण पर कोई धारणा नहीं बनाना है, लेकिन यह आवश्यक है कि गैर-शून्य संभावना वाले प्रत्येक अहसास को स्पष्ट रूप से बताया जाए (जैसे कि "किनारे सेट की संभावना 0.1 {{3,4}, {1,2} }, संभावना 0.2)। ..”). इसे डिस्ट्रीब्यूशन स्टोकेस्टिक शॉर्टेस्ट पाथ प्रॉब्लम (डी-एसएसपीपीआर या आर-एसएसपीपीआर) कहा जाता है और यह एनपी-पूर्ण है। पहला संस्करण दूसरे की तुलना में कठिन है क्योंकि पहला लघुगणकीय स्थान में कुछ वितरणों का प्रतिनिधित्व कर सकता है जो बाद वाला रैखिक स्थान में दर्शाता है।</nowiki>
+<nowiki>तीसरा मापदंड स्टोकेस्टिक संस्करणों तक ही सीमित है और यह इस बारे में है कि हम प्राप्तियों के वितरण के बारे में क्या धारणाएँ बना सकते हैं और वितरण को इनपुट में कैसे दर्शाया जाता है। स्टोचैस्टिक कैनेडियन ट्रैवलर प्रॉब्लम और एज-इंडिपेंडेंट स्टोचैस्टिक शॉर्टेस्ट पाथ प्रॉब्लम (आई-एसएसपीपीआर) में, प्रत्येक अनिश्चित किनारे (या निवेश) के अनुभूति में होने की संबद्ध संभावना है और ग्राफ़ में किनारे होने की घटना स्वतंत्र है जिसके अन्य किनारे अनुभूति में हैं। यद्यपि यह अधिक सरलीकरण है, फिर भी समस्या तीव्र P-हार्ड है। अन्य प्रकार वितरण पर कोई धारणा नहीं बनाना है, किन्तु यह आवश्यक है कि गैर-शून्य संभावना वाले प्रत्येक अनुभूति को स्पष्ट रूप से बताया जाए (जैसे कि "किनारे समुच्चय की संभावना 0.1 {{3,4}, {1,2} }, संभावना 0.2)। ..”). इसे डिस्ट्रीब्यूशन स्टोकेस्टिक शॉर्टेस्ट पाथ प्रॉब्लम (डी-एसएसपीपीआर या आर-एसएसपीपीआर) कहा जाता है और यह एनपी-पूर्ण है। पहला संस्करण दूसरे की तुलना में कठिन है क्योंकि पहला लघुगणकीय स्थान में कुछ वितरणों का प्रतिनिधित्व कर सकता है जो बाद वाला रैखिक स्थान में दर्शाता है।</nowiki>
-चौथा और अंतिम पैरामीटर यह है कि समय के साथ ग्राफ़ कैसे बदलता है। सीटीपी और एसएसपीपीआर में, प्राप्ति निश्चित है लेकिन ज्ञात नहीं है। रिकोर्स और रीसेट के साथ स्टोकेस्टिक शॉर्टेस्ट पाथ समस्या या अपेक्षित शॉर्टेस्ट पाथ समस्या में, नीति द्वारा उठाए गए प्रत्येक चरण के बाद वितरण से नया अहसास चुना जाता है। इस समस्या को बहुपद क्षितिज के साथ मार्कोव निर्णय प्रक्रिया में घटाकर बहुपद समय में हल किया जा सकता है। मार्कोव सामान्यीकरण, जहां ग्राफ़ का एहसास अगले अहसास को प्रभावित कर सकता है, बहुत कठिन माना जाता है।
+चौथा और अंतिम मापदंड यह है कि समय के साथ ग्राफ़ कैसे बदलता है। सीटीपी और एसएसपीपीआर में, प्राप्ति निश्चित है किन्तु ज्ञात नहीं है। रिकोर्स और रीसमुच्चय के साथ स्टोकेस्टिक शॉर्टेस्ट पाथ समस्या या अपेक्षित शॉर्टेस्ट पाथ समस्या में, नीति द्वारा उठाए गए प्रत्येक चरण के बाद वितरण से नया अनुभूति चुना जाता है। इस समस्या को बहुपद क्षितिज के साथ मार्कोव निर्णय प्रक्रिया में घटाकर बहुपद समय में हल किया जा सकता है। मार्कोव सामान्यीकरण, जहां ग्राफ़ का अनुभूति अगले अनुभूति को प्रभावित कर सकता है, इसलिए इसको बहुत कठिन माना जाता है।
-एक अतिरिक्त पैरामीटर यह है कि बोध पर नए ज्ञान की खोज कैसे की जा रही है। सीटीपी के पारंपरिक वेरिएंट में, एजेंट आसन्न शीर्ष पर पहुंचने पर किनारे के सटीक वजन (या स्थिति) को उजागर करता है। हाल ही में नए संस्करण का सुझाव दिया गया था जहां एजेंट के पास अहसास पर किसी भी स्थान से रिमोट सेंसिंग करने की क्षमता भी होती है। इस संस्करण में, कार्य यात्रा लागत और सेंसिंग ऑपरेशन की लागत को कम करना है।
+एक अतिरिक्त मापदंड यह है कि बोध पर नए ज्ञान की खोज कैसे की जा रही है। सीटीपी के पारंपरिक वेरिएंट में, एजेंट आसन्न शीर्ष पर पहुंचने पर किनारे के सटीक वजन (या स्थिति) को उजागर करता है। वर्तमान में नए संस्करण का सुझाव दिया गया था जहां एजेंट के पास अनुभूति पर किसी भी स्थान से रिमोट सेंसिंग करने की क्षमता भी होती है। इस संस्करण में, कार्य यात्रा निवेश और सेंसिंग ऑपरेशन की निवेश को कम करना है।
 ==औपचारिक परिभाषा==
-हम 1989 से पेपर में अध्ययन किए गए संस्करण को परिभाषित करते हैं। यानी, लक्ष्य सबसे खराब स्थिति में प्रतिस्पर्धी अनुपात को कम करना है। यह आवश्यक है कि हम कुछ शर्तों का परिचय देकर शुरुआत करें।
+हम 1989 से पेपर में अध्ययन किए गए संस्करण को परिभाषित करते हैं। अर्थात, लक्ष्य सबसे व्यर्थ स्थिति में प्रतिस्पर्धी अनुपात को कम करना है। यह आवश्यक है कि हम कुछ शर्तों का परिचय देकर प्रारंभ करें।
-किसी दिए गए ग्राफ़ और अप्रत्यक्ष ग्राफ़ के परिवार पर विचार करें जिसे किसी दिए गए सेट से या अधिक किनारों को जोड़कर बनाया जा सकता है। औपचारिक रूप से, चलो <math>\mathcal{G}(V,E,F) = \{(V,E+F') | F' \subseteq F\}, E \cap F = \emptyset</math> जहाँ हम E को किनारों के रूप में सोचते हैं जो ग्राफ़ में होना चाहिए और F को किनारों के रूप में जो ग्राफ़ में हो सकते हैं। हम ऐसा कहते हैं <math>G \in \mathcal{G}(V,E,F)</math> ग्राफ़ परिवार का एहसास है। इसके अलावा, मान लीजिए कि W संबद्ध लागत मैट्रिक्स है <math>w_{ij}</math> शीर्ष i से शीर्ष j तक जाने की लागत है, यह मानते हुए कि यह बढ़त प्राप्ति में है।
+किसी दिए गए ग्राफ़ और अप्रत्यक्ष ग्राफ़ के वर्ग पर विचार करें जिसे किसी दिए गए समुच्चय से एक या अधिक किनारों को जोड़कर बनाया जा सकता है। औपचारिक रूप से, मान लीजिए <math>\mathcal{G}(V,E,F) = \{(V,E+F') | F' \subseteq F\}, E \cap F = \emptyset</math> जहां हम E को किनारों के रूप में सोचते हैं जो ग्राफ़ में होना चाहिए और F को किनारों के रूप में जो ग्राफ़ में हो सकते हैं। हम कहते हैं कि <math>G \in \mathcal{G}(V,E,F)</math> ग्राफ़ वर्ग का एक अनुभूति है। इसके अतिरिक्त, मान लीजिए कि W एक संबद्ध निवेश मैट्रिक्स है जहां <math>w_{ij}</math> शीर्ष i से शीर्ष j तक जाने की निवेश है, यह मानते हुए कि यह बढ़त प्राप्ति में है।
-V में किसी भी शीर्ष v के लिए, हम कॉल करते हैं <math>E_B(v,V)</math> इसके घटना किनारों को किनारे सेट बी के संबंध में वी पर सेट किया गया है। इसके अलावा, अहसास के लिए <math>G \in \mathcal{G}(V,E,F)</math>, होने देना <math>d_B(s,t)</math> ग्राफ़ में s से t तक के सबसे छोटे पथ की लागत हो। इसे ऑफ-लाइन समस्या कहा जाता है क्योंकि ऐसी समस्या के लिए एल्गोरिदम में ग्राफ़ की पूरी जानकारी होगी।
-हम कहते हैं कि रणनीति <math>\pi</math> ऐसे ग्राफ़ को नेविगेट करने के लिए मैपिंग है <math>(\mathcal{P}(E),\mathcal{P}(F),V)</math> को <math>V</math>, कहाँ <math>\mathcal{P}(X)</math> X के [[ सत्ता स्थापित ]] को दर्शाता है। हम लागत को परिभाषित करते हैं <math>c(\pi, B)</math> रणनीति का <math>\pi</math> किसी विशेष अनुभूति के संबंध में <math>G = (V,B)</math> निम्नलिखित नुसार।
+V में किसी भी शीर्ष v के लिए हम V पर किनारे सेट B के संबंध में इसके घटना किनारों को <math>E_B(v,V)</math> कहते हैं। इसके अतिरिक्त एक प्राप्ति <math>G \in \mathcal{G}(V,E,F)</math> के लिए <math>d_B(s,t)</math> ग्राफ़ में s से t तक के सबसे छोटे पथ की निवेश होगी। इसे ऑफ-लाइन समस्या कहा जाता है क्योंकि ऐसी समस्या के लिए एक एल्गोरिदम में ग्राफ़ की पूरी जानकारी होती है।
-* होने देना <math>v_0 = s, E_0 = E</math> और <math>F_0 = F</math>.
-* के लिए <math>i = 0, 1, 2, ...</math>, परिभाषित करना
+हम कहते हैं कि ऐसे ग्राफ़ को नेविगेट करने के लिए एक रणनीति <math>(\mathcal{P}(E),\mathcal{P}(F),V)</math> से <math>V</math> तक मैपिंग है जहां <math>\mathcal{P}(X)</math> X के पावरसेट को दर्शाता है। हम एक विशेष प्राप्ति <math>G = (V,B)</math> के संबंध में एक रणनीति <math>\pi</math> की निवेश <math>c(\pi, B)</math> को निम्नानुसार परिभाषित करते हैं।
+* मान लीजिए <math>v_0 = s, E_0 = E</math> और <math>F_0 = F</math>.
+* <math>i = 0, 1, 2, ...</math>, के लिए परिभाषित करना
 ** <math>E_{i+1} = E_i \cup E_B(v_i,V)</math>,
 ** <math>F_{i+1} = F_i - E_F(v_i,V)</math>, और
 ** <math>v_{i+1} = \pi(E_{i+1}, F_{i+1}, v_i)</math>.
-* यदि कोई T ऐसा मौजूद है <math>v_T = t</math>, तब <math>c(\pi, B) = \sum_{i=0}^{T-1} w_{v_i,v_{i+1}}</math>; अन्यथा चलो <math>c(\pi, B) = \infty</math>.
+* यदि कोई T ऐसा उपस्थित है <math>v_T = t</math>, तब <math>c(\pi, B) = \sum_{i=0}^{T-1} w_{v_i,v_{i+1}}</math>; अन्यथा माना <math>c(\pi, B) = \infty</math>.
+दूसरे शब्दों में, हम उन किनारों के आधार पर नीति का मूल्यांकन करते हैं जिन्हें हम वर्तमान में ग्राफ़ (<math>E_i</math>) में जानते हैं  और जिन किनारों को हम जानते हैं वे ग्राफ़ (<math>F_i</math>) में हो सकते हैं . जब हम ग्राफ़ में कदम उठाते हैं, तो हमारे नए स्थान पर पड़ने वाले किनारे हमें ज्ञात हो जाते हैं। वे किनारे जो ग्राफ़ में हैं, <math>E_i</math> जोड़ दिए जाते हैं , और चाहे किनारे ग्राफ़ में हों या नहीं, उन्हें अज्ञात किनारों के समुच्चय <math>F_i</math> से हटा दिया जाता है, . यदि लक्ष्य कभी प्राप्त नहीं होता है, तो हम कहते हैं कि हमारी निवेश अनंत है। यदि लक्ष्य प्राप्त हो जाता है, तो हम चलने की निवेश को प्रमुखता के साथ पार किए गए सभी किनारों की निवेश के योग के रूप में परिभाषित करते हैं।
-दूसरे शब्दों में, हम उन किनारों के आधार पर नीति का मूल्यांकन करते हैं जिन्हें हम वर्तमान में ग्राफ़ में जानते हैं (<math>E_i</math>) और जिन किनारों को हम जानते हैं वे ग्राफ़ में हो सकते हैं (<math>F_i</math>). जब हम ग्राफ़ में कदम उठाते हैं, तो हमारे नए स्थान पर पड़ने वाले किनारे हमें ज्ञात हो जाते हैं। वे किनारे जो ग्राफ़ में हैं, जोड़ दिए जाते हैं <math>E_i</math>, और चाहे किनारे ग्राफ़ में हों या नहीं, उन्हें अज्ञात किनारों के सेट से हटा दिया जाता है, <math>F_i</math>. यदि लक्ष्य कभी प्राप्त नहीं होता है, तो हम कहते हैं कि हमारी लागत अनंत है। यदि लक्ष्य प्राप्त हो जाता है, तो हम चलने की लागत को प्रमुखता के साथ पार किए गए सभी किनारों की लागत के योग के रूप में परिभाषित करते हैं।
+अंत में, हम कनाडाई ट्रैवलर समस्या को परिभाषित करते हैं।
+:सीटीपी उदाहरण <math>(V,E,F,s,t,r)</math> को देखते हुए, तय करें कि क्या ऐसी कोई नीति उपस्थित है <math>\pi</math> जो प्रत्येक प्राप्ति के लिए <math>(V,B) \in \mathcal{G}(V,E,F)</math> , पॉलिसी की निवेश <math>c(\pi, B)</math> ऑफ-लाइन इष्टतम <math>d_B(s, t)</math> के r गुना से अधिक नहीं है
-अंत में, हम कनाडाई यात्री समस्या को परिभाषित करते हैं।
+पापादिमित्रीउ और यान्नाकाकिस ने कहा कि यह [[ खेल सिद्धांत | खेल सिद्धांत]] को परिभाषित करता है | दो-खिलाड़ियों का खेल, जहां खिलाड़ी अपने संबंधित पथ की निवेश पर प्रतिस्पर्धा करते हैं और किनारे का समुच्चय दूसरे खिलाड़ी (प्रकृति) द्वारा चुना जाता है।
-: एक CTP उदाहरण दिया गया है <math>(V,E,F,s,t,r)</math>, तय करें कि क्या कोई नीति मौजूद है <math>\pi</math> ऐसा कि हर अहसास के लिए <math>(V,B) \in \mathcal{G}(V,E,F)</math>, लागत <math>c(\pi, B)</math> पॉलिसी का ऑफ-लाइन इष्टतम से आर गुना से अधिक नहीं है, <math>d_B(s, t)</math>.
-पापादिमित्रीउ और यान्नाकाकिस ने कहा कि यह [[ खेल सिद्धांत ]] को परिभाषित करता है|दो-खिलाड़ियों का खेल, जहां खिलाड़ी अपने संबंधित पथ की लागत पर प्रतिस्पर्धा करते हैं और किनारे का सेट दूसरे खिलाड़ी (प्रकृति) द्वारा चुना जाता है।
+==जटिलता                                                                                ==
+मूल पेपर ने समस्या की जटिलता का विश्लेषण किया और इसे पीस्पेस-पूर्ण बताया गया था। यह भी दिखाया गया कि उस स्थिति में इष्टतम पथ खोजना जहां प्रत्येक किनारे के ग्राफ़ (आई-एसएसपीपीआर) में होने की संबद्ध संभावना है, पीस्पेस- आसान किन्तु तीव्र-P कठिन समस्या है।<ref>Papadimitriou and Yannakakis, 1989, p. 148</ref> इस अंतर को पाटना ओपन समस्या थी, किन्तु तब से निर्देशित और अप्रत्यक्ष दोनों संस्करणों को पीएसपीएसीई-हार्ड दिखाया गया था।<ref>Fried, Shimony, Benbassat, and Wenner 2013</ref>
-==जटिलता==
-मूल पेपर ने समस्या की जटिलता का विश्लेषण किया और इसे PSPACE-पूर्ण बताया। यह भी दिखाया गया कि उस मामले में इष्टतम पथ खोजना जहां प्रत्येक किनारे के ग्राफ़ (i-SSPPR) में होने की संबद्ध संभावना है, PSPACE- आसान लेकिन तीव्र-P|♯P-कठिन समस्या है।<ref>Papadimitriou and Yannakakis, 1989, p. 148</ref> इस अंतर को पाटना खुली समस्या थी, लेकिन तब से निर्देशित और अप्रत्यक्ष दोनों संस्करणों को पीएसपीएसीई-हार्ड दिखाया गया।<ref>Fried, Shimony, Benbassat, and Wenner 2013</ref>
 स्टोकेस्टिक समस्या के निर्देशित संस्करण को संचालन अनुसंधान में रिकोर्स के साथ स्टोकेस्टिक शॉर्टेस्ट पाथ समस्या के रूप में जाना जाता है।
-==अनुप्रयोग==
+==अनुप्रयोग                                                                                                                                                                                                       ==
 कहा जाता है कि इस समस्या का अनुप्रयोग संचालन अनुसंधान, परिवहन योजना, कृत्रिम बुद्धिमत्ता, [[ यंत्र अधिगम ]], संचार नेटवर्क और रूटिंग में होता है। संभाव्य लैंडमार्क पहचान के साथ रोबोट नेविगेशन के लिए समस्या के प्रकार का अध्ययन किया गया है।<ref name=briggs04>{{cite journal |first1=Amy J. |last1=Briggs |first2=Carrick |last2=Detweiler |first3=Daniel |last3=Scharstein |title=लैंडमार्क-आधारित रोबोट नेविगेशन के लिए अपेक्षित सबसे छोटा पथ|journal=International Journal of Robotics Research |year=2004 |volume=23 |pages=717–718 |doi=10.1177/0278364904045467 |issue=7–8|citeseerx=10.1.1.648.3358 |s2cid=15681481 }}</ref>
-==खुली समस्याएँ==
+==ओपन समस्याएँ                                                                                                                                                                                         ==
-समस्या की उम्र और इसके कई संभावित अनुप्रयोगों के बावजूद, कई स्वाभाविक प्रश्न अभी भी खुले हैं। क्या कोई स्थिर-कारक सन्निकटन है या समस्या [[APX]]-कठिन है? क्या यह i-SSPPR #P-पूर्ण है? और भी मौलिक प्रश्न अनुत्तरित छोड़ दिया गया है: क्या इष्टतम नीति का बहुपद-आकार का विवरण है, विवरण की गणना करने के लिए आवश्यक समय को पल के लिए अलग रखा गया है?<ref>Karger and Nikolova, 2008, p. 1</ref>
+समस्या की उम्र और इसके कई संभावित अनुप्रयोगों के अतिरिक्त, कई स्वाभाविक प्रश्न अभी भी खुले हैं। क्या कोई स्थिर-कारक सन्निकटन है या समस्या [[APX|एपीएक्स]]-कठिन है? क्या यह आई-एसएसपीपीआर P-पूर्ण है? और भी मौलिक प्रश्न अनुत्तरित छोड़ दिया गया है: क्या इष्टतम नीति का बहुपद-आकार का विवरण है, विवरण की गणना करने के लिए आवश्यक समय को पल के लिए अलग रखा गया है ?<ref>Karger and Nikolova, 2008, p. 1</ref>
-==यह भी देखें==
+==यह भी देखें                                                                                                                                                                                                  ==
 * [[ग्राफ ट्रैवर्सल]]
-* [[ प्रहार का समय ]]
+* [[ प्रहार का समय | हिटिंग समय]]
-* सबसे छोटा रास्ता समस्या
+* सबसे छोटा पथ समस्या
 ==टिप्पणियाँ==

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 09:00, 5 July 2023

Contents

समस्या वर्णन

वेरिएंट

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

जटिलता

अनुप्रयोग

ओपन समस्याएँ

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 09:00, 5 July 2023

समस्या वर्णन

वेरिएंट

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

जटिलता

अनुप्रयोग

ओपन समस्याएँ

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories