Travelling salesman problem Sind alle Exakte Algorithmen schwierig zu implementieren?
Hallo ich schreibe ein Facharbeit in Informatik über Travelling salesman problem(TSP). ich muss Algorithmen vergleichen und Algorithmen implementieren. Sollte ich überhaupt Exakte Algorithmen Implementieren, weil sie Schwer sind? außer (a brute force approach).
1 Antwort
"Schwer" bedeutet im Fall des Handelsreisenden nicht dass sie "kompliziert", "schwierig" zu implementieren oder zu verstehen sind, sondern dass sie eben exponentiellen Aufwand erzeugen.
Welche Algorithmen du konkret implementieren und vergleichen sollst mußt du mit deinem Betreuer/deiner Betreuerin abstimmen.Eine Möglichkeit wäre, dass du dir verschiedene "pathologische" Beispiele heraus suchst, also Beispiele bei denen ein exakter Algorithmus tatsächlich exponentiellen Aufwand haben oder bei denen ein heuristischer Algorithmus eben keine optimale Lösung liefern. Das kannst du dann jeweils ins Verhältnis zur Lösungszeit setzen.
Das kommt nun darauf an welche exakten Algorithmen du implementierst. Aber scheinbar benötigen diese immer eine Variante der linearen Optimierung, sind also tatsächlich in der Implementierung nicht trivial. Wie bereits gesagt würde ich mich zur Eingrenzung des Themas an meine Bereuerin/meinen Betreuer wenden, dafür sind die schließlich da. Aber um mit diesen zu reden solltest du dich wenigstens in die algorithmischen Grundlagen eingearbeitet haben, d.h. du solltest wissen über was du redest. Allerdings kannst du bei einer kleinen Anzahl von Orten das Problem noch exakt modellieren und daran bereits wichtige Eigenschaften darstellen.
ich meinte mit schwer, ob generell Exakte Algorithmen z.B. 10k Zeilen von Cod benötigen. Wenn nicht dann würde ich sie nicht in meine Facharbeit mitnehmen