月夜の配達のヒントは最短経路をどう計算しているか

確認できていることと、まだ確かめることがあること

作品について確認済みなのは、次の点です。

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

一方、地図の形、受け取り地点と届け先の位置、燃料を補給できる場所があるか、道が一方通行かといった点は、確認済みの情報にありません。これらは作品を開いて確かめる部分です。

ここで「区間」という単位に注目します。燃料の消費も、最少の記録も、区間で数えています。ヒントの「残り最短距離」も同じ単位であれば、燃料の残りと直接比べられます。単位が揃っているかどうかは、作品の画面で確かめてください。

図で追う:直線の道の見本

状態探索の考え方を見るために、実際の地図とは無関係の見本を作ります。地図は直線の道で、0番から5番まで6つの地点が並びます。

0 —— 1 —— 2 —— 3 —— 4 —— 5
出発  P1   P2   P3        届け先(全員5番)

小包P1・P2・P3は、それぞれ1番・2番・3番で受け取り、すべて5番に届けます。バッグは2枠で、燃料は10です。地点に着くと、バッグに空きがあれば自動で受け取る決まりにします。

バッグが無制限なら、0番から5番へまっすぐ進むだけで5区間です。2枠だと3つ目のP3を最初の通過で拾えません。次の流れが最短で、合計9区間です。

1. 1番でP1、2番でP2を受け取ります。
2. 3番ではバッグが満杯なので、P3を拾えずに通過します。
3. 5番に着いてP1とP2を届けます。
4. 3番まで戻ってP3を受け取り、5番へ向かいます。

「別の順番なら短くなるのでは」と考えて確かめます。P2を飛ばしてP1とP3を持って進む案は、P2を取りに戻る分だけ長くなり、11区間でした。今回の見本では、9区間が最短です。

この最短ルートを、燃料10のまま辿ると次のようになります。

• 0、位置：0番、起きること：出発、燃料：10、残り最短：9、余裕(燃料−残り)：1
• 2、位置：2番、起きること：P1・P2を所持、燃料：8、残り最短：7、余裕(燃料−残り)：1
• 3、位置：3番、起きること：満杯でP3を拾えない、燃料：7、残り最短：6、余裕(燃料−残り)：1
• 5、位置：5番、起きること：P1・P2を配達、燃料：5、残り最短：4、余裕(燃料−残り)：1
• 7、位置：3番、起きること：P3を受け取る、燃料：3、残り最短：2、余裕(燃料−残り)：1
• 9、位置：5番、起きること：P3を配達、完了、燃料：1、残り最短：0、余裕(燃料−残り)：1

見てほしいのは2つあります。1つ目は、最短ルートに従う限り、残り最短が1手ごとに1ずつ減ることです。2つ目は、余裕（燃料から残り最短を引いた値）が終始1のままで変わらないことです。この見本では、燃料が最短より1だけ多いことになります。

「位置」だけでは残り距離が決まらない

表の3手目と7手目は、どちらも3番にいます。ところが残り最短は6と2で、大きく違います。

3手目は2つの小包を抱えたままで、まだ誰も届けていません。7手目はP1とP2を届け終え、P3を受け取った直後です。同じ地点でも、何を持っていて、何を届け終えたかが違えば、残りの道のりは変わります。

つまり「残り最短距離」を出すには、位置だけでなく、次の3つをまとめた状態を単位にする必要があります。

• いまの位置
• 各小包が「まだ受け取っていない」「持っている」「届け済み」のどれか
• 持っている数が2以下かどうか

見本の小包は3つです。1つにつき3通りなので、3の3乗で27通りです。このうち「3つとも持っている」状態だけはバッグの2枠を超えるので除き、26通りが残ります。これに地点の数を掛けた数が状態の総数です。地点が数十個あっても数千程度に収まるため、一歩ごとに最初から数え直しても、現代の端末にはごく軽い計算です。

これは一般的な計算量の見積もりであり、「月夜の配達」の実装がこの方式だという意味ではありません。ただ、「持ち物を含めて数えれば足りる」ことを示しています。

燃料は状態ではなく「深さの上限」になる

ここで題名の核心です。燃料という制約を入れると、探索は複雑になるのでしょうか。

燃料が1区間ごとに1減るだけで、補給がない場合を考えます。このとき燃料の残りは「最初の燃料から、進んだ区間数を引いた値」で決まります。状態に燃料を加える必要はなく、探索の深さの上限として扱えば足ります。

• 最短の手数を求めます。幅優先探索（近い状態から順に、1区間ずつ広げて調べる方法）が使えます。
• 求めた手数が燃料の残り以下なら、そのルートは通れます。超えていれば、もう届けきれない状態です。

このとき「燃料を最も節約するルート」と「区間数が最短のルート」は同じものです。燃料は進んだ区間数に比例して減るだけなので、別々に最適化する必要はありません。

先ほどの余裕は、回り道の許容量も表します。見本で余裕が1なら、2区間ぶんの往復（1番へ行って戻る寄り道など）はできません。たとえば0→1→0→1→2→3と進むと、3番に着くのに5区間かかります。位置も持ち物も3手目の状態と同じなので、残り最短は6のままです。ところが燃料は5しかなく、6に足りません。位置と持ち物が同じでも、通ってきた手数が多いと、残りの燃料が足りなくなるのです。

なお、補給地点があるなら話は変わります。燃料が増える遷移が入るため、状態に燃料を含めるか、別の扱いが必要です。補給の有無は、作品を開いて確かめてください。

60行以内の試作で確かめる

見本と同じ規則を、外部ライブラリなしの1ファイルで書きます。HTMLファイルに貼ってブラウザで開くと、画面に4つの値が出ます。

<script>
const parcels = [[1, 5], [2, 5], [3, 5]]; // [受取地点, 届け先]
const CAP = 2, START = 0, LAST = 5;
const ALL = (1 << parcels.length) - 1;
const count = (m) => m.toString(2).replace(/0/g, "").length;

function move(s, np) {
  let { got, done } = s;
  parcels.forEach(([, to], i) => {
    const b = 1 << i;
    if (got & b && !(done & b) && np === to) done |= b;
  });
  parcels.forEach(([from], i) => {
    const b = 1 << i;
    if (!(got & b) && np === from && count(got & ~done) < CAP) got |= b;
  });
  return { pos: np, got, done };
}
function shortest(start, fuel) {
  const id = (s) => [s.pos, s.got, s.done].join();
  const seen = new Set([id(start)]);
  let frontier = [start];
  for (let used = 0; used <= fuel; used++) {
    if (frontier.some((s) => s.done === ALL)) return used;
    const next = [];
    for (const s of frontier) {
      for (const np of [s.pos - 1, s.pos + 1]) {
        if (np < START || np > LAST) continue;
        const t = move(s, np);
        if (!seen.has(id(t))) { seen.add(id(t)); next.push(t); }
      }
    }
    frontier = next;
  }
  return null; // 燃料内では届けきれない
}
const start = { pos: 0, got: 0, done: 0 };
const a = { pos: 3, got: 0b011, done: 0 };
document.body.textContent = [
  shortest(start, 10), shortest(start, 8),
  shortest(a, 7), shortest(a, 5),
].map(String).join(" / ");
</script>

先ほどの手計算では、「9 / null / 6 / null」と出るはずです。順に読むと、次のとおりです。

• 最初から燃料10なら9区間です。
• 燃料8なら届けきれません。
• 3番で2つ持っている状態からは、燃料7なら6区間です。
• 同じ状態でも燃料5では届けきれません。

実際に動かして、手計算と一致するか確かめてください。一致しなければ、手計算か規則の読み違いが見つかったことになります。

CAP = 2 を 3 に変えると、最初からの最短は5に縮むはずです。バッグの枠が最短距離を押し上げていることを、数字で確かめられます。

作品を開いて確かめる観察手順

ここからは、実際の「月夜の配達」で読者が確かめる手順です。結果をこの記事に書くことはしません。ご自身の画面で、次の項目を記録してください。

1. 開始時の数字を控えます。 夜を開いた直後の燃料と、ヒントの残り最短距離を書き留めます。差（余裕）が何になるかを見ます。
2. ヒントどおりに1歩進みます。 残り最短が1減るかを見ます。数夜で同じなら、「従えば1ずつ減る」という性質が成り立ちます。
3. ヒントと違う方向へ1歩進みます。 残り最短がどう変わるかを見ます。増える場合も変わらない場合もあり得るので、複数の場面で記録します。
4. 受け取りの前後で数字を見比べます。 同じ地点でも持ち物が変われば、残り最短が変わるかを確かめます。
5. 「一歩戻る」の前後で、燃料と残り最短を見ます。 燃料が戻るかどうかは、確認済みの情報にありません。

読み取るときの注意があります。記録の回数が少ないうちは、アルゴリズムを断定しないでください。観察できるのは、画面に出る数字の振る舞いまでです。振る舞いが先ほどの見本と同じ形であれば、「状態を含めた最短」を出していると読めます。ずれがあれば、補給や一方通行などの規則が別にあるのかもしれません。その場合は、規則を作品の中で確かめてください。

次の行動

まず、試作のコードをHTMLに貼って動かし、4つの値が手計算と合うか確かめてください。次に、「月夜の配達」で1つの夜を選び、開始時の燃料と残り最短距離を記録してみてください。ヒントどおりに進めたときと、あえて外したときで、余裕がどう動くかを見ると、燃料を含めた最短経路の考え方が見えてきます。