为什么回溯会使算法变得不确定？
因此，至少有两位教授提到回溯使算法变得不确定，但没有给出太多解释为什么会这样。 我认为我理解这是如何发生的，但我很难用语言来表达。 有人能给我一个简洁的解释吗？
So I've had at least two professors mention that backtracking makes an algorithm non-deterministic without giving too much explanation into why that is. I think I understand how this happens, but I have trouble putting it into words. Could somebody give me a concise explanation of the reason for this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（9）
回溯并不是让算法变得不确定的情况。
相反，您通常需要回溯来处理非确定性算法，因为（根据非确定性的定义）您不知道在处理过程中的特定时间采用哪条路径，而是必须尝试多条路径。
It's not so much the case that backtracking makes an algorithm non-deterministic.
Rather, you usually need backtracking to process a non-deterministic algorithm, since (by the definition of non-deterministic) you don't know which path to take at a particular time in your processing, but instead you must try several.
我简单引用一下维基百科：
摘自非确定性编程文章。
I'll just quote wikipedia:
Out of the Nondeterministic Programming article.
考虑一种为世界地图着色的算法。 相邻国家不能使用任何颜色。 该算法任意从一个国家开始，并将其着色为任意颜色。 所以它继续前进，为国家着色，每一步都改变颜色，直到“呃哦”，两个相邻的国家具有相同的颜色。 好吧，现在我们必须回溯，并做出新的颜色选择。 现在我们不会像非确定性算法那样做出选择，这对于我们的确定性计算机来说是不可能的。 相反，我们通过回溯来模拟非确定性算法。 不确定性算法将为每个国家做出正确的选择。
Consider an algorithm for coloring a map of the world. No color can be used on adjacent countries. The algorithm arbitrarily starts at a country and colors it an arbitrary color. So it moves along, coloring countries, changing the color on each step until, "uh oh", two adjacent countries have the same color. Well, now we have to backtrack, and make a new color choice. Now we aren't making a choice as a nondeterministic algorithm would, that's not possible for our deterministic computers. Instead, we are simulating the nondeterministic algorithm with backtracking. A nondeterministic algorithm would have made the right choice for every country.
确定性计算机上回溯的运行时间是阶乘的，即 O(n!)。
非确定性计算机可以在每个步骤中立即正确猜测，而确定性计算机必须尝试所有可能的选择组合。
由于不可能构建一台非确定性计算机，因此您的教授的意思可能如下：
事实证明，复杂性类别 NP 中的难题（非确定性计算机可以通过始终正确猜测来有效解决的所有问题）在真实计算机上无法比回溯更有效地解决。
如果复杂性类别 P（确定性计算机可以有效解决的所有问题）和 NP 不同，则上述陈述成立。 这就是著名的 P vs. NP 问题。 克莱数学研究所为其解决方案提供了 100 万美元的奖金，但该问题多年来一直无法得到证明。 然而，大多数研究者认为P不等于NP。
一个简单的总结方法是：非确定性计算机可以通过始终正确猜测来有效解决的最有趣的问题是如此困难，以至于确定性计算机可能必须尝试所有可能的选择组合，即使用回溯。
The running time of backtracking on a deterministic computer is factorial, i.e. it is in O(n!).
Where a non-deterministic computer could instantly guess correctly in each step, a deterministic computer has to try all possible combinations of choices.
Since it is impossible to build a non-deterministic computer, what your professor probably meant is the following:
A provenly hard problem in the complexity class NP (all problems that a non-deterministic computer can solve efficiently by always guessing correctly) cannot be solved more efficiently on real computers than by backtracking.
The above statement is true, if the complexity classes P (all problems that a deterministic computer can solve efficiently) and NP are not the same. This is the famous P vs. NP problem. The Clay Mathematics Institute has offered a $1 Million prize for its solution, but the problem has resisted proof for many years. However, most researchers believe that P is not equal to NP.
A simple way to sum it up would be: Most interesting problems a non-deterministic computer could solve efficiently by always guessing correctly, are so hard that a deterministic computer would probably have to try all possible combinations of choices, i.e. use backtracking.
思想实验：
1）隐藏在视野之外的是一些电荷的分布，您可以感受到其中的力，并测量它们产生的势场。 准确地告诉我所有指控的立场。
2）收取一些费用并安排它们。 准确地告诉我他们创造的势场。
只有第二个问题有唯一的答案。 这是矢量场的非唯一性。 这种情况可能与您正在考虑的一些非确定性算法类似。 进一步考虑数学极限，这些极限并不存在，因为它们根据你接近的方向有不同的答案的不连续性。
Thought experiment:
1) Hidden from view there is some distribution of electric charges which you feel a force from and you measure the potential field they create. Tell me exactly the positions of all the charges.
2) Take some charges and arrange them. Tell me exactly the potential field they create.
Only the second question has a unique answer. This is the non-uniqueness of vector fields. This situation may be in analogy with some non-deterministic algorithms you are considering. Further consider in math limits which do not exist because they have different answers depending on which direction you approach a discontinuity from.
我编写了一个使用回溯（当然）的迷宫跑步者，我将用它作为示例。
你穿过迷宫。 当您到达路口时，您可以掷硬币来决定要走哪条路线。 如果您选择了死胡同，请追溯到路口并走另一条路。 如果您尝试了所有这些，请返回之前的路口。
这个算法是非确定性的，不是因为回溯，而是因为抛硬币。
现在改变算法：当你到达一个路口时，总是先尝试你还没有尝试过的最左边的路线。 如果这导致了死胡同，请返回路口并再次尝试您尚未尝试过的最左边的路线。
该算法是确定性的。 没有任何机会，这是可以预测的：你将始终在同一个迷宫中遵循同一条路线。
I wrote a maze runner that uses backtracking (of course), which I'll use as an example.
You walk through the maze. When you reach a junction, you flip a coin to decide which route to follow. If you chose a dead end, trace back to the junction and take another route. If you tried them all, return to the previous junction.
This algorithm is non-deterministic, non because of the backtracking, but because of the coin flipping.
Now change the algorithm: when you reach a junction, always try the leftmost route you haven't tried yet first. If that leads to a dead end, return to the junction and again try the leftmost route you haven't tried yet.
This algorithm is deterministic. There's no chance involved, it's predictable: you'll always follow the same route in the same maze.
如果允许回溯，则允许程序中出现无限循环，这使得程序具有不确定性，因为所采取的实际路径可能总是包含一个循环。
If you allow backtracking you allow infinite looping in your program which makes it non-deterministic since the actual path taken may always include one more loop.
非确定性图灵机 (NDTM) 可以在一个步骤中执行多个分支。 另一方面，DTM 遵循试错过程。
您可以将 DTM 视为普通计算机。 相比之下，量子计算机与 NDTM 类似，可以更轻松地解决非确定性问题（例如，查看它们在破解密码学中的应用）。 所以回溯对他们来说实际上是一个线性过程。
Non-Deterministic Turing Machines (NDTMs) could take multiple branches in a single step. DTMs on the other hand follow a trial-and-error process.
You can think of DTMs as regular computers. In contrast, quantum computers are alike to NDTMs and can solve non-deterministic problems much easier (e.g. see their application in breaking cryptography). So backtracking would actually be a linear process for them.
我喜欢迷宫的比喻。 为简单起见，让我们将迷宫想象为一棵二叉树，其中只有一条路径。
现在您想尝试深度优先搜索来找到走出迷宫的正确方法。
非确定性计算机将在每个分支点复制/克隆自身并并行运行每个进一步的计算。 这就好像迷宫中的人会在每个分支点复制/克隆自己（就像电影《Prestige》中一样），并将自己的一个副本发送到树的左子分支，将自己的另一个副本发送到树的右子分支。那个树。
最终陷入死胡同的计算机/人会死亡（没有答案就终止）。
只有一台计算机能够幸存（以答案结束），即走出迷宫的计算机。
回溯和非确定性之间的区别如下。
在回溯的情况下，在任何给定时刻只有一台计算机活着，他会执行传统的迷宫解决技巧，简单地用粉笔标记他的路径，当他到达死胡同时，他只是简单地回溯到一个分支点，其子分支他还没有完全探索，就像深度优先搜索一样。
相比之下：
非确定性计算机可以在每个分支点克隆自己，并通过在子分支中运行并行搜索来检查出路。
所以回溯算法在顺序/非并行/确定性计算机上模拟/仿真非确定性计算机的克隆能力。
I like the maze analogy. Lets think of the maze, for simplicity, as a binary tree, in which there is only one path out.
Now you want to try a depth first search to find the correct way out of the maze.
A non deterministic computer would, at every branching point, duplicate/clone itself and run each further calculations in parallel. It is like as if the person in the maze would duplicate/clone himself (like in the movie Prestige) at each branching point and send one copy of himself into the left subbranch of the tree and the other copy of himself into the right subbranch of the tree.
The computers/persons who end up at a dead end they die (terminate without answer).
Only one computer will survive (terminate with an answer), the one who gets out of the maze.
The difference between backtracking and non-determinism is the following.
In the case of backtracking there is only one computer alive at any given moment, he does the traditional maze solving trick, simply marking his path with a chalk and when he gets to a dead end he just simply backtracks to a branching point whose sub branches he did not yet explore completely, just like in a depth first search.
IN CONTRAST :
A non deteministic computer can clone himself at every branching point and check for the way out by running paralell searches in the sub branches.
So the backtracking algorithm simulates/emulates the cloning ability of the non-deterministic computer on a sequential/non-parallel/deterministic computer.