早期在分支定界算法中確定無望的分支

Question

我必須設計一個分支定界算法，每次在笛卡爾平面上解決圖的最佳巡視。我已經得到了一個暗示，即在運行時早些時候識別無望的分支會合成一個運行速度「快一百倍」的程序。我有這樣的想法，假設連接到開始/結束節點的最短邊將是巡迴中的第一個或最後一個邊，但是一個薄菱形圖證明了其他情況。有沒有人對如何消除這些無望的分支有想法，或者有關這方面的參考？

基本上，是否有更好的方法可以更好地分解解決方案的子集，而不僅僅是按字典順序排列，例如。第一個分支包含並排除邊緣a-b，第二個分支包含並排除分支a-c

Answer 1

因此，在您的分支定界算法中，您可以查看可能的位置，然後以某種方式跟蹤它們以後再做。

爲了使這更有效，你可以做兩件事情：

1. 寫一個更好的結合計算器。換句話說，想出一個更準確地確定邊界的算法。這將導致花費在路徑上的時間變得很差。
2. 而不是使用堆棧來跟蹤事情，使用隊列。不使用隊列，而是使用按約束排序的優先級隊列（堆），例如，看起來最好的東西放在堆的頂部，而那些看起來不好的東西放在底部。

Answer 2

最近鄰居是一個簡單的算法。分支定界只是一個優化循環，另外你需要一個子問題求解器。我認爲最近鄰居也是分支定界算法。相反，我會研究單純形算法。這是一種線性編程算法。另外還有切割算法來解決tsp。