please provide me with correct answer Suppose the following

please provide me with correct answer

Suppose the following adjacency matrix is given for the Traveling Salesman Problem: The number of distinct tours (beginning and ending in v_1) is 25 24 16 10 D[3][4] = 7 1 18 24 (Recall that the notation D(f)(A) means the minimum distance from vertex v_1 to vertex v_1 passing through each of the vertices in the set A exactly once. D[3]{[4, 5]} = 16 20 27 31

Solution

Travelling Salesman Problem:

A salesman is assigned n cities to visit. The problem is to use the route that is of minimum length (or cost, or time). Since a complete cycle is involved, it makes no difference which city is taken to be the starting city. Starting from a given city, the salesman will have before him a total of (n – 1)! different sequences of possible routes (given that the total number of cities be n and each city be visited once only)   

Since in this problem, there are 5 cities, the number of distinct tours is (5 – 1)! = 4! = 24

1. Correct option is (b) 24

2. The ideal route in this case is given below:

3 4 1

Cost of transportation = 7 + 11 = 18

Correct option is (c) 18

3. The possible routes are:

3 4 5 1 (Cost of transportation = 7 + 2 + 18 = 27)

3 5 4 1 Cost of transportation = 16 + 4 + 11 = 31)

Min (27, 31) = 27

Correct option is (c) 27

(Answer)