php - 修改Held-Karp TSP算法，不需要回原点

Question

我必须解决一个问题，我必须找到从距离矩阵开始链接所有点的最短路径。这几乎就像一个旅行商问题，除了我不需要通过返回起点来关闭我的路径。我找到了 Held-Karp algorithm (Python)很好地解决了 TSP 但总是计算返回起点的距离。所以现在它留给我 3 个问题:

1. 如果我修改我的函数而不是回到起点，至少有一种情况会产生不同的结果吗？
2. 如果对 1 的回答是肯定的，我该如何更改我的 held_karp() 函数以满足我的需要？
3. 2中没有办法，接下来我该找什么？

我已经将 held_karp() 函数从 Python 翻译成 PHP，对于我的解决方案，我很乐意使用任何一种语言。

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)];
}

如果您需要了解 every_combinations() 函数的工作原理

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;
}

Answer 1

是的，答案可以不同。例如，如果图有 4 个顶点和以下无向边:

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

最佳路径是1-2-3-4权重为1 + 1 + 1 = 3，但同一个循环的权重为1 + 1 + 1 + 100 = 103。但是，循环的权重1-3-4-2是2 + 1 + 2 + 1 = 6，这条路径的权重是2 + 1 + 2 = 5，所以最优循环和最优路径是不同的。

如果你正在寻找一条路径，而不是一个循环，你可以使用相同的算法，但你不需要将最后一条边的权重添加到起始顶点，即

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

应该是for($k = 1; $k < $nb_nodes; $k++) $res[] = [$c["($bits,$k)"][0], $k];