Save
Decision Mathematics 1
Chapter 5 - The Travelling Salesman Problem
Save
Share
Learn
Content
Leaderboard
Learn
Created by
Toby Harrington
Visit profile
Cards (6)
Classical TSP
=
Visit each vertex exactly once
Practical TSP
=
Visit each vertex at least once
To Find
Initial
Upper
Bound
=
2x weight
of
MST
To Find
Better Upper
Bounds
=
Add Shortcuts to the MST
To Find a
Lower Bound
=
Weight
of
RMST
+
2 shortest edges
of
removed vertex
To Find Upper
Bound
=
Nearest Neighbour Algorithm
(for
di-graphs
complete this
vertically
)
