-
Notifications
You must be signed in to change notification settings - Fork 1
Tour
James Bremner edited this page Feb 6, 2023
·
1 revision
This option attempts to find a path that visits every node
The first line specifies the calculation required. It must contain
format tour
| Column | Description |
|---|---|
| 1 | l for link |
| 2 | vertex name |
| 3 | vertex name |
| 4 | cost |
format tour
l 1 2 1
l 2 3 1
l 2 4 10
l 4 3 1
The algorithm is an approximation of the travelling salesman algorithm.
While it is not guaranteed to find the best possible path ( in terms of cost, visiting every vertex, not revisiting vertices ) it will usually quickly find a reasonable path.
The algorithm finds a spanning tree of the graph, then does a depth search through the tree. When it becomes 'trapped' at a leaf of the tree it will 'jump' to another unvisited leaf and continue the search from there.