Solution Found!
A social worker starts from her home A, must visit clients at B, C, D, and E (in any
Chapter 6, Problem 30(choose chapter or problem)
A social worker starts from her home A, must visit clients at B, C, D, and E (in any order), and return home to A at the end of the day. The graph in Fig. 40 shows the distance (in miles) between the five locations. Find an optimal tour for this TSP, and give its cost in miles. (Hint: The edge AC is part of an optimal tour.)
Questions & Answers
QUESTION:
A social worker starts from her home A, must visit clients at B, C, D, and E (in any order), and return home to A at the end of the day. The graph in Fig. 40 shows the distance (in miles) between the five locations. Find an optimal tour for this TSP, and give its cost in miles. (Hint: The edge AC is part of an optimal tour.)
ANSWER:Step 1 of 3
Finding the optimal tour for TSP:
To find an optimal tour, the social worker finds the cheapest way to start at her home A and visits the clients B, C, D, E and then returns back to home A at the end of the day.
For that we find the Hamilton circuit in a complete graph that has the smallest overall weight.
Now, using nearest neighborhood algorithm finding the smallest overall weight shown below in the image:
