Programmierung » ClassPad 300 » Basic » Travelling Salesman Problem
Travelling Salesman Problem
Der Travelling Salesman soll eine Rundreise durch alle Städte machen, ohne eine doppelt zu besuchen und am Ende am Startpunkt ankommen. Für die Verbindungen zwischen den Städten ist eine Kosten-Matrix gegeben.
Zum Beispiel:
| A | B | C | D | |
| A | 0 | 10 | 8 | 15 |
| B | 1 | 0 | 7 | 8 |
| C | 4 | 13 | 0 | 4 |
| D | 15 | 2 | 5 | 0 |
Diese Matrix enthält die Kosten, um von einem Ort zu einem anderen zu gelangen. Zum Beispiel: Von Ort A zu Ort C zu gelangen, kostet 8. Von Ort C zu Ort A hingegen kostet nur 4.
Das Problem kann nun mit Branch & Bound gelöst werden. Dabei werden, von einem beliebigen Startpunkt ausgehend,
schrittweise der Pfad mit den geringsten Kosten verfolgt:
Die Lösung ist also A-C-D-B-A mit den Kosten 15.
Das Programm macht das selbe: Es hält jedoch die Pfade in einer Tabelle, aus der die Pfade (und der Baum) einfach zu rekonstruieren sind. Die oberste Zeile enthält die Kosten für den Pfad darunter. Die Pfade sind spaltenweise abgespeichert.
| 17 | 18 | 21 | 15 | 15 |
| 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 3 | 3 | 4 |
| 3 | 4 | 2 | 4 | 0 |
| 0 | 0 | 0 | 2 | 0 |
| 0 | 0 | 0 | 1 | 0 |