Immer den kleinsten Wert finden

Design Patterns, Erklärungen zu Algorithmen, Optimierung, Softwarearchitektur
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.
Antworten
Benutzeravatar
Zudomon
Establishment
Beiträge: 2139
Registriert: 25.03.2009, 08:20
Kontaktdaten:

Immer den kleinsten Wert finden

Beitrag von 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
Establishment
Beiträge: 724
Registriert: 23.04.2003, 15:29
Kontaktdaten:

Re: Immer den kleinsten Wert finden

Beitrag von joeydee »

Hört sich nach einer Aufgabe für einen Baum an, man mag mich korrigieren...
Alexander Kornrumpf
Moderator
Beiträge: 1755
Registriert: 25.02.2009, 14:37

Re: Immer den kleinsten Wert finden

Beitrag von Alexander Kornrumpf »

Priority Queue
Benutzeravatar
Zudomon
Establishment
Beiträge: 2139
Registriert: 25.03.2009, 08:20
Kontaktdaten:

Re: Immer den kleinsten Wert finden

Beitrag von Zudomon »

Danke :D
Dann werde ich mich mal mit Heaps beschäftigen...
Alexander Kornrumpf
Moderator
Beiträge: 1755
Registriert: 25.02.2009, 14:37

Re: Immer den kleinsten Wert finden

Beitrag von Alexander Kornrumpf »

Tu das :)
Benutzeravatar
Brainsmith
Establishment
Beiträge: 109
Registriert: 04.09.2009, 13:52
Echter Name: Fabbo

Re: Immer den kleinsten Wert finden

Beitrag von 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
Benutzeravatar
Zudomon
Establishment
Beiträge: 2139
Registriert: 25.03.2009, 08:20
Kontaktdaten:

Re: Immer den kleinsten Wert finden

Beitrag von 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
Benutzeravatar
Zudomon
Establishment
Beiträge: 2139
Registriert: 25.03.2009, 08:20
Kontaktdaten:

Re: Immer den kleinsten Wert finden

Beitrag von 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
Moderator
Beiträge: 1755
Registriert: 25.02.2009, 14:37

Re: Immer den kleinsten Wert finden

Beitrag von Alexander Kornrumpf »

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

Alle Operationen mit Laufzeitangaben und Vergleich zum Binomial Heap.
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 238
Registriert: 05.07.2003, 11:17

Re: Immer den kleinsten Wert finden

Beitrag von 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ß
Antworten