Algorithms/OnlineAlgorithm - tmura's note - atwiki（アットウィキ）

Algorithms > OnlineAlgorithm

オンラインアルゴリズム

入力が時間とともに与えられ、各時刻においてそれまでの入力のみから
その時点での行動を決めるアルゴリズムを、オンラインアルゴリズムとよぶ。

競合比 (competitive ratio)

オンラインアルゴリズムの性能を評価する方法の１つで、
アルゴリズムのコスト（あるいは利益）を、「神様」のコストと比較する。
「神様」とは、全ての入力を予め知っており、それに対して最適なアルゴリズムを採用できると想定する。

正確な定義は、次の通りである。
入力 $x$ に対するオンラインアルゴリズム $A$ のコストを $C_A(x)$ 、
また、その入力であることを最初から知っていて動作できる最適オフラインアルゴリズム
（optimal offline algorithm）のコストを $C_{OPT}(x)$ とする。
任意の $x$ に対して、ある定数 $d \geq 0$ が存在して、
$C_A(x) \leq rC_{OPT}(x) + d$
が成立するとき、 $A$ の競合比は $r$ であるという。
コストの値が十分大きくなるような入力に対して $d$ は無視できるので、
アルゴリズムのコストが最適コストのほぼ $r$ 倍以下であることを意味している。

なお、ある特定のオンラインアルゴリズムに対して意地の悪い入力を
「敵対者（adversary）の入力」と呼び、競合比の解析においては重要である。

競合比解析の手法が発見される前は、
入力の分布を仮定して平均的な性能を評価する流儀が終了だったが、
残念ながら解析が困難な場合が多かった。

代表的な問題

スキーレンタル問題

スキー用品を、レンタルすると１万円、購入すると１０万円かかるとする。
購入した場合、１シーズン中は使い続けられるとする。
１シーズン中に、スキーに行く機会が来るごとにレンタルするか購入するかを選択できるとして、
どのようなアルゴリズムをとるべきか？

線形リスト探索問題

いわゆる「かな/漢字変換プログラム」での、変換候補リストの並び順を決める問題で、
選択された要素を常に一番先頭に再配置するアルゴリズムであるMTF(Move To Front)が有名。
MTFの競合比は2以下であることが知られている。

ページ管理問題

いわゆるメモリのキャッシュ制御におけるページの入れ替え問題で、
LRU(Least Recent Used)アルゴリズムなどが有名。

CNN問題

イメージとしては、マンハッタンとか平城京みたいな碁盤の目のような街を考え、
そのどこかの交差点で、次から次に（時系列的に）事件が起き、
CNNテレビのクルーがカメラを持って、その場面を撮影に行くとする。
ただし、事件が起きた交差点そのものまで行かなくても、
その交差点を含む縦の通りか横の通りまで行けば事件現場を撮影できるとする。
各時点で、どのようにカメラクルーを移動させれば、コスト（移動距離）をなるべく小さくできるか？

一般に、オンラインアルゴリズムに対しては貪欲アルゴリズムが有効な場合が結構多いが、
CNN問題に対してはあまり向かない（競合比が発散してしまう）。

直角CNN問題の競合比に関する定理: CNN問題のうち、場面が縦か横にしか移動しない特殊な場合を直角CNN問題(Orthogonal CNN Problem)と呼ぶ。; つまり、ある時点での場面が $(i,j)$ であるなら、次の場面は $i$ または $j$ のどちらかが等しい。; 直角CNN問題に対しては、競合比9.0のアルゴリズムが存在する。