書評：「最短経路の本－レナのふしぎな数学の旅」
P. グリッツマン，R. ブランデンベルク 著，石田基広 訳
シュプリンガー・ジャパン
慶應義塾大学理工学部 小田芳彰
この夏に車を買い換え，ようやく我が家の車にもカーナビがつきました．カーナビは想像していた以上に便利です．
目的地を設定するだけで，わずか数秒後には早くたどりつけそうなルートを教えてくれます．また，その時の渋滞情報も加味してルートを計算しているようです．これを使うようになると，道路を覚えられなくなるなと痛感しました．携
帯電話を持ち始めてから，覚えている電話番号の数がぐっと減ったことを思い出します…．

『最短経路の本』は，ドイツ数学会の元会長グリッツマンと若手研究者ブランデンベルクによって書かれた “Das Geheimnis des kürzesten Weges’’（最短経路の秘密）の邦訳本である．本の帯に「ドイツで実売１万部突破！」と書かれており，数学に関する本としては異例の売れ行きだったことがうかがえる．主な登場人物は次の２人＋１本である．
・ レナ ドイツミュンヘンに暮らす数学が苦手な（という割に飲み込みが早い気がする）女子高生．
・ ヤン レナの高校の同級生．
・ ビム 人間と対話ができるソフトウェア．
本書の物語は，レナが父からパソコンをもらったところから始まる．そのパソコンの中にはビムという人間と対話できるソフトウェアが入っており，ビムは数学にまつわるいろいろな話をレナに教えてくれる．高校の数学は苦手だが，レナは経路に関する問題に興味を持ち始める．
読み始めて最初に思ったことは，「とても読みやすい」．この一言につきる．この物語は 32 節からなるが，一節一節の分量はそれほど多くない．また，どの節もレナとその家族や友人の話題がちりばめられていて，そのストーリーも楽しい．数学にあまりなじみがない人にとっても気軽に読み進められる本である．また，登場する問題は地図上のさまざまな条件をみたす最短経路を探すというものであり，いずれの問題もわれわれにとって身近な題材が対象になっている．しかしながら，簡単なお話で終わることなく，NP 困難や分枝限定法など大学レベルの情報科学のトピックにふみこみ，ていねいに説明されている．また，グラフ理論の基本的な性質をきちんとおさえていたり，曖昧さをなくすためにきちんとアルゴリズムが記述されていたり，アルゴリズムの正当性を背理法により証明していたりするところもある．最近，大学教員は高校生向けに体験講座や出張講義を行う機会が増えているが，こうした準備をする際にもよい参考書籍になりそうである．

次に，この本の数学の話題に焦点をしぼって述べていく．
まず，冒頭でも述べたカーナビを支える最短経路問題から始まる．最短経路問題とは，グラフ理論における有名な問題の１つで，いくつかの都市と各都市間の距離のわかる地図が与えられたとき，その地図上の指定した２都市（現在地，目的地）間を結ぶ最短経路を求める問題である．この問題は，例えば１９５９年にダイクストラが示したアルゴリズムを用いると，地図上の都市の数が増えても実用的な時間（多項式時間）で解けることが知られている．そのおかげで，カーナビで目的地までの経路を計算させると，わずか数秒で画面上にルートが表示できるわけである．この本では，ミュンヘンの地下鉄路線図上の２駅間の最短経路について，各辺に重みがついた重みつきグラフを用いてレナとビムの対話が進められていく．
さらに，負の重みの辺がある場合の難しさについても述べられている．
次に，話題は最小全域木問題に移る．この問題は重みつきグラフ上の全域木の中で重みの和が最小のものを見つける問題である．この問題は電話回線のネットワークの最適化などへの応用がある．この問題に対して，プリムのアルゴリズムやクルスカルのアルゴリズムが紹介されているが，それだけにとどまらず，最小全域木がグリーディアルゴリズムで得られることとマトロイドとの関係についてもふれられている．
続いて，グラフ理論の始まりとされているケーニヒスベルクの問題，一筆書きを数学的に表現する
オイラー閉路（小路），そして，中国の郵便配達人問題へ話が広がっていく．中国の郵便配達人問題とは，１人の郵便配達人が地図上のすべての道路をまわって配達をし，出発点に戻ってくるとき，総移動距離が最小になる経路を見つける問題である．この問題に対しては，オイラー閉路だけでなく，グラフのマッチングに関する概念も必要となる．無向グラフ，有向グラフの場合は多項式時間で解けることがわかっているが，この問題の面白いところの１つは，向きのない辺と向きのある辺がまざったミックスグラフ上では急に状況が変わり，計算量理論の観点でも難しくなるところである． （この結果にまでふれられているのには少し驚いた．
）
そして，巡回セールスマン問題．この問題は私が学生のころから興味を持って取り組んでいる問題の１つである．

巡回セールスマン問題 セールスマンが会社を出発し，いくつかの顧客先をすべて訪問し，会社に戻ってくるとき，総移動距離が最小になるようにまわりたい．そのような経路（巡回路）を求めよ．

グラフ理論の用語を用いると，この問題は，重みつきグラフ上の重みの和が最小のハミルトン閉路を求める問題ということもできる．この問題は都市（頂点）数が増えるにつれ，計算時間が指数的に増加するアルゴリズムしか知られておらず，多項式時間で求められるアルゴリズムは存在しないだろうと予想されている．計算量理論の分野では，この問題は NP 困難に属すると言われ，こうした NP困難に属する問題が多項式時間で解けるかどうかはわかっておらず，P vs NP 問題とよばれる有名な未解決問題の１つになっている．この NP 困難に関する理論体系についてもこの本では述べられている．さらに，近似解法で得られる解と最適解との間の誤差の精度の話や多項式時間で終了する保証はないけれども高速に解を得る手法の１つである分枝限定法についてもわかりやすく書かれている．
本書には関連するさまざまな web ページの URL が掲載されている．インターネットに接続されたパソコンが氾濫している今日では，書籍の参考文献に比べて有益な情報だと始めは思ったのだが，デッドリンクになっているものが少なくなく，残念だった．しかし，その一部については，訳者が似た情報を含むサイトを注で書き加えており，読者にとってはとてもありがたいと思った．
最後に，この本に似た書籍として，[1]についても述べておきたい．この本は巡回セールスマン問題だけに焦点をあてて書かれているので，その分内容は濃いが，対話形式で書かれていてとてもおもしろい．私はこの本を学生時代に買ったが，いまでも時々読み返すことがある．また，巡回セールスマン問題に関する研究をもっと深く知りたいという方には[2,3]も詳しくまとめられており，おすすめである．

もう１つだけ．物語の中でレナが友人のマルティーナと「チケットトゥライド」というボードゲームで遊んだという話が出てきます．これは，高得点を目指して，指定された２都市をつないでいくゲームです．今夏のゼミ合宿で学生がたまたま持ってきてくれたゲームの１つだったのでよく覚えています．他のプレイヤーの操作を妨げたり，最短経路以外の要素が点数に加わるので，ルールは少し複雑でしたが，慣れてくるととてもおもしろいです．合宿では学生たちと夜中までこのゲームに興じてしまいました．これもおすすめです．

参考文献[1] 山本芳嗣，久保幹雄，「巡回セールスマン問題への招待」，朝倉書店，1997．
[2] D. L. Applegate, R. E. Bixby, V. Chvátal and W. J. Cook, The Traveling Salesman Problem - A
Computational Study, Princeton University Press, 2006.
[3] G. Gutin and A. P. Punnen, eds., The Traveling Salesman Problem and Its Variations,Springer, 2002.