TRAVELLING SALESMAN PROBLEM USING DYNAMIC PROGRAMMING
TRAVELLING SALESMAN PROBLEM USING DYNAMIC PROGRAMMING IN WHICH THE NODE CONSIST OF THE COST AND THE TIME THAT IS REQUIRED TO TRAVEL PATH FROM ONE NODE TO OTHERS WHICH CONSIST OF THE FOLLOWING CONDITIONS :-
1. BEST DISTANCE WITH THE TIME AND PATH
2. BEST TIME WITH THE DISTANCE(COST) ANT D PATH
3. BEST TIME AS WELL AS DISTANCE WITH PATH
_______________________________________________________________________________________________________________________The traveling salesman problems abide by a salesman and a set of cities. The salesman has to visit every one of the cities starting from a certain one and to return to the same city. The challenge of the problem is that the traveling salesman needs to minimize the total length of the trip.
Initially, all cities are unvisited, and the visit starts from the city s. We assume that the initial travelling cost is equal to \mathsf{0}. Next, the TSP distance value is calculated based on a recursive function. If the number of cities in the subset is two, then the recursive function returns their distance as a base case.
On the other hand, if the number of cities is greater than is greater than 2 , then we’ll calculate the distance from the current city to the nearest city, and the minimum distance among the remaining cities is calculated recursively.
Finally, the algorithm returns the minimum distance as a TSP solution.
BEST TIME AS WELL AS DISTANCE WITH PATH IS CALCULATED USING THE BELOW FORMULA OF SPEED :{ { { 0, 0 }, { 10, 12 }, { 15, 6 }, { 20, 10 } },
{ { 5, 8 }, { 0, 0 }, { 9, 3 }, { 10, 7} },
{ { 6, 5 }, { 13, 20 }, { 0, 0 }, { 12, 6 } },
{ { 8, 15 }, { 8, 11 }, { 9, 12 }, { 0, 0 } } };
{ { { 0, 0 }, { 4, 7 }, { 1, 1.2 }, { 3, .1765 } },
{ { 4, 2 }, { 0, 0 }, { 2, 2.3 }, { 1, 1.67} },
{ { 1, 0.24 }, { 2, 1.2 }, { 0, 0 }, { 5, 0.23 } },
{ { 3, 3.3 }, { 1, 1.1 }, { 5, 3.2 }, { 0, 0 } } }