非确定性算法

不确定的问题 (Undecidable Problems)

An undecidable problem is a problem for which there is no algorithm that can solve it. Alan Turing proved that the famous halting problem is undecidable. The halting problem can be simply stated as follows - Given an input and a Turing machine, there is no algorithm to determine if the machine will eventually halt. There are several problems in mathematics and computer science that are undecidable.

无法确定的问题是没有算法可以解决的问题。 艾伦·图灵(Alan Turing)证明了著名的停止问题尚不确定。 停止问题可以简单地描述如下-给定输入和Turing机器，没有算法确定机器是否最终停止。 在数学和计算机科学中存在一些无法确定的问题。

多项式和非多项式时间算法 (Polynomial and Non - polynomial time algorithm)

If the complexity of an algorithm is expressed as O (p(n)) where p(n) is some polynomial of n, then the algorithm is said to be a polynomial time algorithm. Generally, polynomial time algorithms are tractable. Any algorithm with a time complexity that cannot be bounded by such bound then this is known as non - polynomial algorithms.

如果一种算法的复杂度被表示为O(P(N))其中p(n)是多项式的一些n个 ，则算法被认为是一个多项式时间算法。 通常，多项式时间算法很容易处理。 具有时间复杂度的任何算法都不能被这种限制所限制，这就是非多项式算法。

确定性和非确定性算法 (Deterministic and Non - deterministic Algorithms)

The algorithms in which the result of every algorithm is uniquely defined are known as the deterministic algorithm. In the theoretical framework, we can remove this restriction on the outcome of every operation. We can allow algorithms to contain operations whose outcomes are not uniquely defined but are limited to specified sets of possibilities. The machine executing each operation is allowed to choose any one of these outcomes subjects to a determination condition to be defined later. This leads to the concept of a Non-deterministic algorithm.

唯一定义每个算法的结果的算法称为确定性算法 。 在理论框架中，我们可以消除对每个操作结果的限制。 我们可以允许算法包含操作，这些操作的结果不是唯一定义的，但仅限于指定的可能性集。 允许执行每个操作的机器选择这些结果对象中的任何一个，以决定条件以便稍后定义。 这导致了非确定性算法的概念。

There are three new functions which specify such types of algorithms are:

有三种指定这些算法类型的新功能是：

1. Choice(S) arbitrarily chooses one of the elements of the set S.

   Choice(S)任意选择集合S的元素之一。

2. Failure() signals an unsuccessful completion.

   Failure()表示未成功完成。

3. Success() signals a successful completion.

   Success()表示成功完成。

The assignments statement x: Choice (1, n) could result in x being assigned any one of the integers in the range [1, n]. There is no rule specifying how this choice is to be made. The Failure() and the Success() signals are used to define a computation of the algorithm. These statements cannot be used to effect a return. Whenever there is a set of the choices that lead to a successful completion, then one such set of the choices is always made and the algorithm terminates successfully. A non - deterministic algorithm terminates unsuccessfully if and only if there exists no set of the choices leading to a success signal. The computing times for the Choices, the Success, and the Failure are taken to be O (1). A machine capable of executing a non - deterministic algorithm in this way is called a non – deterministic machine.

赋值语句x：Choice(1，n)可能导致x被赋值范围[1，n]中的任何整数。 没有规则指定如何进行此选择。 Failure()和Success()信号用于定义算法的计算。 这些语句不能用于产生回报。 只要有一组选择导致成功完成，就总是做出这样一组选择，并且算法成功终止。 当且仅当不存在导致成功信号的选择集时， 非确定性算法才会失败终止。 选择，成功和失败的计算时间取为O(1) 。 能够以这种方式执行非确定性算法的机器称为非确定性机器。

References:

参考文献：

翻译自:

非确定性算法