1

我试图用集团问题来理解非确定性。

在计算机科学中，集团问题是指与在图中找到特定完整子图（“集团”）相关的任何问题，即每对元素相连的元素集合。

假设我有一个带有节点 A、B、C、D、E、F 的图，我想确定是否存在 4 的集团。

我对非确定性的理解是通过取四个节点（B、C、D、F）进行猜测，并检查所有 4 个节点之间是否存在连接。如果存在，我断定集团存在，如果不存在，我断定集团不存在。

然而，我不确定这如何帮助解决问题，因为我可能做出了错误的选择。

我想我想总体上理解非确定性的应用。

4

1 回答 1

2

非确定性选择不同于随机或任意选择。当使用非确定性时，如果可以做出的任何可能的选择将导致算法输出“是”，那么将选择其中一个选择。如果不存在这样做的选择，则将做出任意选择。

如果这看起来像是作弊，那么在某种意义上它就是。不知道如何使用确定性计算机、随机算法或具有大量处理器但只能在每个内核上执行少量工作的并行计算机有效地实现非确定性。这些分别是 P = NP、BPP = NP 和 NC = NP 问题。因此，非确定性主要是一种解决问题的理论方法。

希望这可以帮助！

于 2013-12-10T18:18:46.007 回答