Traveling Salesman Problem: Branch-and-Bound-Verfahren |
11.02.2011, 23:00 | LittleX1 | Auf diesen Beitrag antworten » |
Traveling Salesman Problem: Branch-and-Bound-Verfahren ich hoffe ich habe die richtige Kategorie erwischt. Ich brauche eure Hilfe. Es geht um oben genanntes Thema. Folgendes: Die Aufgabe ist es mit dem Branch-and-Bound-Verfahren die optimale Rundreise zu finden. Jetzt ist eine Kostenmatrix gegeben, diese wird erst als relaxiertes Zuordnungsproblem gelöst womit wir die untere Schranke (d.h. die minimal möglichen Kosten) bekommen. Davon ausgehend suche ich jetzt nach dem Element, mit dem größten Mindestumweg, der mir entstehen würde wenn ich es weglassen würde. Beispiel: Das relaxierte Zuordnungsproblem ergibt folgenden Rundweg und Kostenmatrix: Jetzt wäre das Element 13 in der Kostenmatrix das mit dem größten Umweg. Was sind jetzt meine Branches, nach denen ich aufspalte? a) Alle RR mit 1-3 und ohne 3-1 b) Alle RR ohne 1-3 und ohne 3-1 Ich verstehe nicht, wann ich den Rückweg (3-1) auch sperren muss und wann nicht. Es steht leider nirgends in meinen Unterlagen drin. In manchen Beispielen wird der Rückweg auch gesperrt, bei manchen nicht. Könnt ihr mir da helfen? Ich hoffe ich habe mich verständlich ausgedrückt. Viele Grüße LittleX1 |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|