Chapter 6, Problem 54E

A robotic laser must drill holes on five sites (A, B, C, D, and E) in a microprocessor chip. At the end, the laser must return to its starting position A and start all over. $\underset{\_}{\text{Figure}6-49}$ shows the time (in seconds) it takes the laser arm to move from one site to another. In this TSP, a tour is a sequence of drilling locations starting and ending at A.

a. Find the cheapest-link tour and its length.

b. Given that the tour A, D, B, E, C, A is an optimal tour, find the relative error of the cheapest-link tour found in (a).

	A	B	C	D	E
A	$\ast$	$1.2$	$0.7$	$1.0$	$1.3$
B	$1.2$	$\ast$	$0.9$	$0.8$	$1.1$
C	$0.7$	$0.9$	$\ast$	$1.2$	$0.8$
D	$1.0$	$0.8$	$1.2$	$\ast$	$0.9$
E	$1.3$	$1.1$	$0.8$	$0.9$	$\ast$

$Figure6-49$