回溯算法
权重顺序如何影响回溯算法中的计算成本？节点和搜索树的数量是相同的，但是当它是无序的时，它需要更多的时间，所以它正在做一些事情。
谢谢！
How weigth order affects the computing cost in a backtracking algorithm? The number of nodes and search trees are the same but when it's non-ordered it tooks a more time, so it's doing something.
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
有时在回溯算法中，当您知道某个分支不是答案时 - 您可以修剪它。这在游戏代理中非常常见，称为 Alpha Beta 修剪。
因此，当您对访问的节点重新排序时，您可以提高修剪率，从而减少您访问的实际节点数量，而不会影响答案的正确性。
另一种可能性——如果没有修剪的话就是缓存性能。有时树被存储为数组[特别是完整树]。数组在迭代时效率最高，而不是“随机跳跃”。重新排序可能会改变此行为，从而导致更好/更差的缓存行为。
Sometimes in backtracking algorithms, when you know a certain branch is not an answer - you can trim it. This is very common with agents for games, and is called Alpha Beta Prunning.
Thus - when you reorder the visited nodes, you can increase your prunning rate and thus decrease the actual number of nodes you visit, without affecting the correctness of your answer.
One more possibility - if there is no prunning is cache performance. Sometimes trees are stored as array [especially complete trees]. Arrays are most efficient when iterating, and not "jumping randomly". The reorder might change this behavior, resulting in better/worse cache behavior.
回溯的本质恰恰是不考虑所有可能性或节点（在本例中），但是，如果节点没有排序算法不可能“修剪”可能的分支，因为无法确定元素是否确实位于该分支上。
与不同，当它是有序树时，因为如果搜索元素大于/小于该子树的根，则搜索元素位于右侧或左侧分别是强>。这就是为什么如果树没有排序，则计算顺序等于暴力，但是，如果树按最坏情况排序，则计算顺序相当于暴力，但执行顺序较小。
The essence of backtracking is precisely not looking at all possibilities or nodes (in this case), however, if the nodes are not ordered it is impossible for the algorithm to "prune" a possible branch because it is not known with certainty if the element Is actually on that branch.
Unlike when it is an ordered tree since if the searched element is greater / smaller the root of that subtree, the searched element is to the right or left respectively. That is why if the tree is not ordered the computational order is equal to brute force, however, if the tree is ordered in the worst case order is equivalent to brute force, but the order of execution is smaller.