Loading article…
SMAWKアルゴリズムは、暗黙的に定義された完全単調行列の各行の最小値を求めるアルゴリズムです。このアルゴリズムは、5人の発明者、Peter Shor、Shlomo Moran、Alok Aggarwal、Robert Wilber、およびMaria Klaweの頭文字にちなんで名付けられました。[ 1 ]
このアルゴリズムでは、行列は、各行の最小値が前の行の最小値の列以上の列にある場合に単調であると定義されます。任意の部分行列（与えられた行列の行と列の任意の部分集合によって定義される）に対して同じ性質が成り立つ場合、その行列は完全単調です。言い換えれば、行の最小値が右上隅と左下隅にある2×2の部分行列が存在しない場合、その行列は完全単調です。すべてのモンジュ配列は完全単調ですが、必ずしもその逆は成り立ちません。
SMAWKアルゴリズムでは、検索対象の行列を関数として定義し、この関数を（行列の次元とともに）アルゴリズムへの入力として与えます。アルゴリズムは、特定の行列セルの値を知る必要があるたびに、この関数を評価します。この評価にO ( 1 )の時間を要する場合、 r行c列の行列では、実行時間と関数評価回数はどちらもO ( c (1 + log( r / c )))となります。これは、すべての行列セルを評価する単純なアルゴリズムのO ( rc )時間よりもはるかに高速です。
このアルゴリズムの基本的な考え方は、解決すべき問題を定数倍だけ小さい同じタイプの単一の再帰的な部分問題に縮小する、剪定と探索の戦略に従うことです。そのためには、まず、グラハムスキャンやすべての最も近い小さい値アルゴリズムと同様のスタックベースのアルゴリズムを使用して、行の最小値を含むことができない列を行列から削除する前処理を行います。このアルゴリズムのフェーズの後、残りの列の数は行の数と最大で等しくなります。次に、アルゴリズムは自身を再帰的に呼び出し、行列の偶数行の行の最小値を見つけます。最後に、連続する偶数行の最小値の位置間の列を探索することにより、アルゴリズムは奇数行の残りの最小値を埋めます。
Aggarwal らによる原著論文で紹介されたこの手法の主な応用例は、計算幾何学、凸多角形の各点から最も遠い点を見つけること、および最適な外接多角形を見つけることでした。その後の研究では、同じアルゴリズムの応用が、段落を行に分割すること[ 2 ] 、 RNA二次構造予測[ 3 ] 、DNAおよびタンパク質配列のアライメント[ 4 ] [ 5 ]、接頭辞コードの構築[ 6 ]、画像閾値処理[ 7 ]などにも見出されました。