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