🙍🏼 ☝🏿 🧚🏻 सबसे छोटे के लिए मायने रखता है: बीएफएस 0-1 ❣️ 🔵 👟

शुभ दोपहर, प्यारे खाबरोवित्स!
पिछली पोस्टों में, हमने पहले से ही दो एल्गोरिदम के बारे में बात की थी जिसके साथ आप भूलभुलैया के माध्यम से रास्ता पा सकते हैं: DFS और BFS । कोई भी जो हमारी भूलभुलैया का थोड़ा और मजाक करना चाहता है, कृपया, बिल्ली के नीचे।

समस्या का नया बयान

टेलीपोर्ट को भूलभुलैया में जोड़ें - अब कुछ कमरों में ऐसे उपकरण होंगे जिनका उपयोग करके आप शून्य समय में दूसरे कमरे में जा सकते हैं।
या, औपचारिक रूप से बोलते हुए, अब प्रत्येक किनारे को उसके साथ जाने के समय के साथ चिह्नित किया जाता है - यह 0 या 1 है। लेकिन लक्ष्य एक ही है - प्रारंभिक शीर्ष से अंतिम एक तक समय के दृष्टिकोण से सबसे छोटा रास्ता खोजने के लिए।

निर्णय

हम पहले से ही एक एल्गोरिथ्म जानते हैं जो आपको सबसे छोटा रास्ता खोजने की अनुमति देता है - यह बीएफएस है, क्रमशः, मैं इसके आधार पर कुछ प्रकार के एल्गोरिदम के साथ आना चाहता हूं।

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

कार्यान्वयन

यह माना जाता है कि ग्राफ को वेक्टर <वेक्टर <जोड़ी <int, int >>> किनारों के रूप में दर्शाया गया है, जहां किनारों [v] किनारों की एक सरणी है जो वर्टेक्स v से उत्पन्न होती है। प्रत्येक किनारे को संख्याओं की एक जोड़ी द्वारा परिभाषित किया जाता है - अंतिम शीर्ष और वजन की संख्या।
वर्टिस की दूरी सदिश <int> d में संग्रहित की जाती है, और शुरू में इस एरे के सभी तत्व ऐसे नंबर्स होते हैं, जो सभी वर्टिकल से दूरी से बड़े माने जाते हैं।

BFS 0-1

void BFS() { //  deque<int> q; q.push_back(start); d[start] = 0; //   while (!q.empty()) { //   int v = q.front(); q.pop_front(); //      for (int i = 0; i < (int)edges[v].size(); ++i) { //      if (d[edges[v][i].first] > d[v] + edges[v][i].second) { //         d[edges[v][i].first] = d[v] + edges[v][i].second; //   ,    if (edges[v][i].second == 0) { q.push_front(edges[v][i].first); } //  -   else { q.push_back(edges[v][i].first); } } } } }

एल्गोरिथ्म की जटिलता

प्रत्येक किनारे और प्रत्येक शीर्ष के लिए एक निरंतर संख्या में क्रियाएं की जाती हैं, इसलिए एल्गोरिथ्म की समय जटिलता O (V + E) है।
प्रत्येक शीर्ष, स्पष्ट रूप से, डेक को दो बार से अधिक नहीं मिलता है, इसलिए एल्गोरिथ्म द्वारा उपयोग की जाने वाली स्मृति की मात्रा हे (वी) है।

सबसे छोटे के लिए मायने रखता है: बीएफएस 0-1

समस्या का नया बयान

निर्णय

कार्यान्वयन

एल्गोरिथ्म की जटिलता

More articles: