SMAWK algorithm とは

SMAWKアルゴリズムは、暗黙的に定義された完全に単調な行列の各行で最小値を見つけるためのアルゴリズムです。それは5人の発明者、ピーターShor、Shlomo Moran、Alok Aggarwal、ロバートWilber、およびMaria Klaweの頭文字から命名された。
このアルゴリズムの目的のために、各行の最小値が前の行の最小値の列と等しいかまたはそれより大きい列で発生する場合、行列は単調であると定義されます。指定された行列の行と列の任意の部分集合によって定義されるすべての部分行列について、同じプロパティが真である場合、これは完全に単調です。同様に、行の最小値が右上および左下角にある2×2サブマトリクスが存在しない場合、行列は完全に単調である。すべてのMonge配列は完全に単調ですが、必ずしもその逆ではありません。
SMAWKアルゴリズムでは、検索対象の行列を関数として定義し、この関数をアルゴリズムの入力として(行列の次元とともに)指定します。アルゴリズムは、特定の行列セルの値を知る必要があるときはいつでも関数を評価します。この評価でO(1)が必要な場合、r行とc列の行列の実行時間と関数評価数はどちらもO(c(1 + log(r / c)))です。これは、すべての行列セルを評価する単純なアルゴリズムのO(r c)時間よりもはるかに高速です。
このアルゴリズムの基本的な考え方は、解決すべき問題が一定の係数だけ小さい同じ型の単一再帰的サブ問題に還元されるプルーンと探索戦略に従うことである。そうするために、アルゴリズムは最初に行列を前処理し、Grahamスキャンと類似のスタックベースのアルゴリズムと最も近いすべての小さな値アルゴリズムを使用して、行最小値を含むことのできない列を削除します。アルゴリズムのこのフェーズの後、残りの列の数は最大で行の数に等しくなります。次に、アルゴリズムはそれ自身を再帰的に呼び出して、行列の偶数行の行最小値を見つける。最後に、連続する偶数行の最小値の位置の間で列を探索することにより、アルゴリズムは奇数行の残りの最小値を満たす。
この方法の主な用途はAggarwal et al。計算幾何学、凸多角形の各点から最も遠い点を見つけ、最適な包絡線を見つけることにあった。その後の研究では、パラグラフを線、RNA二次構造予測、DNAおよびタンパク質配列アラインメント、接頭辞コードの構築、および画像閾値化などに分割する同じアルゴリズムの適用が見出された。