TRAVELING SALESMAN PROBLEM
Insertion Algorithms
(Rosenkrantz, Stearns, Lewis)
Arbitrary Insertion
- Step 1. Start with a sub-graph consisting of node i only.
- Step 2. Find node r such that cir
is minimal and form sub-tour i-r-i.
- Step 3. Arbitrarily select node r not in the
sub-tour to enter the sub-tour.
Note that the first two steps are identical to nearest insertion
Worst Case Behavior:
Number of Computations:
The arbitrary insertion algorithm is
.
