algorithm - 在精确覆盖问题中，是什么导致 r 的选择具有不确定性？

Question

背景:

以下是 Donald Knuth 论文中的伪代码:Dancing Links

If A is empty, the problem is solved; terminate successfully.
Otherwise choose a column, c (deterministically).
Choose a row, r, such that A[r, c] = 1 (nondeterministically).
Include r in the partial solution.
For each j such that A[r, j] = 1,
   delete column j from matrix A;
   for each i such that A[i, j] = 1,
       delete row i from matrix A.
Repeat this algorithm recursively on the reduced matrix A.

Knuth 然后写道:

The nondeterministic choice of r means that the algorithm essentially clones itself into independent subalgorithms; each subalgorithm inherits the current matrix A, but reduces it with respect to a different row r.

我对(非)确定性算法的假设:

我认为 c 的选择是确定性的，因为精确约束矩阵 A 中的列数是事先已知的。

我认为这种 r 的选择是不确定的，因为事先不知道可用行的数量。可用行集取决于求解器的当前状态。例如，对于求解器的特定状态，满足 A[r, c] = 1 的下一行可能就在附近。在另一个州，它可能会更远。

我通过阅读 Wikipedia entry on nondeterministic algorithms 得出上述假设，具体来说:

An algorithm that solves a problem in nondeterministic polynomial time can run in polynomial time or exponential time depending on the choices it makes during execution.

问题

算法的不确定性如何使其“本质上是 self 克隆”？这看起来更像是递归的属性，而不是确定性算法的属性。

Answer 1

c 的选择是确定性的，因为没有错误的选择(但做出该选择的某些规则比其他规则更好；请参阅 Knuth 的文章中伪代码后不久的讨论)。该算法做出任意选择并继续前进。在递归调用中，矩阵中剩余的列数是事先不知道的。

r 的选择是不确定的，因为算法需要尝试所有可能的选择以找到所有的解决方案。 Knuth 可能是这样描述的，因为(1)他是一个老派的 CS 理论家，这就是自动机/形式语言理论中的描述方式(2)它强调了一个事实，即非确定性分支彼此不依赖，因此适合并行处理。