Programmieraufgabe: Frage zur geforderten Laufzeitkomplexität

Moderator: Effiziente Graphenalgorithmen

Stefan1992
Mausschubser
Mausschubser
Beiträge: 45
Registriert: 20. Okt 2011 22:38

Programmieraufgabe: Frage zur geforderten Laufzeitkomplexität

Beitrag von Stefan1992 » 11. Apr 2016 16:28

Hallo,

ich habe mal wieder eine Frage zur geforderten Laufzeitkomplexität der Algorithmen. Und zwar ist gefordert, dass die Algorithmen die im Wiki angegebene Komplexität unter allen Umständen einhalten.

Ich versuche jedoch die Empfehlung aus der Vorlesung einzuhalten, die Algorithmen als Iterator zu implementieren.
In Java bedeutet das, dass die Algorithmen eine next()- und eine hasNext()-Methode implementieren müssen.
Dabei beinhaltet, zumindest nach meinem Verständnis, die next()-Methode den eigentlichen Induktionsschritt des Algorithmus und die hasNext()-Methode prüft, ob die Abbruchbedingung erfüllt ist.
Das heißt für mich: Die hasNext()-Methode kann den Zustand der Datenstruktur verändern, wohingegen die next()-Methode dies nicht tut.

Betrachtet man nun beispielsweise den Ford-Fulkerson, so wird in einem Induktionsschritt ein flusserhöhender Pfad gesucht. Die Abbruchbedingung ist, dass kein flusserhöhender Pfad mehr im Netzwerk existiert.
Um die Abbruchbedingung zu überprüfen, muss ich also auf jeden Fall noch einmal eine Tiefensuche über das Netzwerk laufen lassen. Um den Zustand der Datenstruktur allerdings nicht zu verändern, müsste ich das "lokal" prüfen, ohne den Zustand zu verändern.
Erst wenn die Überprüfung des Algorithmus ergibt, dass ein flusserhöhender Pfad existiert, sollte der Induktionsschritt (in dem erneut der Pfad gesucht wird) ausgeführt werden.

Also würde der so implementierte Algorithmus im Prinzip die Tiefensuche doppelt ausführen und somit genau genommen nicht der angegebenen Laufzeitkomplexität entsprechen.
Eine Möglichkeit wäre natürlich, einen eventuell gefundenen Pfad bei der Überprüfung der Abbruchbedingung zu speichern und bei Aufruf der next()-Methode zu verwenden.
Allerdings würde das meiner Meinung nach nicht der geforderten (Java-)Iterator-API entsprechen, da ich so unter Umständen den Zustand der Datenstruktur durch die hasNext()-Methode verändern kann.

Deshalb meine Frage: Wie genau soll die Laufzeitkomplexität eingehalten werden?


Grüße Stefan

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Programmieraufgabe: Frage zur geforderten Laufzeitkomplexität

Beitrag von Prof. Karsten Weihe » 11. Apr 2016 20:58

Stefan1992 hat geschrieben: Also würde der so implementierte Algorithmus im Prinzip die Tiefensuche doppelt ausführen und somit genau genommen nicht der angegebenen Laufzeitkomplexität entsprechen.
Eine Verdopplung der Laufzeit ergibt dieselbe Komplexität :!: :idea:

Schauen Sie noch einmal in dieses Kapitel in der GdI II hinein.

Mit "Iterator" ist im Wiki auch nicht unbedingt java.util.Iterator gemeint, sondern allgemein das Design Pattern Iterator: https://de.wikipedia.org/wiki/Iterator_(Entwurfsmuster). Vor allem die englischsprachige Seite https://en.wikipedia.org/wiki/Iterator_pattern zeigt mit der Auflistung der Realisierungen in verschiedenen Sprachen, welche Bandbreite an Designs dieses Pattern erlaubt.

Aber: Es ist keine Anforderung der Aufgabenstellung, Algorithmen als Iteratoren zu implementieren.

KW

Stefan1992
Mausschubser
Mausschubser
Beiträge: 45
Registriert: 20. Okt 2011 22:38

Re: Programmieraufgabe: Frage zur geforderten Laufzeitkomplexität

Beitrag von Stefan1992 » 12. Apr 2016 11:56

Vielen Dank für die Hinweise! :)

Antworten

Zurück zu „Effiziente Graphenalgorithmen“