I have to solve a problem where I had to find the shortest path to link all points starting from a distance matrix. It's almost like a Traveling Salesman Problem except I do not need to close my path by returning to the starting point. I found the Held-Karp algorithm (Python) that solves the TSP very well but always computes distances returning to the starting point. So now it leaves me with 3 questions :
- Could at least one situation have a different result if I modify my function not to get back to the starting point?
- If the answer to 1 is yes, how could I alter my held_karp() function to fit my needs?
- It there is no way in 2, what should I look for next?
I have translated the held_karp()
function from Python to PHP, and for my solution I'd be happy to use either language.
function held_karp($matrix) {
$nb_nodes = count($matrix);
# Maps each subset of the nodes to the cost to reach that subset, as well
# as what node it passed before reaching this subset.
# Node subsets are represented as set bits.
$c = [];
# Set transition cost from initial state
for($k = 1; $k < $nb_nodes; $k++) $c["(".(1 << $k).",$k)"] = [$matrix[0][$k], 0];
# Iterate subsets of increasing length and store intermediate results
# in classic dynamic programming manner
for($subset_size = 2; $subset_size < $nb_nodes; $subset_size++) {
$combinaisons = every_combinations(range(1, $nb_nodes - 1), $subset_size, false);
foreach($combinaisons AS $subset) {
# Set bits for all nodes in this subset
$bits = 0;
foreach($subset AS $bit) $bits |= 1 << $bit;
# Find the lowest cost to get to this subset
foreach($subset AS $bk) {
$prev = $bits & ~(1 << $bk);
$res = [];
foreach($subset AS $m) {
if(($m == 0)||($m == $bk)) continue;
$res[] = [$c["($prev,$m)"][0] + $matrix[$m][$bk], $m];
}
$c["($bits,$bk)"] = min($res);
}
}
}
# We're interested in all bits but the least significant (the start state)
$bits = (2**$nb_nodes - 1) - 1;
# Calculate optimal cost
$res = [];
for($k = 1; $k < $nb_nodes; $k++) $res[] = [$c["($bits,$k)"][0] + $matrix[$k][0], $k];
list($opt, $parent) = min($res);
# Backtrack to find full path
$path = [];
for($i = 0; $i < $nb_nodes - 1; $i++) {
$path[] = $parent;
$new_bits = $bits & ~(1 << $parent);
list($scrap, $parent) = $c["($bits,$parent)"];
$bits = $new_bits;
}
# Add implicit start state
$path[] = 0;
return [$opt, array_reverse($path)];
}
In case you need to know how the every_combinations() function works
function every_combinations($set, $n = NULL, $order_matters = true) {
if($n == NULL) $n = count($set);
$combinations = [];
foreach($set AS $k => $e) {
$subset = $set;
unset($subset[$k]);
if($n == 1) $combinations[] = [$e];
else {
$subcomb = every_combinations($subset, $n - 1, $order_matters);
foreach($subcomb AS $s) {
$comb = array_merge([$e], $s);
if($order_matters) $combinations[] = $comb;
else {
$needle = $comb;
sort($needle);
if(!in_array($needle, $combinations)) $combinations[] = $comb;
}
}
}
}
return $combinations;
}