contemporary algorithm 07

先週の講義の続き。

直線上に、サーバーを配置する。

ランダムなリクエストに基づいて、サーバを、要求地点に移動させていく。
移動距離のコストを最小にする戦略を探求する。
double coverageという戦略をとった場合、それは、optimumなコストより、
どれくらい、無駄が発生するのかを計算する。

ここまでが、online　algorithm

今回の講義から
approximation algorithmというトピックに入る。

具体例　１
時間割のスケジューリング

いろいろな、科目を、曜日、時間を違えて、配置する。
その時間割に対して、すべての必修科目を履修できる学生が全体の何割なのかを
計算するみたいな。
学生、一人、一人はそれぞれの都合により、いろいろな事情がある。
すべての学生にとって満足のいく時間割を作ることができるのかどうか。

ここで、現実的にはそんなことはできないという前提をうけいれる。

それでは、全体の学生のうちの８５パーセントは、納得できる時間割をつくることが
できるかどうかという問題にすこし組み替える。
そして、そのようにした場合のアルゴリズムの「性能」「コスト」を評価するにはどうすれば
いいのかを、数学的につめていく。

具体例　２
荷物のパッキング
ある一定の体積の荷物を詰め込むことができるコンテナを、任意の数用意する。
そして、様々な体積をもつ、いろいろな荷物の集合を仮定する。

１００立方のコンテナには、２０立方、３０立方、５０立方の三つの荷物が入るみたいな状況。

出来るだけ、すくないコンテナで、すべての荷物を詰め込みたい。
どのような戦略をとるべきか？

ここでも、
まず荷物の合計の体積を計算して、「理想的なコンテナの最小数」を計算する。
２０、３０、５０立方の荷物しかなければ、１００立方のコンテナは１つでいいみたいな計算。

First Fitという戦略を立て場合、
せいぜい、いくつのコンテナを用意すれば、すべての荷物の梱包が可能なのかを計算する。