Given a graph of n vertices, determine the minimum cost path to start at a given vertex and travel to each other vertex exactly once, returning to the starting vertex. In some versions, the starting and ending points are different and fixed, and all other points have to be visited exactly once from start to end. A standard way to solve these problems is to try all possible orders of visiting the n points, which results in a run-time of O(n!). To calculate cost using Dynamic Programming, we need to establish recursive relation in terms of sub-problems. Let us define a term C(S, i) be the cost of the minimum cost path visiting each vertex in set S exactly once, starting at 1 and ending at i. We start with all subsets of size 2 and calculate C(S, i) for all subsets where S is the subset, then we calculate C(S, i) for all subsets S of size 3 and so on. Note that 1 must be present in every subset. So the algorithm is like below - If size of S is 2, then S must be {1, i}, C(S, ...
Comments
Post a Comment