There are N towns T1 TN and a cost matrix C cy where cy is

There are N towns T_1, ...., T_N and a cost matrix C = {c_y} where c_y is the cost of moving directly from T_i to T_j for i, j = 1, ...., N and c_u = 0 for I = 1, ..., N. Starting from T_1 it is required to find the lowest cost route to T_N, including as many intermediate cities on the route as are required. Show how this problem may be formulated in terms of Dynamic Programming and show how the method of successive approximations (e.g. the N point problem) may be used to provide a solution. Taking care to provide the necessary equations and also describe the necessary steps.

Solution

Here the given below procedure is to be followed to acheive the required lowest cost route from T1 to TN...

Dynamic programming is defined as breaking down the given problem into sub problems and finding the solution for these sub problems result in the solution of given main problem...

In the above given problem we will first consider the movement of T1 to the next node with least cost to move and this process is continued untill we reach the TN. Here first all the neighbours of given node is considered and then compare the cost values for all these edges and one with lower value node is considered and given as input and the above process is repeated untill we reach the final state...

Backtracking methodology can also be included in these problem solving methodology and compare all the computed cost routes and one with minimum value can be selected as output route