回溯算法

Question

重量順序如何影響回溯算法中的計算成本？節點和搜索樹的數量是相同的，但是如果它是無序的，它會花費更多的時間，所以它正在做一些事情。

謝謝！

Answer 1

有時在回溯算法中，當你知道某個分支不是答案 - 你可以修剪它。這在遊戲代理商中非常常見，被稱爲Alpha Beta Prunning。

因此 - 當您對訪問節點重新排序時，您可以提高您的訪問速度，從而減少您訪問的實際節點數量，而不會影響答案的正確性。

還有一種可能性 - 如果沒有任何遺漏就是緩存性能。有時候樹被存儲爲數組[特別是complete trees]。數組迭代時效率最高，而不是「隨機跳躍」。重新排序可能會改變這種行爲，導致更好/更糟糕的緩存行爲。

Answer 2

回溯的本質恰恰是沒有看所有的可能性或節點（在這種情況下），但是，如果節點沒有下令是不可能的算法「修剪」一個可能的分支因爲如果元素實際上位於該分支上，則不確定。

不同於當它是一個有序樹，因爲如果所搜索的元素是更大/更小的該子樹的根，搜索到的元素是對向右或向左分別。這就是爲什麼如果樹不是有序的，那麼計算順序就等於暴力，但是，如果樹在最壞情況下是有序的，就等於暴力，但是執行的次序更小。