剪定と検索

プルーンアンドサーチは、 1983年にニムロド・メギドによって提案された最適化問題を解決する手法です。 ^[1]

この方法の基本的な考え方は、各ステップで入力サイズが定数係数 $0 < p < 1$ で削減 (「剪定」) される再帰手順です。したがって、これは各ステップで定数係数で削減される減少統治アルゴリズムの一種です。入力サイズを $n$ 、剪定および検索アルゴリズム全体の時間計算量を $T (n)$ 、剪定ステップの時間計算量を $S$ $($ $n$ $)とします。この場合、$ $T$ $($ $n$ $) は$ 次の再帰関係に従います。

T(n)=S(n)+T(n(1-p)).

これは二分探索の再帰に似ていますが、二分探索の定数項よりも $S (n)項が大きくなります。プルーンおよび検索アルゴリズムでは、S(n) は通常少なくとも線形です (入力全体を処理する必要があるため)。この仮定では、再帰の解は$ $T (n) = O (S (n))となります。これは、$ 分割統治再帰のマスター定理を適用するか、再帰サブ問題の時間が等比級数的に減少することを観察することで確認できます。

特に、メギド自身は次元が固定されている場合の線形計画問題^[2]と空間内の点の集合に対する最小包囲球問題に対する線形時間アルゴリズムでこのアプローチを使用しました。 ^[1]

参考文献

^ ab Nimrod Megiddo (1983) R ³における線形計画法と関連問題のための線形時間アルゴリズム。SIAM J. Comput.、12:759–776 doi :10.1109/SFCS.1982.24
^ Nimrod Megiddo (1984)次元が固定されている場合の線形時間での線形計画法doi :10.1145/2422.322418

[lp3-1] Nimrod Megiddo (1983) R ³における線形計画法と関連問題のための線形時間アルゴリズム。SIAM J. Comput.、12:759–776 doi :10.1109/SFCS.1982.24

[2] Nimrod Megiddo (1984)次元が固定されている場合の線形時間での線形計画法doi :10.1145/2422.322418