एक वैचारिक दृष्टिकोण से, एक तालाब में पत्थर छोड़ने और लहरों को
देखने की कल्पना करें। मार्ग तालाब और पत्थर को आपकी शुरुआती स्थिति
का प्रतिनिधित्व करेंगे।
बेशक एल्गोरिदम को एन ^ 2 पथों के कुछ अनुपात को खोजना होगा
क्योंकि दूरी एन बढ़ जाती है। आप आपको स्थिति शुरू करेंगे और उस बिंदु
से सभी उपलब्ध पथों की जांच करेंगे। फिर उन पथों के अंत में बिंदुओं
के लिए रिकर्सिव कॉल करें और इसी तरह।
यदि आप पहले से ही कवर हो चुके हैं और बहुत लंबे समय तक चल रहे
पथों को छोड़कर मार्ग पर दोबारा जांच नहीं कर रहे हैं, तो पथ पर
दोबारा समर्थन न करके आप प्रदर्शन बढ़ा सकते हैं।
चींटी फेरोमोन दृष्टिकोण का उपयोग करने का एक वैकल्पिक तरीका है,
जहां चींटियां प्रारंभ बिंदु से यादृच्छिक रूप से क्रॉल करती हैं और
एक सुगंध का निशान छोड़ती हैं, जो किसी दिए गए पथ पर अधिक चींटियों को
पार करती है। यदि आप प्रारंभ बिंदु और अंत बिंदु दोनों से चींटियों
(पर्याप्त) चींटियों को भेजते हैं तो आखिरकार सबसे मजबूत सुगंध वाला
मार्ग सबसे छोटा होगा। ऐसा इसलिए है क्योंकि किसी भी समय की अवधि में
सबसे छोटा रास्ता बार-बार दौरा किया जाएगा, क्योंकि चींटियां एक समान
गति से चलती हैं।
संपादित करें @ स्पाइकी
तालाब एल्गोरिदम को कार्यान्वित करने के तरीके के बारे में एक और
स्पष्टीकरण के रूप में - संभावित डेटा संरचनाओं को हाइलाइट किया गया
है:
आपको मानचित्र को नेटवर्क के रूप में स्टोर करने की आवश्यकता होगी।
यह बस उनके बीच नोड्स और edges का एक सेट
है। नोड्स का एक सेट मार्ग का गठन करता है।
एक किनारा दो नोड्स (संभवतः एक ही नोड दोनों) में शामिल होता है, और
किनारे को पार करने के लिए cost या time
जैसे संबद्ध लागत होता है। एक किनारा या तो
द्वि-दिशात्मक या यूनी-दिशात्मक हो सकता है। संभवतः यूनी-दिशात्मक
वाले लोगों के लिए सबसे सरल और नोड्स के बीच दो तरह की यात्रा के लिए
दोहराएं (यानी ए से बी के किनारे और बी से ए के लिए एक अलग)।
उदाहरण के तौर पर कल्पना करें कि तीन रेलवे स्टेशन ऊपर की ओर इशारा
करते हुए एक समतुल्य त्रिभुज में व्यवस्थित हैं। उनके बीच प्रत्येक
आधे रास्ते में एक और तीन स्टेशन भी हैं। किनारों के साथ सभी आसन्न
स्टेशनों में शामिल हो जाते हैं, अंतिम आरेख में एक बड़े त्रिकोण के
अंदर एक उल्टा त्रिकोण होगा।
नीचे बाईं ओर से शुरू होने वाले लेबल नोड्स, ए, बी, सी, डी, ई, एफ
(शीर्ष पर एफ) के रूप में बाएं से दाएं और ऊपर जा रहे हैं।
मान लें कि किनारों को किसी भी दिशा में घुमाया जा सकता है।
प्रत्येक किनारे की लागत 1 किमी है।
ठीक है, इसलिए हम नीचे बाएं ए से शीर्ष स्टेशन एफ तक मार्ग बनाना
चाहते हैं। ऐसे कई संभावित मार्ग हैं, जिनमें स्वयं को दोहराएं, उदा।
ABCEBDEF।
हमारे पास नियमित रूप से कहना है, NextNode , जो
नोड और लागत स्वीकार करता है और प्रत्येक
नोड के लिए स्वयं को कॉल करता है, जिस पर वह यात्रा कर सकता है।
स्पष्ट रूप से अगर हम इस दिनचर्या को चलाने देते हैं तो अंततः उन
सभी मार्गों को खोजा जाएगा, जिनमें संभावित रूप से अनंत (उदाहरण के
लिए अबाबाबाब आदि) शामिल हैं। हम लागत के विरुद्ध जांच
करके ऐसा होने से रोकते हैं। जब भी हम उस नोड पर जाते हैं जिसे पहले
नहीं देखा गया था, हम उस नोड के खिलाफ से आए लागत और नोड दोनों को
डालते थे। यदि हम मौजूदा लागत के खिलाफ जांच करने से पहले नोड का दौरा
किया गया है और यदि हम सस्ता हैं तो हम नोड को अपडेट करते हैं और
(रिकर्सिंग) लेते हैं। यदि हम अधिक महंगी हैं, तो हम नोड को छोड़ देते
हैं। यदि सभी नोड्स छोड़े जाते हैं तो हम दिनचर्या से बाहर निकलते
हैं।
अगर हम अपने लक्ष्य नोड को दबाते हैं तो हम दिनचर्या से भी बाहर
निकलते हैं।
इस तरह सभी व्यवहार्य मार्गों की जांच की जाती है, लेकिन
महत्वपूर्ण रूप से केवल सबसे कम लागत वाले लोग ही हैं। प्रक्रिया के
अंत तक प्रत्येक नोड में हमारे नोड को प्राप्त करने के लिए सबसे कम
लागत होगी, जिसमें हमारे लक्षित नोड भी शामिल होंगे।
मार्ग प्राप्त करने के लिए हम अपने लक्ष्य नोड से पीछे की ओर काम
करते हैं। चूंकि हमने नोड को संग्रहित किया है, इसलिए हम लागत के साथ
आए हैं, हम बस मार्ग की ओर बढ़ने की उम्मीद करते हैं। हमारे उदाहरण के
लिए हम कुछ इस तरह खत्म हो जाएगा:
Node A - (Total) Cost 0 - From Node None
Node B - Cost 1 - From Node A
Node C - Cost 2 - From Node B
Node D - Cost 1 - From Node A
Node E - Cost 2 - From Node D / Cost 2 - From Node B (this is an
exception as there is equal cost)
Node F - Cost 2 - From Node D
तो सबसे छोटा रास्ता एडीएफ है।