Immer den kleinsten Wert finden

[Zudomon]

Hallo!

Irgendwie komme ich gerade nicht so recht weiter. Ich würde gerne Objektsimplifikation einbauen und das klappt bisher auch ganz gut. Das Problem ist allerdings, dass das ganze sehr langsam läuft. Das will ich nun optimieren, aber bisher steh ich da etwas auf dem Schlauch.

Das Problem:
Ich habe eine Liste von Kanten. Für jede wird ein gewisser Wert (Kosten) berechnet, der mir angibt, wie teuer es wäre, diese zu entfernen. Nachdem eine Kante entfernt wurde, ändern sich die Kosten auch für einige andere Kanten. Mein zur Zeit trivialer Ansatz besteht darin, alle Kanten abzuklappern und die mit den geringsten Kosten zu finden. Wenn dann diese Kante entfernt und die anderen angepasst wurden, wird wieder nach dem kleinsten Kostenwert gesucht.
Das ganze endet dann in einem typischen O(n²).

Der Ansatz:
Grundlegend denke ich, dass man die Kanten erstmal sortieren sollte. Allerdings müssten dann die abgewandelten Kanten nach jedem Schritt wieder einsortiert werden.
Dieses neu einsortieren von z.B. 5 Kanten nach jedem durchlauf müsste dann aber schneller gehen, als wenn ich das komplette Array einmal nach dem kleinsten Wert abklappere. Und da liegt nun auch meine Denkblockade.
Wenn ich es über ein Array lösen würde, welches sortiert wird, dann müsste ich dieses immer auf und abrücken, um die Werte an die richtige Stelle zu bekommen, was ich mir zu langsam vorstelle.
Wenn ich es über eine verkette Liste mache, dann ist das einfügen und löschen zwar kein Problem mehr, aber ich wüsste nicht so einfach die Werte schnell an den richtigen Stellen einzufügen.

Vielleicht hat da jemand eine Lösung oder einen Ansatz, wie man da weiter kommt.

Gruß
Zudo

[joeydee]

Hört sich nach einer Aufgabe für einen Baum an, man mag mich korrigieren...

[Alexander Kornrumpf]

Priority Queue

[Zudomon]

Danke :D
Dann werde ich mich mal mit Heaps beschäftigen...

[Alexander Kornrumpf]

Tu das :)

[Brainsmith]

also, ich hab in der Uni gelernt, dass man für schnelle zugriffszeiten und bei nem sortierten System, B-Bäume benutzen sollte.
Die Breite der Bäume sollte sich aus der Wurzel der Anzahl der voraussichtlich zu verwaltenden Kanten bestimmen.
Da wärst du bei den Bäumen in Sachen geschwindigkeit bei O(log n)
Natürlich alles vorausgesetzt, ich vertue mich net.. ^^

Alternativ könntest du die Kanten von vornherein sortiert in eine verwaltungsliste einfügen und müsstest immer nur den kleinsten aufrufen.

Ich weiß leider nicht, inwiefern die Neuberechnung der Knoten abläuft, aber das sollte schonmal das Problem mit den kleinsten kantenkosten verbressern

[Zudomon]

Diese Priority Queques werden ja soweit ich nun weiß, als binäre Heaps dargestellt, was ja letztendlich binäre Bäume sind. Die haben den Vorteil, dass sie direkt als Array darstellbar sind und dieselbe Zugriffszeit fürs löschen und einfügen haben O(log n).

Die Kanten selbst darf ich leider nicht manipulieren, weil ich ebenfalls Cachelisten brauche, die mir sagen, welche Kanten von welchen Vertices aus erreichbar sind. Also ich denke, ich bin nun auf dem richtigen Wege.... irgendwo haben sich noch ein paar Bugs verkrochen.... aber sobald ich die habe, gibs auch endlich wieder was neues von mir :D

[Zudomon]

Kann man aus einem binären Heap auch einen Wert wieder löschen? Ich finde nur Methoden zum einfügen und um den kleinsten/größten Schlüssel wieder zu entfernen.

[Alexander Kornrumpf]

http://de.wikipedia.org/wiki/Fibonacci-Heap

Alle Operationen mit Laufzeitangaben und Vergleich zum Binomial Heap.

[Lord Delvin]

Wenn du heaps verwendest, dann solltest du, wenns dir wirklich auf die Laufzeit ankommt mehrere probieren(was ja deinen code nicht ändert), da sich da einige Abweichungen bei kleinen Stückzahlen gegen die (amortisierten) Laufzeiten ergeben können, wenn du ihn nach einem gleichbleibenden Muster verwendest.
Eigentlich sollten sich auch vollständige und getestete Implementierungen für binär, binomial und fibonacci Heaps finden.
Gruß