HiKaLo Books No.8 研究紹介

研究紹介トップへ

群馬大学

群馬大学工学研究科
博士後期課程　電子情報工学専攻1年
　　岡下　綾


	当研究トップへ

1.	はじめに

2.	アルゴリズムとは何か？

3.	難しい問題を解くためには

4.	中野先生の研究について

5.	中野先生について

6.	おわりに

群馬大学工学部　情報工学科
　　中野　眞一　助教授

３．難しい問題を解くためには

　世の中に存在する問題は様々な条件を考えなければならないため、一般に難しい問題となります。実際に考えられる問題の例として、トラックが荷物を顧客の元に配送するとき、どのトラックが、どの顧客を、どの順番で配送すれば最も効率が良いかという問題を考えます。荷物を顧客に配送するとき、いろいろな条件を考える必要があります。

図1：様々な条件付の配送問題の例

例えば、トラックの最大積載量や1日に走れる距離と時間は決まっているでしょうし、各顧客は何時から何時までに荷物を届けて欲しいと指定してくるかもしれません。このような条件をなるべく満たすような配送ルートを考える問題を配送計画といいます。顧客の数が少ない場合には、人間が直感に頼って配送ルートを考えても、それなりに効率の良い解が得られるでしょう。しかし、実際には顧客の数はかなり多くなってしまうので、人間が直感や手計算で良い配送ルートを見つけることは不可能です。この顧客を早く回った方が信号に引っかからないから早く済むとか、そのような部分については人間の経験の方が優れているのですが、全体的な計画に関してはコンピュータに解かせた方が人間の解いたものより優れているようです。1割から3割程度のコスト減が得られるという報告もあります。

　残念ながら、最もコストが低い配送ルート（最適な配送ルート）を探す問題はコンピュータを使っても膨大な計算時間を必要とします。最適な配送ルートを“高速に”見つける問題はNP完全問題と呼ばれる非常に難しい問題の内の一つです。これまでに何十年も世界中の天才達がNP完全問題について研究してきましたが、効率の良いアルゴリズムが存在するのかさえ分かっていません。この問題は顧客の数が50程度でも、解を求めるために数日かかってしまうこともあります。

そこで最適な配送ルートではなく、許容できる範囲での誤差を認めて、高速にそれなりにコストの低い配送ルートを求める問題を考えるのが自然です。この場合はうまく技を効かせて問題を解くと、顧客の数が3000くらいに増えても何とか解を求めることができます。このように、メモリや時間を破綻せずに、解を妥協することによって問題を解決しようという方針を近似解法といいます。