title: Travelling salesman dynamic programming implementation
body: <p>So I was implementing a travelling salesman algorithm in C# using the dynamic programming approach, but after studying the well-known pseudocode I learned quite nothing. At least I think so. Nevertheless, here's a glimpse of my code, I would be glad if someone would help me in explaining that C(S,k) function. I think I get what it does, but I'm not quite sure if mine version does what it needs to do.</p>
  
  <p><a href="http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf" rel="nofollow">Pseudocode (slides 25 and 26)</a>:</p>
  
  <pre><code>class TSP
  {
     public int cols;
     public int[,] matrix;
     public ArrayList solution;
     (...)
  
  }
  
  public int C(ArrayList S, int k)
  {
     int min = int.MaxValue;
  
     if (S.Count == 2)
        min = matrix[0, k];
     else
     {
        foreach (int m in S)
        {
           S.RemoveAt(k);
           if (C(S, m) + matrix[m, k] &lt; min)
              min = C(S, m) + matrix[m, k];
        }
     }
     return min;
  }
  </code></pre>
  
  <p>Yes, I think it should fill an arraylist with solution rather than returning a value...</p>
  
  <p>I have modified it (thanks for the advice) and it looks like:</p>
  
  <pre><code>public int MinimumRouteCostThroughNode(ArrayList RestNodes, int Node)
  {
     int RouteCost = int.MaxValue;
  
     if (RestNodes.Count == 2)
     {
         RouteCost = matrix[0, Node];
     }
     else
     {
         RestNodes.Remove(Node);
         ArrayList CopyOfRestNodes = new ArrayList(RestNodes);          
         foreach (int AnotherNode in RestNodes)
         {
             int MinimumCostThroughNodeAndAnotherNode = MinimumRouteCostThroughNode(CopyOfRestNodes, AnotherNode) + matrix[AnotherNode, Node];
             if (MinimumCostThroughNodeAndAnotherNode &lt; RouteCost)
             {
                 RouteCost = MinimumCostThroughNodeAndAnotherNode;
             }
         }
     }
     return RouteCost;
  }
  </code></pre>
  
  <p>When I debug the program it seems to be doing fine, however the RouteCost is each time being over-written and I don't know how can I get a variable (that would stay the same in every recursive? If not then does it mean that I need to make a global variable or pass it in the definition of a function? Or is there another way? </p>