18

所以我至少有两位教授提到回溯使算法具有不确定性，但没有给出太多解释为什么会这样。我想我明白这是怎么发生的，但我很难用语言表达。有人能给我一个简明的解释吗？

4

9 回答 9

14

回溯使算法不确定的情况并非如此。

相反，您通常需要回溯来处理非确定性算法，因为（根据非确定性的定义）您不知道在处理过程中的特定时间采用哪条路径，而是必须尝试几个。

于 2009-02-01T06:03:50.300 回答
9

我只是引用维基百科：

非确定性编程语言是一种可以在程序中的某些点（称为“选择点”）指定程序流程的各种替代方案的语言。与 if-then 语句不同，这些备选方案之间的选择方法不是由程序员直接指定的；程序必须在运行时通过应用于所有选择点的一些通用方法来决定备选方案。程序员指定有限数量的备选方案，但程序必须稍后在它们之间进行选择。（实际上，“选择”是非确定性算子的典型名称。）可以形成选择点的层次结构，较高级别的选择导致分支中包含较低级别的选择。

一种选择方法体现在回溯系统中，其中一些替代方案可能“失败”，导致程序回溯并尝试其他替代方案。如果所有备选方案在特定选择点都失败，则整个分支都失败，程序将进一步回溯到较旧的选择点。一个复杂的问题是，因为任何选择都是试探性的并且可能被重新做出，系统必须能够通过撤销由部分执行最终失败的分支引起的副作用来恢复旧的程序状态。

出非确定性编程文章。

于 2009-02-01T05:54:16.497 回答
6

考虑一种为世界地图着色的算法。相邻国家不能使用颜色。该算法任意从一个国家开始，并将其着色为任意颜色。所以它继续前进，给国家上色，每一步改变颜色，直到“呃哦”，两个相邻的国家颜色相同。好吧，现在我们必须回溯，并做出新的颜色选择。现在我们没有像非确定性算法那样做出选择，这对于我们的确定性计算机来说是不可能的。相反，我们正在模拟带有回溯的非确定性算法。一个非确定性算法会为每个国家做出正确的选择。

于 2009-02-01T06:05:16.023 回答
4

在确定性计算机上回溯的运行时间是阶乘的，即它在 O(n!) 中。

在非确定性计算机可以在每一步中立即正确猜测的情况下，确定性计算机必须尝试所有可能的选择组合。

由于不可能构建非确定性计算机，因此您的教授的意思可能如下：

复杂性类 NP 中的一个已被证明的难题（非确定性计算机可以通过始终正确猜测来有效解决的所有问题）在真实计算机上的解决比通过回溯更有效。

如果复杂性类别 P（确定性计算机可以有效解决的所有问题）和 NP 不一样，则上述陈述是正确的。这就是著名的 P 与 NP 问题。克莱数学研究所为其解决方案提供了 100 万美元的奖金，但该问题多年来一直无法证明。然而，大多数研究人员认为 P 不等于 NP。

一个简单的总结方法是：非确定性计算机可以通过始终正确猜测来有效解决最有趣的问题，这些问题非常困难，以至于确定性计算机可能不得不尝试所有可能的选择组合，即使用回溯。

于 2009-02-02T19:53:46.067 回答
1

思想实验：

1）从视野中隐藏了一些电荷分布，您可以从中感受到力并测量它们产生的势场。告诉我所有指控的确切位置。

2）收取一些费用并安排它们。准确地告诉我他们创造的潜在领域。

只有第二个问题有一个独特的答案。这就是向量场的非唯一性。这种情况可能类似于您正在考虑的一些非确定性算法。进一步考虑不存在的数学极限，因为它们有不同的答案，具体取决于您从哪个方向接近不连续性。

于 2009-02-01T06:53:40.807 回答
1

我写了一个使用回溯（当然）的迷宫跑步者，我将使用它作为示例。

你穿过迷宫。当你到达一个路口时，你掷硬币来决定走哪条路。如果您选择了死胡同，请回溯到路口并采取另一条路线。如果您都尝试过，请返回上一个路口。这个算法是非确定性的，不是因为回溯，而是因为抛硬币。

现在改变算法：当你到达一个路口时，总是先尝试你还没有尝试过的最左边的路线。如果这导致死胡同，请返回交叉路口并再次尝试您尚未尝试过的最左边的路线。该算法是确定性的。没有任何机会，这是可以预见的：您将始终在同一个迷宫中遵循相同的路线。

于 2009-02-13T15:23:23.697 回答
0

如果您允许回溯，则您允许程序中的无限循环，这使得它具有不确定性，因为所采用的实际路径可能总是包含另一个循环。

于 2009-02-01T07:44:49.627 回答
0

非确定性图灵机 (NDTM) 可以在一个步骤中采用多个分支。另一方面，DTM 遵循试错过程。

您可以将 DTM 视为普通计算机。相比之下，量子计算机与 NDTM 相似，可以更轻松地解决非确定性问题（例如，参见它们在破解密码学中的应用）。所以回溯对他们来说实际上是一个线性过程。

于 2009-02-01T10:04:07.553 回答
0

我喜欢迷宫的比喻。为简单起见，让我们将迷宫想象成一棵二叉树，其中只有一条路径。

现在您想尝试深度优先搜索以找到走出迷宫的正确方法。

非确定性计算机将在每个分支点复制/克隆自身并并行运行每个进一步的计算。就好像迷宫中的人会在每个分支点复制/克隆自己（就像电影 Prestige 中一样），并将自己的一个副本发送到树的左子分支，将自己的另一个副本发送到树的右子分支那个树。

最终陷入死胡同的计算机/人会死去（没有回答就终止）。

只有一台计算机能够存活（以答案结束），即走出迷宫的计算机。

回溯和非确定性之间的区别如下。

在回溯的情况下，在任何给定时刻只有一台计算机活着，他使用传统的迷宫解决技巧，简单地用粉笔标记他的路径，当他到达死胡同时，他只是简单地回溯到一个分支点，其子分支他还没有完全探索，就像在深度先搜索一样。

相比之下 ：

非确定性计算机可以在每个分支点克隆自己，并通过在子分支中运行并行搜索来检查出路。

所以回溯算法模拟/模拟了非确定性计算机在顺序/非并行/确定性计算机上的克隆能力。

于 2014-10-31T18:59:37.473 回答