मेरा प्रश्न इस प्रकार है: विभिन्न स्रोतों के मुताबिक, डिजस्ट्रा का एल्गोरिदम कुछ भी नहीं बल्कि समान लागत खोज का एक रूप है। हम जानते हैं कि डिजस्ट्रा के एल्गोरिदम को स्रोत और सभी गंतव्यों (एकल-स्रोत) के बीच सबसे छोटा रास्ता मिल जाता है। हालांकि, हम स्टार्ट और एक गोलाल राज्य के बीच सबसे छोटा रास्ता खोजने के लिए हमेशा डिजस्ट्रा को संशोधित कर सकते हैं (जब लक्ष्य प्राथमिकता कतार से पॉप किया जाता है, हम बस रुकते हैं); लेकिन ऐसा करने से, सबसे खराब स्थिति परिदृश्य अभी भी स्टार्ट से अन्य सभी नोड्स तक सबसे छोटा रास्ता ढूंढ रहा है (मान लीजिए कि लक्ष्य ग्राफ में सबसे दूर नोड है)।डिजस्ट्रा के एल्गोरिदम बनाम समान लागत खोज (समय कॉम्प्लेक्सिटी)
हम एक मिनट प्राथमिकता ढेर का उपयोग कर डिज्कस्ट्रा एल्गोरिथ्म लागू करते हैं तो चलने का समय हे (वी लॉग वी + ई) है, जहां ई किनारों और वी की संख्या कोने की संख्या है किया जाएगा।
चूंकि वर्दी लागत खोज डिजस्ट्रा (थोड़ा अलग कार्यान्वयन) जैसा ही है, तो यूसीएस का चलने का समय डिजस्ट्रा के समान होना चाहिए, है ना? हालांकि, मेरी एआई कक्षा के अनुसार, वर्दी लागत खोज सबसे बुरी स्थिति में घातीय है, और इसमें ओ (बी 1 + [सी */ε]) लेता है, जहां सी * इष्टतम समाधान की लागत है। (बी शाखाकरण कारक है)
अलग-अलग चलने वाले समय के दौरान दोनों एल्गोरिदम समान कैसे हो सकते हैं? क्या चलने का समय वही है, लेकिन जिस तरह से हम इसे देखते हैं वह अलग है?
मैं तुम्हारी मदद की :) :) आप
चलो ग्राफ़ को सीमित करने के लिए चिपकते हैं (शायद बड़े पैमाने पर, लेकिन अभी भी अंतिम)। तो मैं कैसे साबित कर सकता हूं कि दोनों एल्गोरिदम में एक ही चलने वाला समय है? – John
@ जॉन: जब तक आप दूसरे को नहीं पाते, तब तक एल्गोरिदम के छद्म कोड को फिर से लिखकर। यह मुश्किल हो सकता है क्योंकि डिजस्ट्रा को आम तौर पर पूरी तरह से स्मृति में संग्रहीत परिमित ग्राफ के लिए प्रस्तुत किया जाता है, लेकिन संभावित रूप से असीमित लोगों के लिए यूसीएस एज पीढ़ी के कार्यों के रूप में प्रतिनिधित्व करता है। –
मैं जो कहता हूं उससे सहमत हूं, लेकिन मेरे मामले में, यहां मैं जो साबित करना चाहता हूं: शहरों का नक्शा (एक ग्राफ) दिया गया है, मैं साबित करना चाहता हूं कि दोनों एल्गोरिदम में इष्टतम समाधान खोजने के लिए एक ही समय जटिलता है – John