最短経路はどう見つけるか：月夜の配達のヒントを手で計算する

「最短」で数えているのは何か

月夜の配達の確認済みの仕様は、小包が3つ、バッグが2枠、燃料は有限で、1区間進むと燃料が1減る、というものです。夜は3つあり、残り最短距離を示すヒント、次の一歩を照らすヒント、一歩戻る操作があります。

ここで重要なのは「1区間で燃料1」という点です。どの区間も同じ重さなので、最短とは「通る区間の数がいちばん少ない道」を意味します。道のりの長さや曲がり角の数は関係ありません。区間ごとに重さが違うと、BFSだけでは足りず、重みを足し合わせる別の方法（ダイクストラ法など）が必要になります。全部が同じ重さだからこそ、BFSが素直に使えます。

整理すると、次の2つが出発点です。

• 数える単位は「区間」で、すべて同じ重さです。
• 最短とは、区間数が最小の道のことです。

「最短」を考えるときは、まず何を1と数えるのかを確かめます。この確認が、次に作る地図の前提になります。

手計算用の小さな架空の地図

練習用に、8つの地点A〜Hを使います。つながりは次の10本の道で、どれも行き来できます。

• A–B、A–C
• B–D、C–D、C–E
• D–F、E–F、E–G
• F–H、G–H

出発点はA、目的地はHです。紙に8つの丸を書いて線を引くと、AからDとEのあたりで道が合流し、FとGを経てHに集まる形になります。

見ただけで最短が分かるでしょうか。AからHまで行く道は複数あって、どれも似た長さに見えます。ここで「たぶんこれ」と目で選ぶのではなく、手順で確実に求めるのが今回の練習です。

幅優先探索を一歩ずつ進める

手順は3つだけです。

1. 出発点に距離0を書き、これを「待ち行列」の先頭に入れます。待ち行列は、順番待ちの列のことです。
2. 列の先頭を取り出し、そこから行ける隣の地点のうち、まだ距離が書かれていない地点に「取り出した地点の距離+1」を書いて、列の後ろに並べます。
3. 列が空になるまで2を繰り返します。

地図で実際に進めてみます。

• 距離0、新しく距離が付く地点：A、由来：出発点です。
• 距離1、新しく距離が付く地点：B、C、由来：Aの隣です。
• 距離2、新しく距離が付く地点：D、E、由来：BからD、CからDとEです。
• 距離3、新しく距離が付く地点：F、G、由来：DからF、EからFとGです。
• 距離4、新しく距離が付く地点：H、由来：FからH、GからHです。

途中の細部も確かめておきます。距離2の層でBからDに進むとき、CからもDに届きますが、Dにはすでに距離が書かれているので、書き直しません。同じ地点を二度扱わないのが、この方法の肝です。

結論として、AからHの最短は4区間です。実際に4区間の道を探すと、A–B–D–F–H、A–C–D–F–H、A–C–E–F–H、A–C–E–G–Hの4本があり、同じ4区間になります。5区間以上かかる道はありますが、より短い道は存在しません。Hに隣り合うのはFとGだけで、どちらも距離3なので、Hは4より小さくなりようがないからです。

この「層ごとに広げる」という性質のおかげで、最初にゴールに届いた時点でそれが最短だと言い切れます。燃料が5あれば届き、3しかなければ、この地図ではどう進んでも届かないことも、手計算の時点で分かります。

ゴールから数えると、ヒントが作れる

ここからが「ヒント」の話です。上の計算は出発点から数えましたが、ゴールから逆向きに数える方法もあります。道は行き来できるので、結果は同じ形になります。ゴールHを距離0として、同じ手順で進めます。

• H：0
• F、G：1
• D、E：2（DはF、EはFとGの隣です）
• B、C：3（BはD、CはDとEの隣です）
• A：4

こうして全地点に「ゴールまでの残り区間数」が付きます。この表があれば、2つのことが簡単に分かります。

• 残り最短距離は、今いる地点の数字を読むだけです。Aにいれば4です。
• 次の一歩は、隣の地点のうち数字が1小さいところを選べば決まります。Aの隣はBとCで、どちらも3なので、どちらに進んでも最短のままです。

月夜の配達の確認済みの仕様に、残り最短距離を示すヒントと、次の一歩を照らすヒントがあります。この2つは、上のような「ゴールまでの残り区間数の表」から自然に導けるものです。ただし、作品が実際にそう実装されているかは、確認済みの情報にはありません。ここでは「設計から読み取れること」として、2つのヒントが同じ種類の情報（残り区間数）から作れる、というところまでにとどめます。

作品で次の点を確かめると、仕組みの予想が当たっているか分かります。

• 寄り道をして一歩戻ったとき、残り最短距離の数字は、戻る前の地点の数字に戻るでしょうか。
• 次の一歩の候補が2つ以上あるとき、照らされるのは1つでしょうか、複数でしょうか。
• 道を外れて燃料が減ったとき、残り最短距離の数字と残り燃料の関係はどう見えるでしょうか。

記録は、ヒントを使う前に自分で数えた区間数と、表示された数字を、夜ごとに紙に並べるのが確実です。各夜の最少区間数の記録は、プレイ中だけ残る仕様で、画面を閉じると消えます。比べるなら、その場でメモを取ってください。

小さなコードで確かめる

手計算の結果は、コードでも再現できます。次のHTMLはそのまま保存してブラウザで開けば動き、結果はコンソールに出ます。

<script>
const edges = "A-B A-C B-D C-D C-E D-F E-F E-G F-H G-H".split(" ");
const g = {};
for (const e of edges) {
  const [a, b] = e.split("-");
  (g[a] ??= []).push(b);
  (g[b] ??= []).push(a);
}
function distancesFrom(goal) {
  const dist = { [goal]: 0 };
  const queue = [goal];
  while (queue.length) {
    const now = queue.shift();
    for (const next of g[now]) {
      if (next in dist) continue;
      dist[next] = dist[now] + 1;
      queue.push(next);
    }
  }
  return dist;
}
const d = distancesFrom("H");
console.log(d);
const here = "A";
console.log(g[here].filter(n => d[n] === d[here] - 1));
</script>

コンソールに出る1つ目は、各地点の残り距離です。手計算の表と同じ値になっているはずです。2つ目は、Aから見て残りが1小さい隣の地点で、先ほどの手計算ならBとCの両方になります。

値が食い違ったときは、辺の書き間違いを疑ってください。edges の文字列を1本ずつ地図と照らすと、たいてい原因が見つかります。

自分の地図に置き換えるには、edges を書き換えるだけです。ゲームの面を作る人は、道の本数が増えても同じコードで残り距離が出せます。

起こりやすい誤りと、状態が増える場合

手計算でつまずきやすい点を挙げます。

• 距離が書かれた地点を、あとから別の経路で書き直してしまいます。書き直さないのが決まりです。
• 層の順番を飛ばします。距離2の地点をすべて処理する前に距離3へ進むと、最短が崩れます。
• 行き来できない道（一方通行）を、両方向に書いてしまいます。道の向きは地図に合わせて決めます。

もう1つ、ゲームならではの落とし穴があります。小包を拾ったり届けたりする規則がある場合、「どこにいるか」だけでは状況を表せないことがあります。たとえばバッグに何が入っているか、どの小包を配達済みかが先の展開を左右するなら、探索の対象は「地点」ではなく「地点とバッグの中身の組」になります。この組を一つの状態として、同じ手順で層を広げていきます。

月夜の配達のバッグは2枠、小包は3つと、持てる数より運ぶ数のほうが多い仕様です。そのため、最短を考えるときに状態を増やす必要があるかもしれません。ただし、小包の受け取りと配達の細かな規則は、確認済みの情報にありません。この部分は作品を開いて、自分で試して確かめてください。

次の行動

まず、この記事の架空の地図で、距離の表を紙に書いて自力で再現してください。次に、月夜の配達を開き、ヒントを使う前に自分で区間数を数えて、表示された残り最短距離と見比べてみてください。ゲームを作る人は、自作の面の道を edges に書き写し、distancesFrom で残り距離の表を出してみると、ヒント機能の土台になります。