■

漢字の変換にまつわるアルゴリズムのコスト計算について引き続き。

一度、選択された漢字の変換パターンを、一番先頭に出てくるように、変換される熟語のパターンの順番を
変えるという戦略をとった場合のその後の話。

そのパターンに対して、次の変換のリクエストが一番、コストがかかるように、入力を繰り返すという
ことをした場合に、
この操作をn回繰り返した時のコストの計算をする。

このようなmaliciousな入力に対して、コストを最小にするための方策をとっていく。

漢字の変換のリクエストがどういう形で登場するのかは、不明。（未来のinputだから。）

そういう不確定な要素があったとしても、
変換パターンの順番をかえていく戦略を一つに決定したとき、そのコストがせいぜい、どれくらいになるのかは
数学的証明によってわかるというトピック。（リクエストがあった漢字のパターンを、列の先頭にもってくるMTFという戦略の
コストの計算になる。）

＝＝＝＝＝
k server

座標平面上に、k個のサーバーを配置する。
その座標平面上のどこかの点において、「どのサーバーでもよいので、この地点までそのサーバーを移動せよ。」
というリクエストが、ランダムにくるという設定。

事前に、どの地点にくるのかということはわからない。（だからonline algorithm)

あるサーバーを、リクエストがきた地点に運ぶときの、移動距離がコストになる。

n回のリクエストに対して、どういうサーバーの選択の仕方と、移動の仕方が、
移動距離コストを最小にするのかということを計算で行う。

比較対象されるのは
greedy strategy　　リクエストのあった地点から一番近いサーバーを動かす。

double coverage　　リクエストのあった地点の両端に存在するサーバを同じ距離だけ動かしていく。

という二つの戦略。直感的にはGreedy strategyのほうが、安上がりになりそうだけど。
そうはなりませんというお話。
double coverageという戦略をとったほうが、安上がりになることを数学的に証明していく。