重み付きグリッド上で A* をどのように実装しますか？

1. 問題

aStar(grid, start, goal) を実装してください。各セルは通行不可能（ブロック）であるか、正の移動コストを持ちます。移動は4方向であり、隣接セルへ進入する際にそのセルのコストが加算されます。経路と総コストを返してください。ゴールに到達不能な場合は NO_PATH を返します。

2. 制約事項と明確化

• 座標はグリッド内部の整数ペア (row, column) です。スタートとゴールは通行可能である必要があります。
• 最適な結果を得るためには、ヒューリスティックが残りのコストを過大評価してはなりません。4方向移動かつセルの最小コストが m の場合、マンハッタン距離に m を乗じた値は許容的（admissible）です。
• f で順序付けされ、座標による決定論的なタイブレークを備えた最小ヒープを使用してください。より良い g スコアが見つかった後、ヒープには古いエントリ（stale entries）が含まれる場合があります。
• 負のセルコストは無効です。シングルスレッドの実装で十分ですが、並行してグリッドが更新される場合はスナップショットまたはバージョンチェックが必要です。

3. コアアプローチ

各セルへの既知の最小コストを記録する gScore と、経路復元用の cameFrom を保持します。緩和（relaxation）によって gScore が改善されるたびに (f, g, cell) を push します。pop 時には、保持されている g が現在の gScore よりも大きい場合、そのノードをスキップします。この遅延（lazy）アプローチにより、ヒープ上の任意の decrease-key 操作を回避できます。

無矛盾（consistent）なヒューリスティックの場合、ゴールが初めて有効に（古いエントリでなく）pop された時点で最適性が保証されます。ヒューリスティックが許容的であるのみの場合は、より安価な g が見つかった際、確定済み（closed）ノードの再オープンを許可します。Red Blob Games では、この優先度付きキューのパターンと、ヒューリスティックの品質が探索作業量に与える影響について解説されています。

4. 参照実装

aStar(grid, start, goal):
  require traversable(start) and traversable(goal)
  gScore = map(default=INFINITY)
  cameFrom = map()
  gScore[start] = 0
  open = minHeap((heuristic(start, goal), 0, start))

  while open is not empty:
    (f, queuedG, current) = open.pop()
    if queuedG != gScore[current]: continue   // stale entry
    if current == goal:
      return reconstruct(cameFrom, goal), gScore[goal]

    for next in traversableNeighbors(current):
      tentative = gScore[current] + grid[next].cost
      if tentative < gScore[next]:
        gScore[next] = tentative
        cameFrom[next] = current
        open.push((tentative + h(next, goal), tentative, next))

  return NO_PATH

reconstruct はゴールからスタートへ cameFrom を辿り、収集したセルを反転します。優先度付きキューは候補のスケジューリングのみを行い、gScore が信頼できる唯一の情報源（source of truth）として機能します。

5. 計算量とトレードオフ

到達可能なセル数を V、隣接エッジ数を E とすると、遅延エントリ方式の実装において二分ヒープは O((V + E) log V) の時間と O(V) の空間を要します。4近傍グリッドでは、E は O(V) です。より強力な無矛盾ヒューリスティックを使用すると、最悪ケースの計算量の上限を変えずに、展開されるセル数を削減できます。厳密な decrease-key を備えたヒープは重複エントリを減らせますが、実装の複雑さが増します。

6. 検証とオブザーバビリティ

• スタートとゴールが同一、端点がブロックされている、空のグリッド、隙間のある壁、重み付きの回り道、到達不能なゴールなどのケースをテストします。
• ランダムに生成された非負グリッド上で、h=0 を用いたダイクストラ法と返されたコストを比較します。
• 返された各ステップが隣接しており通行可能であることをアサートし、経路コストを個別に再計算して検証します。
• 展開されたセル数、古いエントリの pop 数、最大ヒープサイズ、ヒューリスティックの違反を追跡します。古いエントリの pop の急増は、重複スケジューリングやデータ構造の境界設定の不備を示している可能性があります。

7. よくある間違い

• 有効な pop 時ではなく、最初に発見された時点でノードを確定済み（closed）としてマークしてしまう。
• 4方向の単位移動に対して、スケーリングや許容性の確認を行わずにユークリッド距離を使用してしまう。
• 隣接セルに進入するコストではなく、現在のセルのコストを加算してしまう。
• ヒープ内の古いレコードからゴールが pop された際に経路を返してしまう。
• start == goal の処理を忘れる、またはブロックされた端点を許可してしまう。

8. 発展的な質問

マンハッタン距離が許容的となるのはどのような場合ですか？

非負コストで最小移動コストが m の4方向移動において、必要な水平または垂直の各ステップには少なくとも m のコストがかかります。したがって、マンハッタン距離に m を掛けた値が実際の残りコストを超えることはありません。

斜め移動によってヒューリスティックはどのように変化しますか？

斜め移動と直線移動のコストに対応する、オクタタイル（octile）またはチェビシェフ（Chebyshev）形式の下限値を使用します。計算式は、最も安価な有効な組み合わせを反映し、かつ下限値を維持する必要があります。

探索中にグリッドが変化した場合はどうすればよいですか？

バージョン管理されたスナップショットを探索して使用前に経路を検証するか、グリッドのバージョンが変更されたときに探索を再開します。異なるバージョンのコストを混在させると、最適性と安全性の両方が損なわれる可能性があります。