SMAWK algorithm

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /smawk-algorithm#noredirect を利用してください。
name
SMAWK algorithm
short description
SMAWK algorithm とは、totally monotone な $H \times W$ 行列に対しその各行の最小値を $O(H + W)$ で求めるアルゴリズムである。
input
totally monotone な $H \times W$ 行列 $f$
output
それぞれの行 $y$ に対し最小値の位置 $x \in \mathrm{argmin} _ x f(y, x)$
time complexity
$O(H + W)$

説明

概要

SMAWK algorithm とは、totally monotone な $H \times W$ 行列 $f$ に対し、それぞれの行 $y$ の最小値の位置 (のひとつ) $x \in \mathrm{argmin} _ x f(y, x)$ をまとめて効率よく求めるアルゴリズムである。愚直には行列全体を走査して $O(HW)$ であるが、これを $O(H + W)$ で行う。仮定を強めることで monotone minima をより高速にしたようなアルゴリズムである。

入力となる行列のそれぞれの行は distinct (重複を持たない) だと仮定されることがあるが、この制約は取り除ける。ただし、ひとつの行に最小値が複数回出現する場合への注意が必要となる。 SMAWK algorithm はそれぞれの行 $y$ について最小値の位置 $x_y$ を出力するが、これを $(x_0, x_1, \dots, x _ {H-1})$ とならべた列は必ず広義単調増加となる。この性質はアルゴリズム自体の内部でも用いられる。

詳細

(省略)

totally monotone について

totally monotone の定義について。$H, W$ は自然数とし $A$ は全順序集合とする。$H \times W$ の行列 $f : H \times W \to A$ が totally monotone であるとは、$f$ の任意の $2 \times 2$ 部分行列 $\begin{pmatrix} a & b \cr c & d \end{pmatrix}$ が $c \lt d$ ならば $a \lt b$ を満たしかつ $c = d$ ならば $a \le b$ を満たすこと。

定義の対偶のようなものを考えると次が言える: $f$ の任意の $2 \times 2$ 部分行列 $\begin{pmatrix} a & b \cr c & d \end{pmatrix}$ が $a \gt b$ ならば $c \gt d$ を満たしかつ $a = b$ ならば $c \ge d$ を満たす。 また、totally monotone な行列は任意の行や列を削除しても totally monotone なままに保たれる。

totally monotone であることは $f$ の任意の部分行列が monotone であることと同値である。その自明な場合として、totally monotone な行列は monotone な行列でもあることが言える。

その他

参考文献

関連項目

外部リンク