Traveling Salesman
CPSC 433: Artificial Intelligence
Computer
Science
|
|
||
|
Traveling Salesman CPSC 433: Artificial Intelligence |
Computer Science |
|
See also the wikipedia article for a LOT more detail about the problem.
The traveling salesman problem is an old problem (1930!) that is very well studied. The problem is this: Given a list of cities and a list of cost/distance/difficulty between connected cities, determine the optimal route a salesman could travel to visit every one of the cites at least once, terminating with the starting city. You will recognize the input to the problem is a graph, an example of which is given at right. The graph, of course, is not necessarily fully connected. Variants of the problem include a directed graph version, where the arcs can only be followed in the direction given (eg: you can imagine an airline that has a Calgary-Edmonton-Vancouver circle route in one direction only; ie: no direct route Calgary-Vancouver).Also give a fully-specified formal search instance for
the problem:
Starting city: A
Cities: (A B C D)
Connections: ((A B 10) (A D 15) (B C 7) (B D 4) (C D 6))
 |
|
| Last updated 2013-08-31 00:00 |