不确定性算法
我需要非确定性算法的简单描述。我们可以将非确定性算法与具有并行处理器的计算机进行比较吗？ 请有人准确地向我解释一下非确定性算法
I need a simple description of nondeterministic algorithms . Can we comapre nondeterministic algorithm with computer with parrallel processor?
please someone exactly explain me about nondeterministic algorithms
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
非确定性算法是在非确定性图灵机上运行的算法。
该算法中的每个计算都可以分为 2 个计算，这些计算是同时计算的。
非确定性算法示例：
设置覆盖：“猜测”顶点的子集，并检查它是否是有效的封面。
猜测是：对于每个元素：检查它在集合中和不在集合中的一种可能性。
它不是并行处理器，因为在这里（非确定性算法），分支数量不受限制，而在并行处理器中则如此。在并行计算中，您仍然必须执行
2^n次操作来查找顶点覆盖范围，而在非确定性算法中，您只能执行n次操作，并且n个不同的分支。非确定性机器更像是量子计算机，而不是并行处理。 [请注意，量子计算机仍然比非确定性图灵机“弱”，当然假设 P!=NP]。
a non deterministic algorithm is an algorithm ran on a non deterministic turing machine.
each calculation in this algorithm can branch into 2 calculations, which are computed simultaneously.
none deterministic algorithm example:
Set Cover: "guess" a subset of the vertices, and check if it is a valid cover.
the guessing is: for each element: check one possibility it IS in the set and it is NOT in the set.
It is not parallel processor, because in here (nondeterministic algorithm), the number of branches is not limited, while in parallel processor it is. In parallel computing, you are still bounded to do the
2^nOPs for finding vertex coverage, while in nondeterministic algorithm, you are doing onlynops, withndifferent branches.a non-deterministic machine would be more like quantum computer, than parallel processing. [note that quantum computer is still 'weaker' then non-deterministic turing machine, assuming P!=NP, of course].