Iterative Divide und Conquer-Algorithmen

Ich versuche, einen Algorithmus mit dem Divide-and-Conquer-Ansatz aber mit einem iterativen Algorithmus (dh keine Rekursion) zu erstellen.Iterative Divide und Conquer-Algorithmen

Ich bin verwirrt, wie man die Schleifen nähert.

Ich muss meine Probleme in kleinere Subprobleme aufteilen, bis ich einen Basisfall treffe. Ich nehme an, das ist immer noch wahr, aber ich bin mir nicht sicher, wie ich (ohne Rekursion) die kleineren Teilprobleme verwenden kann, um das viel größere Problem zu lösen.

Zum Beispiel versuche ich, einen Algorithmus zu finden, der das nächstgelegene Punktepaar findet (im eindimensionalen Raum - obwohl ich beabsichtige, dies auf höhere Dimensionen zu verallgemeinern). Wenn ich eine Funktion nearest_pair (L) hätte, wobei L eine Liste ganzzahliger Koordinaten in ÷ ist, wie könnte ich dann einen ITERATIVE-Algorithmus finden, der dieses Problem lösen kann?

(Ohne Beschränkung der Allgemeinheit ich Python verwende)

Quelle

2016-11-23 TimelordViktorious

Gibt es einen bestimmten Grund, warum Sie Rekursion nicht (nicht?) Verwenden können? – Gormador

Ich muss einen iterativen Algorithmus für eine in der Klasse gegebene Zuweisung entwerfen. Ich kenne die Lösung dafür rekursiv (unter Verwendung von D & C) und ich bin zuversichtlich, dass ich dies in iterativen Code übersetzen kann und die Tatsache nutzen kann, dass der D & C-Ansatz in O (nlogn) -Zeit im Gegensatz zu O (n^2) ist. – TimelordViktorious

Das habe ich befürchtet. Vor allem im Rahmen einer Klassenaufgabe werden Sie hier keine Hilfe bekommen, bevor Sie zeigen, was Sie bereits in Codes ausprobiert haben, obwohl ich verstehe, dass Ihre Frage eher allgemeine Programmierung als eine Sprache im Besonderen ist. Ach, du wirst irgendwann Code schreiben müssen und das wird konkrete Antworten beeinflussen ... Obwohl es scheint, jemand hat geantwortet! Du scheinst Glück zu haben! – Gormador

Der günstige Weg, um alle rekursiven Algorithmus in einem iterativen Algorithmus zu drehen ist, um die rekursive Funktion zu übernehmen, es in einer Schleife setzen, und Ihre eigenen Stack verwenden. Dies eliminiert den Funktionsaufruf-Overhead und das Speichern nicht benötigter Daten auf dem Stapel. Dies ist jedoch in der Regel nicht der "beste" Ansatz ("am besten" hängt von dem Problem und Kontext.)

Sie haben Ihr Problem formuliert, es klingt wie die Idee ist, die Liste in Unterlisten zu brechen, zu finden das jeweils nächste Paar und dann das nächste Paar aus diesen beiden Ergebnissen. Um dies iterativ zu tun, denke ich, dass ein besserer Ansatz als die oben erwähnte generische Methode ist, anders herum zu beginnen: Schauen Sie sich Listen der Größe 3 an (es gibt drei Paare zum Anschauen) und arbeiten Sie sich von dort hoch. Beachten Sie, dass Listen der Größe 2 trivial sind.

Schließlich, wenn Ihre Koordinaten Ganzzahlen sind, sind sie in Z (eine viel kleinere Teilmenge von R).

Quelle

2016-11-23 17:32:07 Andrew

Ja, du hast Recht. Ich meinte Z. :-). Ich hatte über die Stack-Idee nachgedacht, aber weil ich versuche, diesen Algorithmus zu analysieren und seine Richtigkeit zu beweisen, möchte ich diese Idee vermeiden. Wenn ich verstehe, was Sie meinen, schlagen Sie einen Bottom-up-Ansatz vor? – TimelordViktorious

@TimelordViktorious Ja; Aus einer algorithmischen Perspektive kann man auch eine andere Reihenfolge wählen, aber ich finde die iterativen Versionen sinnvoller von unten nach oben (und das wird tendenziell bessere Cacheleistung haben, da Sie mehr Zeit mit der Arbeit an Elementen verbringen, die sich im Speicher befinden) – Andrew

Um dies zu tun, sollte ich einfach einen linearen Scan durch eine Liste L machen und Partitionen von 3 Elementen gleichzeitig betrachten (oder 2), bis ich das Ende der Liste erreiche. Ist das richtig in der Art, wie ich das tue? – TimelordViktorious

Iterative Divide und Conquer-Algorithmen

Antwort

Verwandte Themen