正しいと思われるアルゴリズムと証明の例

プログラミングコースの紹介では、アルゴリズムが私たちが期待することを証明するInitialization-Maintenance-Terminationメソッドについて学習しています。しかし、私たちは、すでに正しいことが分かっているアルゴリズムが正しいことを証明しなければなりませんでした。アルゴリズムが正しくないことを示すように依頼されたことはありません。

正しく見えるアルゴリズムの古典的な例はありますか?そうではありませんか?私はInitialization-Maintenance-Terminationのアプローチが一見して直感的ではないものを捉えるケースを探しています。

ベストアンサー

2Dローカル最大値

input: 2-dimensional $n times n$ array $A$

output: a local maximum — a pair $(i,j)$ such
that $A[i,j]$ has no neighboring cell in the array that contains a
strictly larger value.

(隣接するセルは、アレイ内に存在する$ A [i、j + 1]、A [i、j-1]、A [i-1、j]、A [i + 1、j]
)例えば、$ A $が

$$begin{array}{cccc} 0&1&3&mathbf{4}\
mathbf{3}&2&mathbf{3}&1\
2&mathbf{5}&0&1\
mathbf{4}&0&1&mathbf{3}end{array}$$

各太字のセルは極大値になります。すべての空でない配列には、少なくとも1つのローカル最大値があります。

Algorithm. There is an $O(n^2)$-time algorithm:
just check each cell. Here’s an idea for a faster, recursive
algorithm.

$ A $が与えられた場合、中央の列のセルと中央の列のセルからなるようにX $を定義します。まず、$ X
$の各セルを調べて、そのセルが$ A
$のローカル最大値かどうかを調べます。そのような場合は、そのようなセルを返します。そうでなければ、$(i、j)$を最大値の$ X
$のセルとする。 $(i、j)$は局所的な最大値ではないので、より大きな値を持つ隣接セル$(i
‘、j’)$を持たなければならない。

左上、右上、左下、右下の四分円に自然な形で$ A setminus X $(配列$ A $、$ X
$のセルを引いたもの)を分割します。より大きな値を有する隣接セル$(i
‘、j’)$は、それらの象限の1つになければならない。その象限を$ A ‘$と呼んでください。

Lemma. Quadrant $A’$ contains a local
maximum of $A$.

Proof. Consider starting at the cell $(i’, j’)$. If it
is not a local maximum, move to a neighbor with a larger value.
This can be repeated until arriving at a cell that is a local
maximum. That final cell has to be in $A’$, because $A’$ is bounded
on all sides by cells whose values are smaller than the value of
cell $(i’, j’)$. This proves the lemma. $diamond$

このアルゴリズムは、$ frac {n} {2} times frac {n} {2} $サブ配列$ A
‘$を再帰的に呼び出すことで、そこに極大$(i、j)$を見つけ、その細胞。

$ n times n $行列の実行時間$ T(n)$は、$ T(n)= T(n/2)+ O(n) 。

したがって、我々は次の定理を証明した。

Theorem. There is an $O(n)$-time algorithm
for finding a local-maximum in an $ntimes n$ array.

または私たちは持っていますか?

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です