Immer den kleinsten Wert finden
Verfasst: 25.09.2009, 12:58
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
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