第5話 巡回セールスマン問題
第5話 巡回セールスマン問題
「いよいよ巡回セールスマン問題の説明をするね。あるセールスマンがいるとして、Nの都市が存在して、そのセールスマンは各都市の市役所に営業にいくとするんだ。このとき、どういう順番で都市を訪れると最短ルートで営業できますか？というのが命題さ」
「命題はわかるような気がしますね」
「どのくらいのルート数が存在するか計算すると、正確には（N－1）！／2になるけどランダウ記法にすると定数は除外されるからO(N!)になるよね。都市の数が30、つまりN=30として計算すると、だいたい10の32乗のルートが存在するんだ。この中から最短ルートを導き出しなさいという命題なんだよ」
「10の32乗とは、どのくらいの数なんですか？」
「膨大な数ということだよ。たったの30都市でこのくらいだから1万都市もあったら大変だよね。そこでこの命題を解決しようと思うんだ」
「え、どうやって？」
「これから説明するね。先ず全ての都市間に道が通っているとするから、これは完全グラフになるんだ。次が大事だよ。分割対象要素と分割条件を見つけるんだ。利助さんにやってもらいたいのはここなんだ。例えば、巡回セールスマン問題では分割対象要素は線分で分割条件は“最短ルートには交差する線分は存在しない”になるね」
「は～、線分とは点を結んだ線のことでしょうか？交差しないとは線と線が交差しないということでしょうか？」
「そうだよ。簡単でしょ。でも見つけるのには難儀したよ。で、どうして線分と線分が交差するルートは最短距離とならないかは利助さんの宿題にしよう。簡単に分かるよ。でもわからないからといって、先に進めないことは無いけどね。その条件が真だと信じればいいだけだからね」
「宿題はできるかどうかわかりませんが、先に進んでみてください」
「ツリー構造は知っている？アルゴリズムの構築でよく使うのだけど」
「そっち方面はちょっと……」
「完全グラフに集合Lがあったよね。その要素全てを親ノードとしてツリーを構築するのだけど、ノードと分枝について説明するね。ノードは集合か要素1個かで作られて、要素1個のときは、それに1対1で関連付けられている集合のことだと考えて。つまり、ノードは集合だね。複数の集合のときもあるけど。分枝はその集合を一定の条件で分割した集合を置く場所かな。あ、そうだ。この一定の条件も考えて貰わなきゃ」
「ち、ちょっと待ってください。何がなにやらさっぱりと……」
桃九は興にのって説明しているが、利助の頭の中では混乱が渦巻いていた。やがて、桃九も諦めることになるのだが、今はまだ気が付いていない。
「もう少し聞いて。最初の親ノードは１つだけど、分枝した集合が次の親ノードになって、どんどん分枝していくのさ。こうやって集合をもう分割できませんというところまで分枝させたらツリー構造が完成するという仕組みなんだ。このとき、途中で一定の条件を変えないというところが大事だね」
まだ本論に入っていない桃九だったが、利助の限界はすぐそこに近づいてきていた。桃九は、最後まで説明し終えるのだが、利助には混乱だけが残ることとなる。続きは次話で。
