Bidirectional search
द्विदिशात्मक खोज एक ग्राफ खोज एल्गोरिथ्म है जो एक निर्देशित ग्राफ में प्रारंभिक शीर्ष से लक्ष्य शीर्ष तक का सबसे छोटा रास्ता खोजता है। यह एक साथ दो खोजों को चलाता हैः एक प्रारंभिक अवस्था से आगे, और एक गोल से पीछे, जब दोनों मिलते हैं तो रुकते हैं। इस दृष्टिकोण का कारण यह है कि कई मामलों में यह तेज हैः उदाहरण के लिए, खोज समस्या जटिलता के एक सरलीकृत मॉडल में जिसमें दोनों खोज शाखा कारक बी के साथ एक पेड़ का विस्तार करती हैं, और शुरू से लक्ष्य तक की दूरी डी है, दोनों खोजों में से प्रत्येक में जटिलता ओ (बी. डी./2) (बिग ओ संकेतन में) है, और इन दो खोज समय का योग ओ (बी. डी.) जटिलता से बहुत कम है जो शुरुआत से लक्ष्य तक एकल खोज के परिणामस्वरूप होगी। एंड्रयू गोल्डबर्ग और अन्य लोगों ने डिज्क्स्ट्रा के एल्गोरिदम के द्विदिश संस्करण के लिए सही समाप्ति शर्तों की व्याख्या की। जैसा कि ए * खोज में, द्वि-दिशात्मक खोज को लक्ष्य (आगे के पेड़ में) या शुरू से (पीछे के पेड़ में) शेष दूरी के एक अनुमानक अनुमान द्वारा निर्देशित किया जा सकता है। यह एक द्वि-दिशात्मक ह्यूरिस्टिक खोज एल्गोरिदम को डिजाइन और लागू करने वाला पहला व्यक्ति था। शुरू से निकलने वाले खोज पेड़ और लक्ष्य नोड्स समाधान स्थान के बीच में मिलने में विफल रहे। बी. एच. एफ. एफ. ए. एल्गोरिदम ने इस दोष चैंपियो (1977) को ठीक किया। एक स्वीकार्य ह्यूरिस्टिक का उपयोग करते हुए एक-दिशात्मक ए * एल्गोरिथ्म द्वारा पाए गए समाधान की पथ लंबाई सबसे कम होती है; वही गुण डी चैंपियो (1983) में वर्णित बी. एच. एफ. एफ. ए. 2 द्वि-दिशात्मक ह्यूरिस्टिक संस्करण के लिए है। बी. एच. एफ. एफ. ए. 2 में, अन्य बातों के अलावा, बी. एच. एफ. एफ. ए. की तुलना में अधिक सावधानीपूर्वक समाप्ति स्थितियाँ हैं। एक द्विदिशात्मक शोध खोज किसी राज्य से दूसरे राज्य में एक राज्य अंतरिक्ष खोज है, जो एक साथ आने-जाने के लिए खोज करती है। यह ऑपरेटरों की एक वैध सूची देता है जिसे यदि लागू किया जाता है तो यह हमें देगा। हालांकि ऐसा लग सकता है कि ऑपरेटरों को रिवर्स खोज के लिए व्युत्क्रम योग्य होना चाहिए, किसी भी नोड को देखते हुए, केवल ऐसे मूल नोड्स के सेट को खोजने में सक्षम होना आवश्यक है कि प्रत्येक मूल नोड्स से कुछ वैध ऑपरेटर मौजूद हों। इसकी तुलना अक्सर मार्ग-खोज क्षेत्र में एक तरफा सड़क से की जाती हैः दोनों दिशाओं में यात्रा करने में सक्षम होना आवश्यक नहीं है, लेकिन सड़क के अंत में खड़े होने पर सड़क की शुरुआत को एक संभावित मार्ग के रूप में निर्धारित करना आवश्यक है। इसी तरह, उन किनारों के लिए जिनमें व्युत्क्रम चाप हैं (अर्थात। दोनों दिशाओं में जाने वाले चाप) यह आवश्यक नहीं है कि प्रत्येक दिशा समान लागत की हो। विपरीत खोज हमेशा व्युत्क्रम लागत का उपयोग करेगी (अर्थात। आगे की दिशा में चाप की लागत)। अधिक औपचारिक रूप से, यदि मूल के साथ एक नोड है, तो, से से लागत के रूप में परिभाषित किया जाता है। (Auer Kaindl 2004) शब्दावली और संकेतन एक खोज वृक्ष का शाखा कारक नोड से नोड तक जाने से जुड़ी लागत, मूल से नोड तक की लागत, नोड और लक्ष्य के बीच की दूरी का अनुमान लक्ष्य अवस्था (कभी-कभी, कार्य के साथ भ्रमित नहीं होना चाहिए) वर्तमान खोज दिशा बताता है। परंपरा के अनुसार, आगे की दिशा के लिए 1 और पीछे की दिशा के लिए 2 के बराबर है (केडब्ल्यूए 1989) विपरीत खोज दिशा (यानी) खोज वृक्ष की दिशा d. यदि, जड़ है, यदि, जड़ के पत्ते हैं (कभी-कभी के रूप में संदर्भित)। यह इस समूह से है कि विस्तार के लिए एक नोड चुना जाता है। द्विदिशात्मक खोज में, इन्हें कभी-कभी खोज 'फ्रंटियर्स' या 'वेवफ्रंट्स' कहा जाता है, जो इस बात का उल्लेख करता है कि जब किसी खोज को ग्राफिक रूप से दर्शाया जाता है तो वे कैसे दिखाई देते हैं। इस रूपक में, एक 'टकराव' तब होता है, जब विस्तार चरण के दौरान, एक तरंग के सामने से एक नोड में विरोधी तरंग के सामने उत्तराधिकारी पाए जाते हैं। के गैर-पत्ती वाले नोड्स। इस समूह में खोज दृष्टिकोण द्वारा पहले से ही देखे गए नोड्स शामिल हैं द्विदिशात्मक एल्गोरिदम को मोटे तौर पर तीन श्रेणियों में विभाजित किया जा सकता हैः फ्रंट-टू-फ्रंट, फ्रंट-टू-बैक (या फ्रंट-टू-एंड), और परिधि खोज (कैंडल कैन्ज 1997)। ये ह्यूरिस्टिक की गणना करने के लिए उपयोग किए जाने वाले कार्य से भिन्न होते हैं। फ्रंट-टू-बैक एल्गोरिदम विपरीत खोज वृक्ष के बीच और मूल के ह्यूरिस्टिक अनुमान का उपयोग करके एक नोड के मूल्य की गणना करते हैं। फ्रंट-टू-बैक तीन श्रेणियों में सबसे सक्रिय रूप से शोध किया गया है। वर्तमान में सबसे अच्छा एल्गोरिथ्म (कम से कम पंद्रह पहेली क्षेत्र में) BiMAX-BS * F एल्गोरिथ्म है, जिसे ऑयर और कैंडल (ऑयर, कैंडल 2004) द्वारा बनाया गया है। फ्रंट-टू-फ्रंट एल्गोरिदम और कुछ उपसमुच्चय के बीच ह्यूरिस्टिक अनुमान का उपयोग करके एक नोड के मूल्य की गणना करते हैं। विहित उदाहरण बी. एच. एफ. एफ. ए. (बाइडायरेक्शनल ह्यूरिस्टिक फ्रंट-टू-फ्रंट एल्गोरिदम) का है, जहाँ फ़ंक्शन को वर्तमान नोड और विरोधी मोर्चे पर नोड्स के बीच सभी ह्यूरिस्टिक अनुमानों के न्यूनतम के रूप में परिभाषित किया गया है। या, औपचारिक रूप सेः जहां एक स्वीकार्य रिटर्न (यानी। अधिक अनुमान नहीं लगाना) और नोड्स के बीच की दूरी का अनुमानक अनुमान। फ्रंट-टू-फ्रंट अत्यधिक कम्प्यूटेशनल मांग से पीड़ित है। हर बार जब किसी नोड को खुली सूची में रखा जाता है, तो उसके मूल्य की गणना की जानी चाहिए। इसमें विरोधी समूह में प्रत्येक नोड से एक ह्यूरिस्टिक अनुमान की गणना करना शामिल है, जैसा कि ऊपर वर्णित है। सेट सभी डोमेन के लिए आकार में तेजी से बढ़ते हैं। संदर्भ। .. .. .. ग्राफ एल्गोरिदम खोज एल्गोरिदम