SMAWKアルゴリズム

SMAWKアルゴリズムは、暗黙的に定義された完全単調行列の各行の最小値を見つけるアルゴリズムです。このアルゴリズムは、5人の発明者であるPeter Shor、Shlomo Moran、Alok Aggarwal、Robert Wilber、Maria Klaweの頭文字にちなんで名付けられました。^[1]

入力

このアルゴリズムの目的上、各行の最小値が前の行の最小値と同じかそれより大きい列に発生する場合、その行列は単調であると定義されます。同じ特性がすべてのサブ行列 (特定の行列の行と列の任意のサブセットによって定義されます) に当てはまる場合、その行列は完全に単調です。同様に、行の最小値が右上隅と左下隅にある 2×2 サブ行列が存在しない場合、その行列は完全に単調です。すべてのMonge 配列は完全に単調ですが、その逆は必ずしも当てはまりません。

SMAWK アルゴリズムでは、検索する行列を関数として定義する必要があり、この関数はアルゴリズムへの入力として（行列の次元とともに）与えられます。その後、アルゴリズムは特定の行列セルの値を知る必要があるときはいつでも関数を評価します。この評価にO ( 1 ) かかる場合、 r行c列の行列の場合、実行時間と関数評価の回数はどちらもO ( c (1 + log( r / c )) になります。これは、すべての行列セルを評価する単純なアルゴリズムのO ( r c ) 時間よりもはるかに高速です。

方法

アルゴリズムの基本的な考え方は、解決する問題を、定数倍だけサイズが小さい同じタイプの単一の再帰的サブ問題に縮小する、プルーンおよび検索戦略に従うことです。これを行うために、アルゴリズムは最初に、グラハムスキャンおよびすべての最も近い小さい値アルゴリズムのものと類似したスタックベースのアルゴリズムを使用して、行の最小値を含むことができない列の一部を削除するようにマトリックスを前処理します。アルゴリズムのこのフェーズの後、残りの列の数は最大で行の数と等しくなります。次に、アルゴリズムは自分自身を再帰的に呼び出して、マトリックスの偶数行の行の最小値を見つけます。最後に、連続する偶数行の最小値の位置の間の列を検索することにより、アルゴリズムは奇数行の残りの最小値を埋めます。

アプリケーション

Aggarwalらによる原著論文で発表されたこの方法の主な応用分野は、計算幾何学、凸多角形の各点から最も遠い点の検出、最適な囲み多角形の検出でした。その後の研究では、同じアルゴリズムが段落の行分割^[2] 、[RNA 二次構造予測]、^[3]、[ DNAおよびタンパク質配列アライメント] 、^[4]、^[5]、プレフィックスコードの構築^[6]、画像のしきい値設定^[7]などに応用されていることがわかりました。

参考文献

^ アガーワル、アロック;クローウェ、マリア・M .;モラン、シュロモ;ショア、ピーター; ウィルバー、ロバート (1987)、「行列探索アルゴリズムの幾何学的応用」、アルゴリズミカ、2 (1–4): 195–208、doi :10.1007/BF01840359、MR 0895444。
^ ウィルバー、ロバート（1988）、「凹最小重み部分列問題の再考」、アルゴリズムジャーナル、9（3）：418–425、doi：10.1016 / 0196-6774（88）90032-6、MR 0955150
^ Larmore, Lawrence L. ; Schieber, Baruch (1991)、「RNA二次構造の予測への応用を伴うオンライン動的プログラミング」、Journal of Algorithms、12 (3): 490–515、doi :10.1016/0196-6774(91)90016-R、MR 1114923。
^ Russo, Luís MS (2012)、「シーケンスアラインメントのモンジュ特性」、理論計算機科学、423 :30–49、doi : 10.1016/j.tcs.2011.12.068、MR 2887979。
^ Crochemore, Maxime; Landau, Gad M.; Ziv-Ukelson, Michal (2003)、「制限のないスコアリング行列のサブ二次シーケンスアラインメントアルゴリズム」、SIAM Journal on Computing、32 (6): 1654–1673 (電子版)、CiteSeerX 10.1.1.57.8562、doi :10.1137/S0097539702402007、MR 2034254 。
^ ブラッドフォード、フィル; ゴリン、モーデカイ J.;ラーモア、ローレンス L .;リッター、ウォイチェフ(2002)、「不等文字コストの最適なプレフィックスフリーコード: モンジュ特性による動的プログラミング」、アルゴリズムジャーナル、42 (2): 277–303、CiteSeerX 10.1.1.45.5501、doi :10.1006/jagm.2002.1213、MR 1895977 。
^ Luessi, M.; Eichmann, M.; Schuster, GM; Katsaggelos, AK (2006)、「効率的な最適マルチレベル画像閾値処理に関する新しい結果」、IEEE International Conference on Image Processing、pp. 773–776、CiteSeerX 10.1.1.461.663、doi :10.1109/ICIP.2006.312426、ISBN 978-1-4244-0480-3。

[smawk-1] アガーワル、アロック;クローウェ、マリア・M .;モラン、シュロモ;ショア、ピーター; ウィルバー、ロバート (1987)、「行列探索アルゴリズムの幾何学的応用」、アルゴリズミカ、2 (1–4): 195–208、doi :10.1007/BF01840359、MR 0895444。

[2] ウィルバー、ロバート（1988）、「凹最小重み部分列問題の再考」、アルゴリズムジャーナル、9（3）：418–425、doi：10.1016 / 0196-6774（88）90032-6、MR 0955150

[3] Larmore, Lawrence L. ; Schieber, Baruch (1991)、「RNA二次構造の予測への応用を伴うオンライン動的プログラミング」、Journal of Algorithms、12 (3): 490–515、doi :10.1016/0196-6774(91)90016-R、MR 1114923。

[4] Russo, Luís MS (2012)、「シーケンスアラインメントのモンジュ特性」、理論計算機科学、423 :30–49、doi : 10.1016/j.tcs.2011.12.068、MR 2887979。

[5] Crochemore, Maxime; Landau, Gad M.; Ziv-Ukelson, Michal (2003)、「制限のないスコアリング行列のサブ二次シーケンスアラインメントアルゴリズム」、SIAM Journal on Computing、32 (6): 1654–1673 (電子版)、CiteSeerX 10.1.1.57.8562、doi :10.1137/S0097539702402007、MR 2034254 。

[6] ブラッドフォード、フィル; ゴリン、モーデカイ J.;ラーモア、ローレンス L .;リッター、ウォイチェフ(2002)、「不等文字コストの最適なプレフィックスフリーコード: モンジュ特性による動的プログラミング」、アルゴリズムジャーナル、42 (2): 277–303、CiteSeerX 10.1.1.45.5501、doi :10.1006/jagm.2002.1213、MR 1895977 。

[7] Luessi, M.; Eichmann, M.; Schuster, GM; Katsaggelos, AK (2006)、「効率的な最適マルチレベル画像閾値処理に関する新しい結果」、IEEE International Conference on Image Processing、pp. 773–776、CiteSeerX 10.1.1.461.663、doi :10.1109/ICIP.2006.312426、ISBN 978-1-4244-0480-3。