修改Held-Karp TSP算法，所以我們不需要返回原點

Question

我必須解決一個問題，我必須找到從距離矩陣開始鏈接所有點的最短路徑。這幾乎就像旅遊推銷員問題，除非我不需要通過回到起點來關閉我的路線。我發現Held-Karp algorithm（Python）很好地解決了TSP問題，但總是計算返回到起點的距離。所以現在它留下了3個問題：

1. 如果我修改我的函數不能回到起點，至少有一種情況會有不同的結果嗎？
2. 如果對1的回答是肯定的，我怎麼能改變我的held_karp（）函數以適應我的需求？
3. 2，沒有辦法，接下來應該找什麼？

我已經將Python的held_karp()函數翻譯成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];