समान कोड वाले एल्गोरिदम जो विभिन्न कंटेनरों पर लागू होने पर विभिन्न उपयोगी लक्ष्यों को प्राप्त कर सकते हैं

ब्रेड-पहली खोज और गहराई-पहली खोज दो एल्गोरिदम हैं जो समान हैं, उनके द्वारा किए गए कार्यों को छोड़कर, और वे डेटा संरचना का उपयोग करते हैं।

पहले चौड़ाई खोजो:

q := queue
q.append(root node of tree)
while q is not empty:
    n := q.pop()
    if n is the node being searched for:
        return n
    if n has children:
        c := children of node
        for i in c:
            q.push(i)

गहराई पहली खोज:

s := stack
s.append(root node of tree)
while s is not empty:
    n := s.pop()
    if n is the node being searched for:
        return n
    if n has children:
        c := children of node
        for i in c:
            s.push(i)

क्या कोई अन्य एल्गोरिदम (या डेटा संरचनाएं) हैं जो इस तरह काम करती हैं?

0
@ मार्सिन जब तक मैंने बोरुवका के एल्गोरिदम को गलत समझा नहीं है, वे इस बात के संबंध में अलग हैं कि वे क्या काम करते हैं, जबकि मेरा मतलब था कि उन्होंने क्या उपयोग किया था।
जोड़ा लेखक rlms, स्रोत
शायद इस प्रश्न को "समान एल्गोरिदम" के रूप में संदर्भित किया जा सकता है जो विभिन्न कंटेनर पर लागू होने पर विभिन्न उपयोगी लक्ष्यों को प्राप्त कर सकता है। "
जोड़ा लेखक Michael, स्रोत
ठीक है, बीएफएस और प्राइम एक जैसे हैं, वे दोनों ग्राफ पर काम करते हैं, और पेड़ का उत्पादन करते हैं! :)
जोड़ा लेखक Leeor, स्रोत
"दो एल्गोरिदम जो समान हैं, उनके द्वारा किए गए कार्यों को छोड़कर, और वे डेटा संरचना का उपयोग करते हैं"। Quicksort और Boruvka के एल्गोरिदम के बारे में कैसे? मुझे लगता है कि आप इस मानदंड को परिशोधित करना चाहते हैं।
जोड़ा लेखक Marcin, स्रोत
हाँ। इसलिए मेरी टिप्पणी।
जोड़ा लेखक Marcin, स्रोत
मुझे @sweeneyrod का अर्थ मिलता है - यदि आप कतार और स्टैक दोनों के लिए एक ही चर नाम का उपयोग करते हैं, तो "कंटेनर" कहें, बीएफएस के डीएफएस == कार्यान्वयन के कार्यान्वयन, कोड की पहली पंक्ति को बार दें। यह वास्तव में दिलचस्प है कि एक ही कोड आपको दो अलग-अलग एल्गोरिदम देता है। हालांकि मुझे किसी अन्य उदाहरण के बारे में पता नहीं है।
जोड़ा लेखक Adam Kurkiewicz, स्रोत

2 उत्तर

एल्गोरिदम का एक निरंतर परिवार है, प्राइम-डिजस्ट्रा, जो अंतराल [0,1] में पैरामीटर पर निर्भर करता है। जब पैरामीटर 0 होता है तो आपको प्राइम एल्गोरिदम मिलता है; जब पैरामीटर 1 होता है तो आपको डिजस्ट्रा एल्गोरिदम मिलता है।

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

0
जोड़ा

एक जो दिमाग में आता है वह है डिजस्ट्रा का ग्राफ खोज एल्गोरिदम और ए *। वे अनिवार्य रूप से वही हैं, इसके अलावा लूप का अगला पुनरावृत्ति कैसे चुना जाता है - डिजस्ट्रा पहले चौड़ाई है - आपको निकटतम लक्ष्य खोजने की अनुमति देता है और ए * हेरिस्टिक गहराई है जो आपको कम से कम पुनरावृत्तियों के साथ एक लक्ष्य खोजने की अनुमति देता है (सबसे छोटी राशि दीवार घड़ी का समय)।

असल में, मैंने दोनों को एक ही कोड के साथ कार्यान्वित किया है जो आपको सूची में अगला नोड चुनने के लिए उपयुक्त कॉलबैक की आपूर्ति करके ए * या डिजस्ट्रा (या वास्तव में डी * या अन्य एल्गोरिदम) चलाने की इजाजत देता है।

0
जोड़ा