distances are known from a number of cities. A traveler due from one of them, visiting each city exactly once and return to the starting point having the lowest total travel distance possible.
this problem is to find the path with less weight cycles of a weighted graph through all the vertices and return to the original vertex.
Solution First, we propose the solution of the problem as a series of decisions to verify the principle of optimal. The idea will be to build a search solution by successive minimum runs of size 1, 2, 3, etc.
Representing the problem through a graph G = (V, A), and L is its adjacency matrix, each traveler's journey from vertex v1 is formed by an arc (v1, vk) for some vertex vk belongs to V-{v1} and a path from v1 to vertex vk.
But if the trip is also great to be optimal the path of the vertex v1 vk, as if it were not arrive at a contradiction. If it were not there a better way and including it in the original route would get a better way than the optimum, which is impossible. Thus, it meets the principle of optimal .
then consider recurrence relationship. To this end, we call D (vi, S) to the minimum path length from vertex vi passes through all vertices of set S and returns to the vertex vi. The solution to the traveling salesman problem is given then by D (v1, v1-{V}):
Generalizing to start the tour from any vertex:
Note the difference between the strategy of this algorithm and we try to design the following two techniques greedy (see chapter 4.4 of the previous problem.) In the greedy algorithm has to choose one of the possible options at each step, once taken, or discarded, "and not be seen ever again. Are algorithms which have no "history", and therefore does not always work. However, the dynamic programming solution to the overall problem is constructed in another way: from the optimal solutions for smaller problems.
However, the design here has made a serious drawback: its implementation using a data structure that allows reuse
calculations. This structure should contain the intermediate solutions necessary for the computation of D (v1, v1-{V}), but these are too.
In fact, the table must have n rows and 2n columns, as this is the cardinal part of the set V, which are all possibilities that can take the second parameter of D in its definition.
So yes there is a solution to the traveling salesman problem using dynamic programming, but not only fails to improve the efficiency of the classic version by Turning Back (see next chapter), but also offers an improvement in terms of simplicity implementation.
More information
Dynamic Programming 
0 comments:
Post a Comment