/ / TSP mit Backtracking - Algorithmus lösen

TSP mit Backtracking-Algorithmus lösen

Ich habe versucht herauszufinden, wie man TSP mittels Backtracking lösen kann. Wie berechnen Sie die "Kosten"?

Matrix:

∞   20  30  10  11
15  ∞   16  4   2
3   5   ∞   2   4
19  6   18  ∞   3
16  4   7   16  ∞

Kosten:

3 -> 1 -> 2 -> 4 -> 5 -> 3 cost = 37
3 -> 1 -> 2 -> 5 -> 4 -> 3 cost = 59
3 -> 1 -> 5 -> 2 -> 4 -> 3 cost = 50
3 -> 1 -> 5 -> 4 -> 2 -> 3 cost = 62
3 -> 1 -> 4 -> 2 -> 5 -> 3 cost = 28
3 -> 1 -> 4 -> 5 -> 2 -> 3 cost = 36

Ich habe herausgefunden, dass es mit Bellmans Gleichung berechnet wurde, ich weiß es einfach nicht der Weg, es zu tun.

Jede Hilfe würde sehr geschätzt werden!

Antworten:

2 für die Antwort № 1

Um die Kosten zu berechnen, müssen Sie nur alle Edge-Kosten zusammenfassen. Zum Beispiel für die Route 3 -> 1 -> 2 -> 4 -> 5 -> 3, Dies ergibt

(3,1) => 3
(1,2) => 20
(2,4) => 4
(4,5) => 3
(5,3) => 7
------------
sum      37

Sie müssen also im Wesentlichen eine erste Beispielroute generieren und deren Kosten berechnen. Sobald Sie dies getan haben, wissen Sie, dass die resultierenden Kosten eine optimale Lösung sein könnten.

Wenn du jetzt zurückschreitest und du kommst in eineSituationen, in denen Sie bereits höhere Kosten haben, wissen Sie, dass dies nicht zu einer besseren Route führt und Sie somit aufhören können, Routen zu erkunden und einen Schritt zurück zu gehen.

Beispiel: Sie haben bei Ihrem ersten Lauf die Route entdeckt 1 2 3 4 5 6 7 8 9 1 ergibt Kosten von 40. Jetzt, bei einem Backtracking-Schritt, haben Sie den Anfang einer Route: 1 2 4 5 6 ... und sehen, dass bis zu diesem Punkt die Kosten bereits sind 41. Das heißt, wenn Sie eine Route beginnend mit diesen Nummern erkunden, haben Sie eine Route, die mehr als kostet 40 und somit nicht optimal! Jetzt können Sie einfach Alle Routen verwerfen mit ... anfangen 1 2 4 5 6.

(Beachten Sie, dass die obigen Überlegungen nur bei Verwendung nichtnegativer Edge-Costs funktionieren!)