■
前回に引き続き、近似アルゴリズム
いろいろな体積をもつ複数の荷物を
一定の体積のBinつまりコンテナーに格納するという場面。
出来る限り、最小のコンテナーの数で、すべての荷物を格納することをめざす。
この目的達成に対して、First Fitという戦略が、理想的なコンテナの数（荷物の体積の和を、コンテナの体積で割った数）
から、最大、どれくらい乖離するのかの計算。
以下がFirst Fit
荷物を一つ、一つ、Binにいれていく。
これ以上、入らないと判断したら次のBinに格納する。
荷物の体積が、以前のBinに収容可能な値であれば、そのBinに格納する。
＝＝＝＝＝
さらに別の具体例。
任意の整数の集合を仮定する。
その整数の集合の部分集合をランダムに作成する。
部分集合をいくつか組み合わせることで、最初に設定した任意の整数の集合をつくるという作業。
（1,2,3,4,5,6,7)
その部分集合
(1,4,5,7)
(3,4,5)
(2,6)
(5,6,7)
(1,3,5)
(1,5,7)
この部分集合をジグソーのように組み合わせることで、元の集合をつくる。
Greedyという戦略をとった場合に、
それが、理想的な最小の部分集合の組み合わせからどれくらい乖離するのかを
計算する。
（部分集合の取り方によっては、Greedyの原則に忠実に元の集合をつくろうとするほうが
手数が多くなる場合があり得るという問題意識）実際に、そういう場合も例示されている。
Greedyという戦略を一度、決定すると、コンピュータは、裁量の余地なく、
元の集合が完成するまで、自動的に、作業を、いつまでも続ける。
Greedyの戦略は、最初の選択で、最大限の数を、うめてしまおうとする。
次の選択では、２番目におおい数をうめてしまおうとする。
途中、この部分集合を一つ選択するにつき、１＄の支払いが発生するというコストを
設定する。
１＄を部分集合の要素の数でわると、その数、一つ一つを調達するのにかかるコストが
設定されることになる。
任意の数(item）を選択したとき、そのitemの価格は精々いくらになるのかということを
数学的証明によって明らかにする。
Traveling sales person Problem
座標平面上に、任意の点を設定する。
すべての点を１回ずつ通過しながら、巡回するのに、どれくらいの距離を歩く必要があるのかという問題。
地点と地点を結ぶ辺で構成される三角形の長さは三角不等式の条件を目指しているものとする。
この応用というか、変形のバージョンとして、
任意の点を座標平面に配置する。
その点と点の間を、適当に道路で結ぶ。
この道路によってとなり地点が、同じ色で塗りつぶされてはいけない。
それでは、なるべく、最小の色の数で、この地点すべてを塗り分けなさいという問題も扱う。
離散数学は三年生の夏学期、つまりこの学科の最初の学期に行われる必修の授業です。
これは文字どおり離散的な、連続でない対象を扱う数学です。例えば離散的な問題の例として、順列や組み合わせをしらみつぶしに調べる問題などは、コンピュータを用いて解くとよいのですが、その効率的な解法の設計や研究は重要です。というのは、ある問題を解く(コンピュータに解かせる)のに要する時間は解法の設計に大きく依存するからです。設計が悪いために解けるはずの問題が現実的な時間内に解けなくなることさえあります。
この講義では離散数学とその手法を用いたアルゴリズムの設計や解析の初歩を学びます。
離散数学の例え話＊＊離散数学的問題の例 「巡回セールスマン問題」
―商品を売ろう。ある営業マンの今日の予定。
-鈴木さん、田中さん、高橋さん、澤さんの４件のお宅にお邪魔し、商品のプレゼンテーションをしたいと思います。
-会社から出発して４件のお宅を全て訪問し、出来るだけ早く会社に帰って来たいと思います(*1)
-早く移動できるルートもあれば、ひどく時間がかかってしまうルートもあります。どういう風に巡回すれば最も効率的か。各ルート毎に所要時間が分かっていて、図にすると以下のようになっているとします。
(* 画像 pict.GIF*)
元来、このような問題は数学としては低級な問題とみなされてきました。全ての場合を網羅すれは必ず解けることがただちにわかるからです。ところが、
訪問するのが、たった４件のお宅でも、
(会社) → １ → ２ → ３ → ４ → (会社)
可能なルートは
4！ ＝ 24
通りあります。訪問する場所が増えれば当然、可能なルートは階乗で増えていきます。コンピュータがいくら人間より高速に計算できるからといえ、たとえば話を世界規模に持っていって「１００都市を巡回する」ように考えると、１秒間に１０億個の順列を作り出せるコンピュータを用いても１００億世紀以上かかってしまうことが単純計算でわかります。つまり、「全ての場合を網羅すれば解けるはずであるが、それが現実的に不可能」であるということです。このような状況、問題に対処する方法を数学的に考える。これも離散数学の分野です。
実はこの「巡回セールスマン問題」は難しく、問題の規模がある程度大きいときに現実的な時間内で厳密に解けるような方法(アルゴリズム)は発見されていません。ここでは解法のいくつかを紹介したいと思います。＜近似的な解法の例＞ 欲張り法(Greedy Algorithm)
方針：現在地から次の目的地へ最もコストの掛からないルートを毎回選択。
コストの最小値だけを調べればよいので、総当りよりは圧倒的に早い。単純な方法。
会社 → 澤さん → 高橋さん → 鈴木さん → 田中さん → 会社 (4.7時間)
この問題では実は最適解です。
が、この方針は精度に関してはいくらでも悪くなります。(田中→会社間が10000時間かかるようになっていても、このアルゴリズムではここを選ばざるを得ません)
まとめ巡回セールスマン問題を例にお話させて頂きましたが、この問題は離散数学の体系のなかでは「グラフ理論」という分類になります。この「グラフ理論」は現実への応用分野も実に広く、たとえばデッドロックの検出、コンピュータネットワーク(インターネット)の構造モデル化、はたまた集積回路の設計にまで役に立っています。
また、これに限らず離散的な値を考えなければならない問題というのはあちこちにあり、線形計画問題、マトロイド、組み合わせ論などがあります。
線形計画問題せっかくなので、もうひとつ、離散数学の問題を見てみましょう。
