algorithm - 回溯算法

Question

权重顺序如何影响回溯算法中的计算成本？节点和搜索树的数量是相同的，但是当它是无序的时，它需要更多的时间，所以它正在做一些事情。

谢谢！

Answer 1

有时在回溯算法中，当你知道某个分支不是答案时——你可以修剪它。这在游戏代理中很常见，称为Alpha Beta Prunning。

因此 - 当您重新排序访问的节点时，您可以提高修剪率，从而减少您访问的实际节点数，而不会影响答案的正确性。

另一种可能性 - 如果没有修剪是缓存性能。有时树被存储为数组[尤其是完整的树]。数组在迭代时最有效，而不是“随机跳跃”。重新排序可能会改变这种行为，从而导致更好/更差的缓存行为。

Answer 2

回溯的本质恰恰是不查看所有可能性或节点（在这种情况下），但是，如果节点没有排序，则算法不可能“修剪”可能的分支，因为不确定元素是否居然是在那根树枝上。

与它是有序树不同，因为如果搜索的元素大于/小于该子树的根，则搜索的元素分别位于右侧或左侧。这就是为什么如果树没有排序，则计算顺序等于蛮力，但是，如果树以最坏的情况排序，则相当于蛮力，但执行顺序更小。