修改Held-Karp TSP算法，这样我们就不需要回到原点了

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 :

1. Could at least one situation have a different result if I modify my function not to get back to the starting point?
2. If the answer to 1 is yes, how could I alter my held_karp() function to fit my needs?
3. 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[\$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)"] + \$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)"] + \$matrix[\$k], \$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;
}

\$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;
}
• 写回答
• 好问题 提建议
• 关注问题
• 收藏
• 邀请回答

1条回答默认 最新

• dongxiaoxing3058 2017-04-14 16:25
已采纳

Yes, the answer can be different. For instance, if the graph has 4 vertices and the following undirected edges:

1-2 1
2-3 1
3-4 1
1-4 100
1-3 2
2-4 2

The optimal path is 1-2-3-4 with a weight 1 + 1 + 1 = 3, but the weight of the same cycle is 1 + 1 + 1 + 100 = 103. However, the weight of the cycle 1-3-4-2 is 2 + 1 + 2 + 1 = 6 and the weight of this path is 2 + 1 + 2 = 5, so the optimal cycle and the optimal path are different.

If you're looking for a path, not a cycle, you can use the same algorithm, but you don't need to add the weight of the last edge to the start vertex, that is

for(\$k = 1; \$k < \$nb_nodes; \$k++) \$res[] = [\$c["(\$bits,\$k)"] + \$matrix[\$k], \$k];

should be for(\$k = 1; \$k < \$nb_nodes; \$k++) \$res[] = [\$c["(\$bits,\$k)"], \$k];

评论
解决 无用
打赏 举报