我们如何定义循环不变量？

Question

我们知道循环变体被定义为在循环的每次迭代之前和之后都为真的语句。但这个定义是不是太宽松了？让我们看一个具体的例子：线性搜索。

输入：n个数的序列A = (a₁, a₂, a₃, ..., a_n) 和一个值 v

输出：索引 i 使得 v = A[i] 或如果在 A

中找不到 v 则为 NIL

这是我的伪代码：

linear_search(A, v)
1 for i ∈ {1, 2, ..., n}
2     if A[i] = v
3         return i
4 return NIL

因此，典型的循环不变量是（因为我们是从左到右搜索）v 不在当前索引的左侧，或者从数学上讲，P: ∀p ∈ {1, 2, ..., i - 1}, A[p] ≠ v. 这显然是正确的，即使在开始是因为 p ∈ Ø 为假，这使得 P 为真，记住每个普遍量化的陈述都可以被认为是一个条件陈述。（不过通俗地想起来更容易：一开始，v左边什么都没有）

我们还可以使用限制较少的条件语句。在这种情况下，Q: If A[i] = v, then 1 ≤ i ≤ n. 显然，如果找到 v，则为真。如果未找到 v，则 A[i] = v 为假，而无论 i 的值如何，Q 都为真。如果我们将算法更改为从右到左搜索，Q 也成立。

也许我们想放宽限制。使用一个永远正确的陈述怎么样？ R: Either A[i] = v or A[i] ≠ v. R 在循环的每次迭代之前和之后都成立。

语句 P、Q 和 R 中的哪一个可以有效用作循环不变量？

Answer 1

你想要什么循环不变量for？也许您想证明您的算法是正确的，即：

linear_search(A,v) = i ⇒ A[i] = v

和

linear_search(A,v) = NIL ⇒ v ∉ A

第一个很简单。为了证明第二个，你可以使用你的循环不变量 P。因为如果函数 returns NIL 对于 i=n 是真的，你有

linear_search(A,v) = NIL
⇒ ∀p ∈ {1, 2, ..., n}, A[p] ≠ v
⇒ v ∉ A

你的候选人P对这个有用，其他的都没有。

此外，您不能只选择一个循环不变量——您必须证明它才能证明您的算法是正确的。循环的迭代性质有助于通过归纳法进行证明，并且像您的候选人 P 这样的不变量很容易通过这种方式证明。

我们如何定义循环不变量？

How do we define a loop invariant?

algorithm

loop-invariant