Question

John and Robyn promised their three sons that they will each get to pick one spot within 500 miles of their home in City A to visit on their vacation. Scott chooses to visit City B so that he can visit some of the popular attractions there. Jacob chooses City C so he can visit a museum. Jevon chooses City D so that he can visit his grandparents. The approximate distances between these cities are as​ follows, City A to City B is 296 ​miles, City A to City C is 206 ​miles, City A to City D is 79 ​miles, City B to City C is 497 ​miles, City B to City D is 241 ​miles, and City C to City D is 281 miles.

Requried:
a. Represent this traveling salesman problem with a complete, weighted graph showing the distances on the appropriate edges. Lot Arepresent City A, B represent City B, C represent City C, and represent City D.
b. Use the brute force method to determine the shortest route for the family to complete their vacation.

Answer 1

A) Weighted graph is attached

B) Shortest routes are;

1. A → C → B → D → A

2. A → D → B → C → A

Explanation:

A) We are told their home is in City A. So that's where any journey will begin from.

Furthermore we are told that;

City A to City B = 296 ​miles

City A to City C = 206 ​miles

City A to City D = 79 ​miles

City B to City C = 497 ​miles

City B to City D = 241 ​miles

City C to City D = 281 miles.

I have attached an image of the weighted graph showing the distances on the appropriate edges.

B) We want to find the shortest route using Brute force method. The brute force method is by solving a particular problem by checking all the possible cases/routes to get the desired result we are looking for.

In this case, the desired result is the shortest route for the family to complete their vacation. So, i have attached a diagram showing the different routes via brute force method.

From the brute force method, the shortest length route is 1023 miles and this routes are from Cities;

1. A → C → B → D → A

2. A → D → B → C → A