第56話: アルゴリズムで挑戦
ドローンが空中に静かに浮かんでいるのを見つめながら、アランはレオンとフィンに提案を持ちかけた。
「ドローンをガイドとして使ったダンジョン攻略を考えてみたらどうだろう？これをきっかけにアルゴリズムについての理解を深めることができるはずだよ。」
レオンが興味深そうに顔を上げた。「アルゴリズムを深めるって…どういう意味？」
アランは微笑んで説明を始めた。「このダンジョン、どうやらモンスターの動きは完全にランダムじゃないらしい。一定のパターンがあって、それを読み取れば攻略の道筋が見えてくる。そこで、ドローンを使ってモンスターの動きを追跡し、最適なルートを見つけ出すためのアルゴリズムを考えようと思うんだ。」
フィンも興味を示し、ドローンに目を向けた。「なるほど。それで、具体的にはどんな方法を考えているんだ？」
「まずは簡単な案を出してみてほしい」とアランが促すと、レオンが最初に手を挙げた。
「僕は、まずダンジョン内の道をできるだけ奥へ奥へと進んでいくのがいいんじゃないかと思うんだ。つまり、目の前に道があるならば、その道が行き止まりになるまで進んで、ダメだったらその時に戻って次の道を探す感じでね。」
アランが少し考えながら頷いた。「なるほど。それは一つのやり方だね。」
「でも、それだと時間がかかりすぎない？」フィンが疑問を投げかけた。「例えば、すぐ近くにゴールがあったのに、ずっと奥に進んでしまったら、無駄な時間がかかっちゃうかもしれない。」
レオンは肩をすくめた。「そうかもしれないけど、奥までしっかり探索しておけば、次の選択肢を一つずつ確認していくのは効率がいいと思うんだ。」
アランは微笑みながらフィンに目を向けた。「じゃあ、フィン。君ならどうする？」
フィンは少し考えてから答えた。「僕なら、まずはダンジョン内のすべての道を一度に確認する。ゴールが近くにあるなら、それをすぐに見つけたいから、手当たり次第に行けるところをすべて確認するのがいいと思うんだ。」
「それも確かに一理ある」とアランが頷いた。「すべての道を広げて確認していけば、近くにゴールがあった場合、すぐに見つかるかもしれないね。でも、その分、多くの情報を一度に処理しなければならないから、時間がかかることもある。」
フィンは笑みを浮かべた。「確かに。でも、それでも無駄に遠くまで進むよりは効率的だと思うんだ。特にゴールが近くにある可能性が高い場合はね。」
レオンは腕を組んで考え込んだ。「でも、その方法だと、どんどん広がっていくから、最終的には無駄に広い範囲を探索しちゃわないか？遠回りする可能性もあるよね。」
アランは2人の案を比較しながら、静かに口を開いた。「レオンの案は、まず奥まで進むことで無駄な探索を減らすことができるけど、近くにゴールがあった場合、かなり遠回りになってしまう可能性があるね。逆にフィンの案は、近場のゴールを早く見つけることができるけれど、多くの道を一度に確認するため、処理する情報量が多くなってしまう。」
レオンは再び口を開いた。「でもさ、奥まで進めば、無駄な道を見つけて戻ってくるまでの時間も無駄になるかもしれない。それに、モンスターがいたら余計に時間を取られるし。」
フィンも反論した。「でも、全体を見渡せば、どこに行けばいいかが早く分かるはずだよ。最短経路が見つかれば、その道だけを進めばいいんだし。」
レオンとフィンは顔を見合わせ、しばらくの間、黙って考え込んだ。
アランは意見を出し合う2人に声をかける。「まずは試してみて、実際のダンジョンでどう動くかを確認してみようか。」
物語の雰囲気に合わせて用語を出さなかったのでこちらで補足しておきます。
深さ優先探索（DFS）と幅優先探索（BFS）は、迷宮のような複雑な構造を探索するための基本的なアルゴリズムです。それぞれに特徴があり、状況に応じて使い分けられます。
1. 深さ優先探索（DFS）：
仕組み: 深さ優先探索は、まずある地点から可能な限り深く（遠く）進み、その道が行き止まりになったら一歩戻って別の道を探索する方法です。つまり、どんどん奥へ進んでいって、行き止まりになったら戻って別の道を試します。スタック（後入れ先出し）を使って実装されることが多いです。
迷宮探索に応用すると: 例えば、迷宮内で進める道があればひたすら進み続け、壁にぶつかって初めて戻るような動きになります。道が1本でも続いている限り奥へ進んでいくので、一本道の迷宮には適しているといえます。
長所: 記憶する分岐点が少なくて済むので、メモリ使用量が少なくて済む場合があります。
短所: 深く進みすぎると、無駄な探索が増えることがあり、特にゴールが近くにあった場合には非効率です。
2. 幅優先探索（BFS）：
仕組み: 幅優先探索は、ある地点から進めるすべての道を均等に広げていきます。つまり、まず出発点の周囲をすべて探索し、次にその先を探索するというように、段階的に探索を広げていきます。キュー（先入れ先出し）を使って実装されます。
迷宮探索に応用すると: 例えば、迷宮の入り口から最初の選択肢をすべて一度確認し、その後、次に進める道を確認していくので、最短距離でゴールにたどり着ける可能性が高いです。DFSに比べて、無駄な遠回りをすることなく、最も近い道を効率的に見つけられる可能性があります。
長所: 最短経路を見つけることができるため、ゴールが近い場合や効率よく進みたい場合に有効です。
短所: 探索範囲が広がるたびに多くの情報を記憶し続ける必要があるため、メモリを多く使用する場合があります。
