为什么回溯使算法不确定？

所以我至少有两位教授提到回溯会使算法不确定,而不会对其原因作出太多解释.我想我明白这是怎么发生的,但我无法用语言表达.有人能给我一个简明的解释原因吗？

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

相反,您通常需要回溯来处理非确定性算法,因为(通过非确定性的定义)您不知道在处理的特定时间采用哪条路径,而是您必须尝试多条路径.

我只想引用维基百科:

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

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

在非确定性编程文章中.

考虑一种用于着色世界地图的算法.相邻国家/地区不得使用任何颜色.该算法任意地在一个国家开始并将其着色为任意颜色.所以它一直在着色国家,改变每一步的颜色,直到"呃哦",两个相邻的国家都有相同的颜色.那么,现在我们必须回溯,并做出新的颜色选择.现在我们没有做出不确定性算法的选择,这对我们的确定性计算机来说是不可能的.相反,我们使用回溯模拟非确定性算法.非确定性算法将为每个国家做出正确的选择.