ダンジョンはアイドルのステージよ！ 転生者の私はゲーム世界で最強を目指す(←既に最強)

巡回アイドル問題

　カカオトレントのリポップ地点は全部で二十数か所あるのだけど、入り口から離れた所にいる数個体を除いた18匹を周回の対象にしている。

　私たちはまず上空写真を撮影し、その写真上にトレントのいる位置をプロットしてみた。

「こうやって見ると、いつもの巡回ルートは結構無駄が多かったんだね」

「この箇所とか、無駄が多そうだね」

「行ったり来たりしてる」

「こう周った方が近いよね～？　あれ、でもそれだとここが無駄している気がする……」

　カカオトレントのリポップ地点はバラバラに配置されていて、どう巡っていくのが最適なのかぱっと見では分からなかった。少なくとも、今の順路が良くないって分かっただけでも大きな成果ね。

「さあて、問題はここからどうやって最短経路を見つけるかなんだよね」

「数学の問題だね！」

「数学で解けるの、これ？　全通り試すしか方法がない気がするけど」

「パソコンに解いてもらうとか？」

　ハルちゃんは計算でどうにか求められると考えたみたいだけど、残念ながらこの問題を数式で解く方法は存在しない。リンちゃんが言うように、すべての順路について、その距離を求めていくしか解法がない。

　当然そんなの人間では出来ないのでコンピュータに解いてもらう事になる訳だけど、それはそれで問題があるのよね。

「この問題は手計算では解けないし、コンピュータでも解く事が出来ないのよ……」

「解けないの？！」

「コンピュータなら解けるんじゃあ……？」

「そんなに難しい問題なの？」

　コンピュータサイエンスでは有名な問題なのだけど、三人はピンと来ていないみたいね。リンちゃんも知らなかったか。むふふ、ちょっと優越感。

「巡回セールスマン問題って名前がついてるくらい重要かつ難しい問題なの。元はセールスマンがN個の都市へ営業に行くとき、その最短経路を示しなさいって言う問題ね」

「ふえー。それはセールスマンにとっては重要な問題だね！」

「一刻も早くノルマを終わらせて家へ帰りたい訳か」

「私たちの場合は巡回アイドルマン問題になるのかな～なんて♪」

「せめて巡回アイドル問題にしよ？　アイドルマンなんて職業無いよ！」

「あ、確かに。えへへ///」

　ネットで巡回セールスマン問題について紹介しているサイトがないか調べてみる。おや、いい記事を発見！　“巡回セールスマン問題を工夫せずに解く”って記事が見つかったわ。

　……この記事の執筆者の名前、なんとなく既視感があるわね。気のせいかしら？

「コホン。この記事によると、愚直に18か所を巡る最短経路を調べると、13年と6か月かかるらしいわね」

「13年？！」

「18×17×……×2×1通りの経路について、計算するわけだから……。なるほど、確かに果てしない計算量になる」

「それじゃあ、どうするの？」

「一応、工夫して計算することで処理時間を短縮する方法があるのだけど、それでもかなりの時間がかかるわ。だから、最適解を求めることは諦めて、代わりに『ヒューリスティック』な解法を使うわ」

「「「ひゅーりすてぃっく？」」」

　ヒューリスティックは「発見的」と言う意味なの。コンピュータサイエンスの分野では、良さそうな解答を発見してくるプログラムの事を指すわ。

　つまり、巡回セールスマン問題みたいな「解答を見つけるのが難しい問題」について、「ベストではないかもしれないけど比較的良い解答」を見つけてくる、言わば妥協案のようなプログラムになるわね。

　巡回セールスマン問題なら、適当な経路を初期状態として、それよりも短くなるように経路を調整、さらに調整、さらに調整っていう風に、少しづつ精度を上げていく方法なんかがあるわ。

　って訳でハルちゃん家の高性能PCをお借りしよう。

　ありがたい事に、今の時代大抵のプログラムはコピペ＆手直しで作れちゃうから、1時間もあれば実行できる状態になる。

◆

「で、出力された結果がこれ……。確かに今までよりもはるかに効率がよさそうだね」

「すごいね！　流石ヒメちゃんー！」

「いい感じ……いやちょっと待って。ここ、おかしなことになってる……」

「どこ～？　あ、崖を登ってる！」

　あちゃあ、やっぱりそうなるかあ。出力された結果は、崖を上り下りする経路だった。これは使えないなあ。

「プログラムを作り直さないと……。移動可能な経路と不可能な経路を区別しないと……」

　試行錯誤の末、よさげな順路を出力させることに成功した。ちょっと疲れたけど、みんなから尊敬のまなざしを向けられたから私は満足です！