1
$\begingroup$

According to this recursion formula for dynamic programming (Held–Karp algorithm), the minimum cost can be found. I entered this code in C ++ and this was achieved (neighbor vector is the same set and v is cost matrix):

recursion formula :

C(i,S) = min { d(i,j) + C(j,S-{j}) }

my code :

#include <iostream>
#include <vector>
#define INF 99999
using namespace std;
vector<vector<int>> v{ { 0, 4, 1, 3 },{ 4, 0, 2, 1 },{ 1, 2, 0, 5 },{ 3, 1, 5, 0 } };
vector<int> erase(vector<int> v, int j)
{
    v.erase(v.begin() + j);
    vector<int> vv = v;
    return vv;
}
int TSP(vector<int> neighbor, int index)
{
    if (neighbor.size() == 0)
        return v[index][0];
    int min = INF;
    for (int j = 0; j < neighbor.size(); j++)
    {
        int cost = v[index][neighbor[j]] + TSP(erase(neighbor, j), neighbor[j]);
        if (cost < min)
            min = cost;
    }
    return min;
}
int main()
{
    vector<int> neighbor{ 1, 2, 3 };
    cout << TSP(neighbor, 0) << endl;
    return 0;
}

In fact, the erase function removes the element j from the set (which is the neighbor vector)

I know about dynamic programming that prevents duplicate calculations (like the Fibonacci function) but it does not have duplicate calculations because if we draw the tree of this function we see that the arguments of function (i.e. S and i in formula and like the picture below) are never the same and there is no duplicate calculation. My question is, is this time O(n!)?

picture :enter image description here If yes,why? This function is exactly the same as the formula and it does exactly the same thing. Where is the problem? Is it doing duplicate calculations?

$\endgroup$
4
  • $\begingroup$ Your tree contains several nodes which have the same label. Currently all of these nodes are leaves, but if you try larger $n$ you'll get such nodes on other levels. $\endgroup$ Dec 14, 2020 at 13:06
  • $\begingroup$ If you implement the Held–Karp recursion without memoization, the complexity would be proportional to $n!$. If you use memoization, it goes down to $O(n^2 2^n)$. $\endgroup$ Dec 14, 2020 at 13:08
  • $\begingroup$ @YuvalFilmus I did not understand what you said. Isn't it necessary to calculate the tree + comparisons to get the minimum? What is the problem with this method? What is the need for memoization? $\endgroup$
    – Satar
    Dec 14, 2020 at 13:36
  • $\begingroup$ The problem with your method is that it doesn't take advantage of duplicate subproblems. $\endgroup$ Dec 14, 2020 at 13:42

1 Answer 1

1
$\begingroup$

The full recursion tree for your problem has as root $(1,\{2,\ldots,n\})$. The children of a node $(i,S)$ are $(j,S \setminus \{j\})$, where $j$ ranges over all elements of $j$. Nodes with $S = \emptyset$ have no children.

Let us annotate each node in the tree by its "history". Instead of annotating each node by an index and a set, we annotate it with a sequence and a set. The root is $(1;\{2,\ldots,n\})$. The children of a node $(a;S)$ are $(a,j;S \setminus \{j\})$ for all $j \in S$. For example, if $n = 3$ then the nodes are:

  1. $(1;\{2,3\})$.
  2. $(1,2;\{3\})$.
  3. $(1,3;\{2\})$.
  4. $(1,2,3;\emptyset)$.
  5. $(1,3,2;\emptyset)$.

A node $(a_1,\ldots,a_m;S)$ in the new tree corresponds to the node $(a_m,S)$ in the original tree. Conversely, each node $(a,S)$ corresponds to nodes $(1,a_2,\ldots,a_{m-1},a;S)$, where $m = n - |S|$ and $\{1,a_2,\ldots,a_{m-1},a\} = \overline{S}$. There are $(n-2-|S|)!$ ways to choose $a_2,\ldots,a_{m-1}$, and so the node $(a,S)$ appears $(n-2-|S|)!$ times in the original tree.

This shows that the full recursion tree for your problem does contain duplicates.

$\endgroup$
4
  • $\begingroup$ Thanks, I got it.The only problem is that it calculates duplicates, right?isnt there any other problem? And that this code does not count as duplicates when the number of S members is 3? $\endgroup$
    – Satar
    Dec 14, 2020 at 18:04
  • $\begingroup$ It’s a big problem, with a dramatic effect on the running time. $\endgroup$ Dec 14, 2020 at 18:57
  • $\begingroup$ That's right- if the size of S is 3, we don't have duplicate calculations, right? $\endgroup$
    – Satar
    Dec 14, 2020 at 19:16
  • $\begingroup$ There are duplicate leaves. $\endgroup$ Dec 14, 2020 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.