问回溯算法

EN

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

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

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

回溯的本质正是没有查看所有的可能性或节点(在这种情况下)，然而，如果节点没有被排序，算法就不可能“修剪”一个可能的分支，因为它不能确定元素是否确实在那个分支上。

与不同，当它是一个有序树时，因为如果搜索到的元素大于或小于该子树的根，则搜索到的元素分别位于或。这就是为什么如果树没有排序，计算顺序等于蛮力，然而，如果树按最坏的情况排序，顺序等同于蛮力，但执行顺序较小。