燃料という制約つきの経路探索：単純な最短距離との違い

月夜の配達の仕様から読み取れること

確認済みの仕様は次のとおりです。

• 小包は3つ、バッグは2枠です。
• 燃料は有限で、1区間進むと燃料を1使います。
• 3つの夜の経路パズルです。
• 「残り最短距離」の表示、次の一歩を照らすヒント、一歩戻る操作があります。
• 各夜の最少区間数は、プレイ中だけ記録されます。

ここから、設計について次のことが読み取れます。

1. 燃料と距離は同じ単位です。 1区間で燃料1なので、使った燃料は進んだ区間の数と一致します。最少区間数の記録は、燃料をどれだけ節約できたかの記録とも読めます。
2. 小包3つに対してバッグが2枠です。 3つとも扱うなら、すべてを同時には持てません。どの順に拾い、どこで降ろすかという順序の選択が、パズルの中心にあると考えられます。
3. 「残り最短距離」とヒントは別の助けです。 前者は数字で距離感を示し、後者は次の一歩を示します。この数字が何を基準に数えられているかは、この記事では断定しません。作品を開いて確かめます。

なお、燃料を補給できる場所があるか、一歩戻ると燃料が戻るか、小包の受け渡し場所がどう決まるかは、確認済み事項にありません。作品を開いて確かめる項目です。

小さな地図で比べる

ここからは、ゲームの地図ではなく、説明用に作った小さな例を使います。5か所を線でつないだ地図です。

S ─ A ─ G
│       │
P ─ ─ ─ D

Sが出発点、Gが目的地です。Pで小包を拾い、Dで届けます。線は、SとA、AとG、SとP、PとD、DとGの5本です。

荷物を考えなければ、S→A→Gの2区間が最短です。しかし小包を拾って届ける条件を足すと、S→P→D→Gの3区間が必要です。つまり次のようになります。

• 燃料が2しかなければ、荷物ありの条件は達成できません。
• 燃料が3あれば、ちょうど達成できます。
• 燃料が4あっても、必要な区間は3のままです。余りは遠回りに使えますが、遠回りしても得点が増えるとは限りません。

地図上のGまでの距離は2のままなのに、荷物の条件が入ると必要な燃料は3になります。「距離」と「その条件を満たす最短の手順」は別の量だということが、この例から分かります。

探索が数えているもの：位置だけでなく状況

単純な最短距離では、探索は「今どこにいるか」だけを覚えます。荷物を含めると、「どこにいて、荷物がどうなっているか」の組を覚える必要があります。この組を「状態」と呼びます。

先ほどの例を、一歩ずつ広げて見ます。荷物の状態は、未(まだ拾っていない)、持(持っている)、済(届けた)の3つです。

• 0、到達できる状態：S・未
• 1、到達できる状態：A・未、P・持
• 2、到達できる状態：G・未、S・持、D・済
• 3、到達できる状態：D・未、A・持、P・済、G・済

2歩目にはG・未が現れます。位置だけの探索ならここで終わりですが、荷物が済になっていないので、条件つきの探索は続けます。目的地に着き、かつ荷物が済になる状態G・済は、3歩目で初めて現れます。

ここで大事なのは、燃料が特別な計算を要しない点です。1区間ごとに燃料1を使うなら、歩数がそのまま使った燃料です。燃料が3なら、3歩目までで探索を打ち切れば足ります。この場合、燃料の制約は「探索の深さの上限」に当たります。

難しくなる本当の原因は、荷物の状態が増えることです。月夜の配達のように小包が3つでバッグが2枠なら、各小包が未・持・済のどれかで、全部で3×3×3=27通りです。このうち3つとも「持」の1通りだけはバッグに入らないので、成り立つのは26通りです。地図が仮に20か所なら、数える状態は最大で20×26=520通りになります。位置だけなら20通りです。条件が増えると、探索が見るべき範囲は掛け算で増えます。

この見方は、燃料の使い方が一定の場合のものです。燃料を補給できる、区間によって消費が違うといった仕組みがあれば、燃料の残量も状態に加える必要があります。月夜の配達にそれがあるかは、作品を開いて確かめます。

手元で確かめる①：小さなコード

上の例を、そのまま探索するコードです。HTMLファイルに貼ってブラウザで開き、開発者ツールのコンソールを見ます。

<script>
// 説明用の地図です（ゲームの地図ではありません）
const edges = [["S","A"],["A","G"],["S","P"],["P","D"],["D","G"]];
const adj = {};
for (const [a, b] of edges) {
  (adj[a] ??= []).push(b);
  (adj[b] ??= []).push(a);
}
// p: 荷物の状態 0=未, 1=持, 2=済
function solve(fuel, needParcel) {
  const start = { at: "S", p: needParcel ? 0 : 2, steps: 0 };
  const seen = new Set(["S|" + start.p]);
  const queue = [start];
  while (queue.length) {
    const cur = queue.shift();
    if (cur.at === "G" && cur.p === 2) return cur.steps;
    if (cur.steps >= fuel) continue; // 燃料切れ＝深さの上限
    for (const next of adj[cur.at]) {
      let p = cur.p;
      if (next === "P" && p === 0) p = 1;
      if (next === "D" && p === 1) p = 2;
      const key = next + "|" + p;
      if (seen.has(key)) continue;
      seen.add(key);
      queue.push({ at: next, p, steps: cur.steps + 1 });
    }
  }
  return null; // 燃料内では達成できない
}
for (const f of [2, 3, 4]) {
  console.log("燃料", f, "荷物なし", solve(f, false), "荷物あり", solve(f, true));
}
</script>

実行前に、前章の例を手で追って予想を立てると、読み取りが深まります。追った結果では、荷物なしはどの燃料でも2、荷物ありは燃料2でnull、燃料3と4では3になるはずです。出力が予想と違えば、地図か荷物の取り扱いの書き方を見直してください。

次の改造も、判断の練習になります。

• edges にSとDを直接つなぐ線を加え、荷物ありの最短がどう変わるか見ます。
• Pの位置を変えて、荷物ありの必要燃料が増える配置を探します。
• 荷物を2つにし、状態を「持った数」で数え直します。

手元で確かめる②：作品で記録をとる

次に、月夜の配達を開いて、「残り最短距離」の数字が何を表しているかを自分で確かめます。作品側の記録は、プレイ中だけ残る仕組みです。確かめた結果は自分でメモに残してください。

準備するもの

3つの夜それぞれについて、次の列を持つ記録表を用意します。

歩数 ／ 燃料の残り ／ 残り最短距離 ／ 操作(移動・取る・降ろす) ／ 燃料−残り最短距離

最後の列は「余裕」です。燃料の残りから残り最短距離を引いた値で、マイナスなら、その状態ではクリアできないことを意味するはずです。

手順

1. 各夜で、最初に何も操作せず、燃料と残り最短距離を記録します。
2. 1歩ずつ進み、そのつど3つの数字を記録します。小包を拾う・降ろす操作の前後は、特に丁寧に記録します。
3. 1回だけ、ヒントとは別の方向に進みます。その直後の数字を記録し、一歩戻る操作の後も記録します。
4. 同じ夜を最低2回遊び、歩数の少ない方を最少区間数として自分のメモに残します。夜ごとに別の紙か列に分けて、混ぜないようにします。

結果の読み方

• 余裕が変わらない歩ばかりなら、ヒントに従った歩は、残り最短距離を1つ縮める歩と読めます。
• 余裕が減る歩があれば、その歩は遠回りです。ヒントと別方向に進んだ歩で減るなら、残り最短距離は進路の評価に使えます。
• 荷物を拾った前後で数字が大きく動くなら、残り最短距離は荷物の条件を含んで計算されている可能性が高いです。まったく変わらないなら、地図上の距離だけを見ている可能性があります。ただし、拾った場所が目的地の方向にあっただけの場合もあるので、複数の場面で確かめます。
• 一歩戻る操作で燃料が戻るかは、戻る前後の燃料を比べればすぐ分かります。戻らないなら、戻る操作は探索の枝を試し直す手段であって、燃料を無料にするものではないと分かります。

起こりやすい誤り

• 一歩戻る操作を歩数に数えたり、数え忘れたりして、最少区間数がずれます。
• 夜を切り替えたのに、前の夜の表を続けてしまいます。
• 残り最短距離を、地図の直線距離のような別の量と取り違えます。
• 1回の記録だけで結論を出します。同じ場面を複数回確かめてください。

次の行動

まず上のコードを動かして、荷物の有無と燃料の値で答えがどう変わるかを確かめてください。次に月夜の配達を開き、1つの夜で記録表をつけて、余裕の列が減る歩を探してみましょう。自作ゲームに燃料や所持数の制約を入れるなら、燃料を「探索の深さ」で扱えるか、状態に加える必要があるかを、最初に決めておくと設計が安定します。