Python - Teilen und erobern

Beim Teilen und Erobern wird das vorliegende Problem in kleinere Unterprobleme unterteilt, und dann wird jedes Problem unabhängig gelöst. Wenn wir die Teilprobleme weiter in noch kleinere Teilprobleme aufteilen, erreichen wir möglicherweise ein Stadium, in dem keine weitere Aufteilung möglich ist. Diese "atomaren" kleinstmöglichen Unterprobleme (Brüche) werden gelöst. Die Lösung aller Unterprobleme wird schließlich zusammengeführt, um die Lösung eines ursprünglichen Problems zu erhalten.

Im Großen und Ganzen können wir verstehen divide-and-conquer Ansatz in einem dreistufigen Prozess.

Teilen / Brechen

Dieser Schritt beinhaltet das Aufteilen des Problems in kleinere Unterprobleme. Unterprobleme sollten einen Teil des ursprünglichen Problems darstellen. Dieser Schritt verwendet im Allgemeinen einen rekursiven Ansatz, um das Problem zu teilen, bis kein Unterproblem mehr teilbar ist. In diesem Stadium werden Unterprobleme atomarer Natur, stellen jedoch immer noch einen Teil des eigentlichen Problems dar.

Erobern / Lösen

Dieser Schritt erhält viele kleinere Teilprobleme, die gelöst werden müssen. Auf dieser Ebene werden die Probleme im Allgemeinen als eigenständig „gelöst“ betrachtet.

Zusammenführen / kombinieren

Wenn die kleineren Teilprobleme gelöst sind, werden sie in dieser Phase rekursiv kombiniert, bis sie eine Lösung des ursprünglichen Problems formulieren. Dieser algorithmische Ansatz funktioniert rekursiv und Conquer & Merge-Schritte arbeiten so nahe, dass sie als eins angezeigt werden.

Beispiele

Das folgende Programm ist ein Beispiel für divide-and-conquer Programmieransatz, bei dem die binäre Suche mit Python implementiert wird.

Implementierung der binären Suche

Bei der binären Suche nehmen wir eine sortierte Liste von Elementen und suchen nach einem Element in der Mitte der Liste. Wenn der Suchwert mit dem Mittelwert in der Liste übereinstimmt, schließen wir die Suche ab. Andernfalls wird die Hälfte der Liste der Elemente entfernt, indem wir je nach Wert des gesuchten Elements auswählen, ob mit der rechten oder linken Hälfte der Liste fortgefahren werden soll. Dies ist möglich, da die Liste sortiert ist und viel schneller als die lineare Suche ist. Hier teilen wir die gegebene Liste und erobern, indem wir die richtige Hälfte der Liste auswählen. Wir wiederholen diesen Ansatz, bis wir das Element finden oder daraus schließen, dass es in der Liste nicht vorhanden ist.

def bsearch(list, val):

    list_size = len(list) - 1

    idx0 = 0
    idxn = list_size
# Find the middle most value

    while idx0 <= idxn:
        midval = (idx0 + idxn)// 2

        if list[midval] == val:
            return midval
# Compare the value the middle most value
        if val > list[midval]:
            idx0 = midval + 1
        else:
            idxn = midval - 1

    if idx0 > idxn:
        return None
# Initialize the sorted list
list = [2,7,19,34,53,72]

# Print the search result
print(bsearch(list,72))
print(bsearch(list,11))

Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:

5
None