我至少有两位教授提到过回溯算法会使算法变得非确定性，但并没有过多解释这是为什么。我认为我理解了这是如何发生的，但我很难用语言表达清楚。能否有人简明扼要地解释一下这个原因？
为什么回溯会使算法变得非确定性？
18
- Jason Baker
2
回溯并不会使算法变得非确定性；请修改您的问题。 - ShreevatsaR
好问题，当我观看这个视频讲座时，我也在问自己同样的问题：http://youtu.be/UBVcV3LIBeU - jhegedus
9个回答
14
回溯(backtracking)并不是使算法变得非确定性的原因。
相反，通常需要回溯来处理一个非确定性算法，因为根据非确定性的定义，您在处理过程中无法知道应该选择哪条路径，而必须尝试多条路径。
- Mark Harrison
9
我只引用维基百科的话：
非确定性编程语言是一种语言，它可以在程序中的某些点（称为“选择点”）指定程序流的各种替代方案。与if-then语句不同，程序员没有直接指定这些选择之间的方法；程序必须在运行时通过应用于所有选择点的某种通用方法在选择之间做出决策。程序员指定了有限数量的备选方案，但程序必须稍后在它们之间选择。 （“选择”实际上是非确定性运算符的典型名称。）可以形成选择点的层次结构，其中高级选择导致包含其中的低级选择的分支。
选择的一种方法体现在回溯系统中，其中某些备选方案可能会“失败”，导致程序回溯并尝试其他备选方案。如果在特定选择点上所有备选方案都失败，则整个分支失败，程序将进一步回溯到旧选择点。一个复杂点在于，由于任何选择都是暂时的并且可能被重新制作，因此系统必须能够通过撤消部分执行最终失败的分支引起的副作用来恢复旧的程序状态。
出自Nondeterministic Programming文章。
非确定性编程语言是一种语言，它可以在程序中的某些点（称为“选择点”）指定程序流的各种替代方案。与if-then语句不同，程序员没有直接指定这些选择之间的方法；程序必须在运行时通过应用于所有选择点的某种通用方法在选择之间做出决策。程序员指定了有限数量的备选方案，但程序必须稍后在它们之间选择。 （“选择”实际上是非确定性运算符的典型名称。）可以形成选择点的层次结构，其中高级选择导致包含其中的低级选择的分支。
选择的一种方法体现在回溯系统中，其中某些备选方案可能会“失败”，导致程序回溯并尝试其他备选方案。如果在特定选择点上所有备选方案都失败，则整个分支失败，程序将进一步回溯到旧选择点。一个复杂点在于，由于任何选择都是暂时的并且可能被重新制作，因此系统必须能够通过撤消部分执行最终失败的分支引起的副作用来恢复旧的程序状态。
出自Nondeterministic Programming文章。
- litb
7
2恭喜。这是一个“阅读维基百科”的答案，让我感觉不是很蠢。 :-) - Jason Baker
1如果不想让系统变得非确定性，我会采用Mark Harrison的答案：这是模拟(一个理论上的)非确定性机器的方法。 - hasen
1Hasen J，你指的是哪个系统？回溯当然只能模拟非确定性，只要它在确定性计算机上运行。一个典型的例子是正则表达式库。它们接受非确定性描述，并将其转换为确定性状态机。 - Johannes Schaub - litb
好的，你说得对，计算机是确定性的（假设没有人为输入），所以在其上运行的任何代码都将以确定性方式运行。 - hasen
这更像是物理上的限制 :) 我的观点是，你的答案（或至少其措辞）暗示了确定性机器可以表现出非确定性行为，仅仅因为它进行了回溯; 这是不正确的。 - hasen
显示剩余2条评论
6
考虑一种涂世界地图的算法，相邻的国家不能使用相同的颜色。该算法从一个国家任意选择一个颜色开始，接着依次涂色，每步更改颜色，直到出现相邻两国拥有了相同的颜色时，“咦”，我们需要回溯并重新选择颜色。这里我们不是像不确定性算法那样做出选择，因为那对于我们的确定性计算机来说是不可能的。相反，我们通过回溯模拟不确定性算法。不确定性算法会为每个国家做出正确的选择。
- George IV
1
请仅返回翻译后的文本：查看我对litb答案的评论 - hasen
4
在确定性计算机上，回溯法的运行时间是阶乘级别的，即它属于O（n！）。
当非确定性计算机可以在每一步中瞬间猜对时，确定性计算机必须尝试所有可能的选择组合。
由于无法构建非确定性计算机，您的教授可能是指以下内容：
复杂度类NP中的一个已知难题（所有非确定性计算机都能够通过始终猜测正确来有效地解决的问题）不能在真实计算机上比回溯更有效地解决。
如果复杂度类P（所有确定性计算机可以有效地解决的问题）和NP不同，则上述语句是正确的。这是著名的P与NP问题。克雷数学研究所为其解决方案提供了100万美元的奖金，但该问题多年来一直没有得到证明。然而，大多数研究人员认为P不等于NP。
简单概括一下就是：大多数有趣的问题，非确定性计算机可以通过始终猜测正确来有效地解决，但是这些问题非常困难，确定性计算机可能需要尝试所有可能的选择组合，即使用回溯。
当非确定性计算机可以在每一步中瞬间猜对时，确定性计算机必须尝试所有可能的选择组合。
由于无法构建非确定性计算机，您的教授可能是指以下内容：
复杂度类NP中的一个已知难题（所有非确定性计算机都能够通过始终猜测正确来有效地解决的问题）不能在真实计算机上比回溯更有效地解决。
如果复杂度类P（所有确定性计算机可以有效地解决的问题）和NP不同，则上述语句是正确的。这是著名的P与NP问题。克雷数学研究所为其解决方案提供了100万美元的奖金，但该问题多年来一直没有得到证明。然而，大多数研究人员认为P不等于NP。
简单概括一下就是：大多数有趣的问题，非确定性计算机可以通过始终猜测正确来有效地解决，但是这些问题非常困难，确定性计算机可能需要尝试所有可能的选择组合，即使用回溯。
- mdm
3
编辑说明算法为阶乘而非指数。 - Jason Baker
1就复杂度类而言，它们是指数级的（即在EXPTIME类中）。此外，大多数O（n！）问题可以使用动态规划在O（N^2*2^N）中解决。但如果您觉得理解起来更容易，那我没问题。 - mdm
据我所知，复杂度类是针对问题/语言而非算法的。回溯只是解决问题的一种方法，因此它本质上不可能是阶乘（也不是指数级别）的。 - logi-kal
1
我写了一个使用回溯算法的迷宫寻路程序，下面以此为例。
你在迷宫中行走。当你到达一个岔路口时，你会抛硬币来决定要走哪条路。如果你选择了一条死路，就返回到岔路口并选择另一条路。如果你都尝试过了，就返回到上一个岔路口。 这个算法是非确定性的，不是因为回溯，而是因为抛硬币。
现在改变算法：当你到达一个岔路口时，总是先尝试你还没有尝试过的最左边的路线。如果那条路通向死路，就返回到岔路口并再次尝试你还没有尝试过的最左边的路线。 这个算法是确定性的。没有涉及到任何机会，它是可预测的：在同一个迷宫中，你总是会按照相同的路线行走。
- stevenvh
0
如果允许回溯，您将允许程序中的无限循环，这使其变得不确定，因为实际采取的路径可能始终包括一个以上的循环。
- jeffD
0
非确定性图灵机（NDTMs）可以在单个步骤中采用多个分支。另一方面，DTMs则遵循试错过程。
您可以将DTMs视为常规计算机。相比之下，量子计算机类似于NDTMs，并且可以更轻松地解决非确定性问题（例如，在破解密码学中应用）。因此，回溯对它们来说实际上是一个线性过程。
- Eduard - Gabriel Munteanu
0
我喜欢迷宫的比喻。为了简单起见，我们可以将迷宫看作是一棵二叉树，其中只有一条出路。
现在你想尝试深度优先搜索来找到正确的出路。
非确定性计算机会在每个分支点上复制/克隆自己，并并行运行每个进一步的计算。就好像在迷宫中的人会在每个分支点上复制/克隆自己（就像电影《致命魔术》中的情节），并将他自己的一个副本发送到树的左子分支，将他自己的另一个副本发送到树的右子分支。
到达死胡同的计算机/人将会死亡（没有答案终止）。
只有一个计算机将存活下来（以答案终止），那就是走出迷宫的那个。
回溯和非确定性之间的区别如下：
在回溯的情况下，任何时候只有一个计算机处于活动状态，他使用传统的迷宫解决技巧，简单地用粉笔标记他的路径，当他到达死胡同时，他只需回溯到一个分支点，他还没有完全探索其子分支，就像深度优先搜索一样。
相比之下：
非确定性计算机可以在每个分支点克隆自己，并通过在子分支中运行并行搜索来检查出路。
因此，回溯算法在顺序/非并行/确定性计算机上模拟/仿真了非确定性计算机的克隆能力。
- jhegedus
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接