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.
Pseudocode (slides 25 and 26):
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] < min)
min = C(S, m) + matrix[m, k];
}
}
return min;
}
Yes, I think it should fill an arraylist with solution rather than returning a value...
I have modified it (thanks for the advice) and it looks like:
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 < RouteCost)
{
RouteCost = MinimumCostThroughNodeAndAnotherNode;
}
}
}
return RouteCost;
}
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?
I think its the double recursion that is going on. First in the
if
statement -if (C(S, m)
... then again right below it.min = C(S, m)
... that should be called once, tested for min, then set min.If your foreach loop is changed like this: