Traveling Salesperson (24)
Michael L. Littman
December 10th, 1998
TRAVELING SALESPERSON PROBLEM
Drilling Holes
Traveling Salesperson Problem
Hamiltonian Circuit
Hardness of HAM
Linking HAM and TSP
Dealing with NP-Completeness
APPROXIMATION
Approximation Idea
Hardness Results
Approximation Algorithm
Running Time
Analysis of Solution Quality
Other Algorithms
OPTIMAL APPROACHES
Idea
Partial-Tour Graph
Shortest Path
Heuristic Search
HEURISTIC APPROACHES
Motivation
Nearest Neighbor
Greedy
Local Search
Some Local Moves
Other Approaches
CONCLUSION
Today's Lecture
The Course
Thanks!
PRACTICE PROBLEMS
Next:
TRAVELING SALESPERSON PROBLEM
