« 「つながり」の進化生物学 | トップページ | 気候変動を理学する―― 古気候学が変える地球環境観 »

2014年1月18日 (土)

驚きの数学 巡回セールスマン問題

a■ 書籍情報

驚きの数学 巡回セールスマン問題   【驚きの数学 巡回セールスマン問題】(#2255)

  ウィリアム・J・クック (著), 松浦俊輔 (翻訳)
  価格: ¥3360 (税込)
  青土社(2013/5/23)

 本書は、「特定のリストにある都市をすべて訪れて出発点に戻る最短距離のルートを計算する」という「悪名高い」問題について、「ありとあらゆる答えを順序よく並べることがそれ程の手間だとしても、それでセールスマン問題が実際に難しことが納得できるわけでは決してない。これと似た、解き方は簡単なのに、候補となる答えがセールスマンがたどりうるルートの数よりもはるかに多いという問題は、他にもいくつかある。巡回セールスマン問題が別格なのは、世界中にいる一流の応用数学者が何十年も調べていながら、一般的に、単純に力任せで調べる以上に大きく改善する方法が知られていないところ」だとして、「巡回セールスマン問題がすたれない強みの一つは、それが応用数学、特にオペレーション・リサーチや数学的計画法といった分野での発見を生み出す原動力として著しく成功しているところだ」と述べた上で、本書の目的は、「この数学の難問を解くための方法を読者に自分で追いかける気になってもらうことだ」と述べています。
 第1章「手強い問題」では、「巡回セールスマン問題(トラヴェリング・セールスマン・プロブレム)」、略して「TSP」について、「一般的な形で言えば、都市名と、リストに載ったそれぞれの都市間の距離が与えられる。問題は各都市を回って出発点に戻る最短距離を見つけることだ」とした上で、「この問題は一般に易しいのか、難しいのか、それとも解けないのか。簡単に答えれば、本当は誰もしらない。そこがこの計算数学の世界で有名な難問の謎であり魅力だ。そしてセールスマンの悩みを解決するよりずっと大きなことがそこにかかってくる。TSPは複雑性の正体や人間の知識にありうる限界という、もっと広い論争の焦点なのだ」と述べています。
 そして、本書の目的として、「読者にTSPの基礎になじんでもらうレベルをはるかに超えて、理論の現状と最先端の解決手段のところまで進んでもらうことをもくろんでいる。究極の目標は、読者に自分でもセールスマンを追いかけようという気持ちになってもらい、できることなら、まだ知られていない方向から決定打が出てくることだ」としています。
 第2章「問題の由来」では、巡回セールスマン問題の「祖父」として、オイラーとハミルトンの名を挙げ、オイラーが1735年に提出したケーニヒスベルクの橋に関する論文が、「必要な情報だけを抽出して問題の本質を捉える古典的な数学の方向をたどっており、オイラーはそうすることによって、グラフ理論と呼ばれる新しく重要な数学の分野の基礎を敷いた」と述べるとともに、ハミルトンも「特定のグラフのたどり方に関する問題に惹かれた」として、オイラーから1世紀後に正十二面体の20の頂点をすべて通る道を調べたと述べています。。
 そして、グラフにおいて、「各頂点を一度ずつだけ通る閉じた散歩」である「ハミルトン閉路」と、「各辺を一度ずつ通る閉じた散歩」である「オイラー小道」について、「どちらの散歩もグラフ理論では根本的な概念だが、明らかな類似はあっても両者間の違いも大きい」と述べ、「グラフにハミルトン閉路があるかどうかを判定するのはNP完全問題で、TSP一般にある複雑さの大部分を捉えている」が、「グラフにオイラー小道があるかどうかの判定には、単純な規則がある」として、「一体になっていて、各頂点は偶数本の辺の端となっていなければならない」と述べています。
 第3章「実地のセールスマン問題」では、「人や乗り物の動きから目を転じると、TSPを元にした驚きの使い方が見つかる」として、遺伝子研究の分野で焦点となっている「遺伝子地図の目印として使われるマーカーの正確な位置」についての情報を得る上でTSPが出番が生じると述べています。
 また、「TSPは、コンピュータでコード化された音楽の膨大な集合を読み取るためにも使われている」として、日本の産業技術総合研究所が開発した「人が自分の音楽上の趣味に合いそうな新しいアーティストを発見するのを助けてくれる」システムである「ミュージックレインボー」について解説しています。
 第4章「巡回路探し」では、「1匹のアリの動きは気まぐれでも群れ全体ではフェロモンの痕跡を通じて連絡し、効率的なルートを見つけている。この集団行動が“蟻コロニー最適化(ACO)と呼ばれるTSPがヒューリスティック群の元になる」と述べています。
 そして、「ヒューリスティックな方法は実行時間と巡回路の質との釣り合いを取らなければならない。最高品質のものについては、膨大な時間をかけて実際に可能な中で最善の回を出そうとする。これはF1レースのようなレベルで、参加者は、課題となるデータセットを回る既知の最善の長さを縮めるため、あらゆる手段を使う」と述べています。
 第3章「線形計画法」では、「一群の点を通る最善の巡回路を選び、それが最善であることを確かめるのがTSPの課題の全体となる。あらゆる順列を並べ替える力任せのアルゴリズムを使えば確実にこの課題をこなすことができるがそのような手法にはわかりにくいところもない代わりにすでにお分かりのとおり、実用的な効率に欠ける。必要なのは、順列をいちいち調べなくても巡回路の質を保証する手段だ。この脈絡では、線形計画法という驚くほど効果的な方法がお薦めの道具となる。これによって、すべての巡回路が満たす多数の単純な条件を組み合わせて、『この点集合すべてを通る巡回路でXより短くなりうるものはない』という形の単独の規則が得られる。数Xは直接に質を表す尺度となる。長さXの巡回路を創ることもできれば、それはたしかに最適解だと考えられる」と述べています。
 そして、「産業界で線形計画法を使える範囲は息をのむほどで、名前が上がるどんな分野にも及ぶ。定量化することが難しいとはいえ、線形計画法による計画が、世界中の膨大な量の自然資源を日々節約しているのは明らかだ」と述べています。
 第6章「切除平面」では、「LP問題全体を一発で解こうとはせず、LP限界を『その都度払い』方式で計算して、必要な時だけ特定のTSP不等式を生成する」という「複雑な問題を処理するためのスッキリとしたアイデア」について、「これはゲームのあり方を変えたし、セールスマン問題だけの話でもなかった」と述べています。
 第9章「複雑性」でが、「セールスマン問題を都市数をますます大きくしてとこうとすることで、数学、計算、工学に飛躍がもたらされ、また多くの実用的な応用面でも前進があった。それこそがTSP研究者の埃であり、喜びだ。しかし一歩ずつ進める方式ではTSPのすべての例を効率的に解けるかという、究極の複雑性の問題は解けない」とした上で、「セールスマン問題の一般的な複雑性についてわかっていること、わかっていないことを解説」しています。
 本書は、有名な数学の難題について、何がわかっていて何がわかっていないのかをわかりやすく解説した一冊です。


■ 個人的な視点から

 グラフ理論は人間関係をはじめとするネットワークを理解する上で必修課題ではないかと思うのでTSPがこれからも色々なネットワーク問題をとくツールになってくれることを期待しています。


■ どんな人にオススメ?

・ネットワークのグラフを理解したい人。


« 「つながり」の進化生物学 | トップページ | 気候変動を理学する―― 古気候学が変える地球環境観 »

その他科学」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/1244312/54598830

この記事へのトラックバック一覧です: 驚きの数学 巡回セールスマン問題:

« 「つながり」の進化生物学 | トップページ | 気候変動を理学する―― 古気候学が変える地球環境観 »

2016年12月
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

最近のトラックバック

無料ブログはココログ