Hallo,
Kann mir jemand einen Tipp geben, wie ich mit möglichst geringem Aufwand den schnellsten Weg für den „Weihnachtsmann“ finden kann. Ich habe es bis jetzt mit dem Verfahren aus dem Skript versucht und schreibe mich an den Entfernungsmatrizen fast tot (und das in den Weihnachtsferien). Es muss doch auch einen einfacheren Weg geben, oder??
Vielen Dank schon mal und einen fleißigen Weihnachtsmann….;-)
Da das Branch-and-Bound-Verfahren im schlechtesten Fall exponentiellen Aufwand erfordert, kannst Du das Pech haben, sehr viele Matrizen erstellen zu müssen.Das Problem gilt als NP-vollständig, so daß derjenige, der Dir eine "einfache" Lösung geben könnte, wohl in den Olymp der theoretischen Informatik aufstiege.
Da wirst Du wohl die Zeit und den Aufwand investieren müssen.
Aber freue Dich, denn "Greedy" geht schneller.(Weil eine einmal getroffene Entscheidung nicht rückgängig gemacht wird.)
Frohes Fest, Dirk
Ich kann mir irgendwie auch nicht vorstellen, dass es es Sinn und Zweck der Aufgabe sein soll, über die Feiertage nur irgendwelche Tabellen (das sind ja nun nicht gerade wenige!!!) auszufüllen. Auch die Punktverteilung steht absolut nicht im Verhältnis zum Aufwand![img]
http://www.fb18.de/gfx/8.gif[/img][img]
http://www.fb18.de/gfx/6.gif[/img]
Es muss doch einen anderen Weg geben!?
Unser Übungsgruppenleiter schwärmte von Prolog. Damit soll es wesentlich einfacher gehen. habe aber noch nicht herausgefunden wie?!
Es muss doch einen anderen Weg geben!?
Der Weg ist hier das Ziel, nicht das ermittelte Resultat!!
heißt das, ein Ermitteln des Weges mittels einer branch and bound-Implementierung (z.B. in Prolog) ist nicht geeignet? Aber wenn selbst ein Übungsgruppenleiter dies empfiehlt, sollte das doch auch ok sein!
Wenn Du nicht nur das Verfahren verstanden hast, sondern es überdies auch noch in ein Programm umwandelst, dann hat der Aufgabenzettel seinen Sinn mehr als erfüllt.
Grundsätzlich sollen, so wie die Hausaufgaben in der Schule, die Übungsaufgaben der Vertiefung und Verfestigung des Verständnisses der in den Vorlesungen vermittelten Inhalte dienen.
Guten Rutsch, Dirk
Tach,
kann ich für den Greedy auch den Dijkstra-Algorithmus aus P3 nutzen?
Danke….
versteh ich das richtig, dass wir nun doch die ganzen matrizen aufzeichnen sollen?
Tach,
kann ich für den Greedy auch den Dijkstra-Algorithmus aus P3 nutzen?
Danke….
Nun, ist es denn so, daß beim Dijkstra-Alg eine einmal getroffene Entscheidung nicht mehr revidiert wird (was doch Greedy ausmacht), oder kann es vielleicht vorkommen, daß Du aufgrund einer neuen Erkenntnis einen bislang vorgesehenen Pfad verwirfst?
O.K., er ist nicht wirklich un-Greedy, da ja nur Zwischenentscheidungen verworfen werden, aber so richtig Greedy ist er für mich nicht wirklich.
Gruß, Dirk
versteh ich das richtig, dass wir nun doch die ganzen matrizen aufzeichnen sollen?
Theorinix schrieb doch: "Der Weg ist das Ziel!"
Ist dann noch irgendetwas unklar?
Das einzige, was wohl akzeptabel wäre, ist diese Idee, ein Programm zu schreiben, welches dem Rechenknecht die Arbeit aufhalst. Aber ist das wirklich weniger Mühe?
@alter Sack: deine Antworten helfen nicht wirklich weiter. Eigentlich ist er greedy, aber irgendwie auch doch nicht…Hää??? Kann sich dazu vielleicht noch jemand anderes äußern?
Äußerung:
bei Dijkstra wird in jedem Schritt eine Kante endgültig bearbeitet
(dies wird nie wieder zurückgenommen wie bei Backtracking,
dem einzig mir bekannten Gegenbeispiel ;) ),
also sehr deutlich (wenn auch nicht in Reinform) greedy
5 Punkte für eine Aufgabe mit der Komplexität von 2^17 find ich scheisse. Da kann mir keiner erzählen, dass der Programmieraufwand nicht weniger ist, als den Quatsch auf Papier zu kritzeln oder in Tabellen zu tippen.
