Algorithmus Kantenfolge über alle Knoten, Anzahl durchlaufenen Knoten minimal |
| 19.01.2017, 13:52 | EinBaumimWald | Auf diesen Beitrag antworten » |
| Algorithmus Kantenfolge über alle Knoten, Anzahl durchlaufenen Knoten minimal Hallo, ich suche einen Algorithmus, der eine Kantenfolge über alle Knoten findet. Die Knoten dürfen auch öfters besucht werden. Allerdings soll die Anzahl an Knoten in der Folge minimal sein. Meine Ideen: Ist es möglich einen Algorithmus für die Suche eines Hamiltonpfades umzuschreiben und wenn ja wie? Und geht es vielleicht auch besser als die Laufzeit für einen Hamiltonpfad von ? Freue mich über jede Hilfe! |
||
| 21.01.2017, 11:12 | Elvis | Auf diesen Beitrag antworten » |
Ist es nicht egal, ob man die zu besuchenden Orte "Orte" oder "Knoten" nennt ? Für Orte gibt es schon Lösungen : traveling salesman problem algorithmus |
||
| 21.01.2017, 12:06 | EinBaumimWald | Auf diesen Beitrag antworten » |
Nein, das macht keinen Unterschied, allerdings geht das TSP davon aus, das ein Ort nur einmal besucht wird. Man kann allerdings zunächst eine Breitensuche für jeden Knoten laufen lassen und die kürzesten Wege von jedem zu jedem anderen Knoten speichern und danach neue Kanten der länge des kürzesten Weges hinzufügen. Jetzt lässt sich das TSP auch hier anwenden. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
