Bagaimana Anda mengimplementasikan A* pada weighted grid?

1. Masalah

Implementasikan aStar(grid, start, goal). Setiap sel dapat berupa rintangan (terblokir) atau memiliki biaya lintasan positif. Pergerakan hanya ke empat arah; memasuki sel tetangga akan menambahkan biaya sel tersebut. Kembalikan jalur beserta total biayanya, atau NO_PATH jika tujuan tidak dapat dijangkau.

2. Batasan dan klarifikasi

• Koordinat merupakan pasangan integer (row, column) di dalam grid; titik awal dan tujuan harus dapat dilalui.
• Heuristik tidak boleh pernah melebih-lebihkan (overestimate) sisa biaya jika hasilnya harus optimal. Dengan pergerakan empat arah dan biaya sel minimum sebesar m, jarak Manhattan dikalikan m bersifat admissible.
• Gunakan min-heap yang diurutkan berdasarkan f, lalu gunakan koordinat deterministik sebagai tie-breaker. Heap dapat memuat entri usang setelah ditemukan skor g yang lebih baik.
• Biaya sel negatif tidak valid. Implementasi single-threaded sudah mencukupi; pembaruan grid yang konkuren memerlukan snapshot atau pemeriksaan versi.

3. Pendekatan utama

Simpan gScore untuk biaya terendah yang diketahui ke setiap sel dan cameFrom untuk rekonstruksi jalur. Lakukan push (f, g, cell) setiap kali relaksasi memperbarui gScore menjadi lebih baik. Saat melakukan pop, lewati node jika nilai g yang tersimpan lebih besar daripada gScore saat ini; pendekatan malas (lazy) ini menghindari operasi decrease-key yang rumit pada heap.

Untuk heuristik yang konsisten (consistent), pop non-usang pertama dari tujuan sudah pasti optimal. Jika heuristik hanya bersifat admissible, izinkan node tertutup (closed) untuk dibuka kembali saat ditemukan g yang lebih murah. Red Blob Games menjelaskan pola priority queue ini dan bagaimana kualitas heuristik memengaruhi beban kerja komputasi.

4. Implementasi referensi

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 menelusuri cameFrom dari tujuan ke titik awal lalu membalikkan urutan sel yang dikumpulkan. Priority queue hanya bertugas menjadwalkan kandidat; gScore tetap menjadi sumber kebenaran (source of truth).

5. Kompleksitas dan kompromi

Dengan V sel yang dapat dijangkau dan E edge tetangga, binary heap menghasilkan waktu O((V + E) log V) dan memori O(V) pada implementasi lazy-entry. Pada grid empat tetangga, E adalah O(V). Heuristik konsisten yang lebih kuat biasanya mengurangi jumlah sel yang diekspansi tanpa mengubah batas kasus terburuk. Heap dengan operasi decrease-key yang tepat dapat mengurangi duplikasi entri, tetapi menambah kompleksitas implementasi.

6. Verifikasi dan observabilitas

• Uji skenario titik awal sama dengan tujuan, titik akhir terblokir, grid kosong, dinding dengan celah, rute memutar berbobot (weighted detours), dan tujuan yang tidak dapat dijangkau.
• Bandingkan biaya yang dihasilkan dengan Dijkstra menggunakan h=0 pada grid non-negatif acak.
• Pastikan (assert) setiap langkah yang dihasilkan bersebelahan dan dapat dilalui, serta hitung ulang biaya jalur secara independen.
• Lacak sel yang diekspansi, pop usang, ukuran heap maksimum, dan pelanggaran heuristik; lonjakan pada pop usang dapat mengindikasikan penjadwalan ganda atau batas struktur data yang buruk.

7. Kesalahan umum

• Menandai node sebagai tertutup permanen saat pertama kali ditemukan, alih-alih saat pop yang valid.
• Menggunakan jarak Euclidean untuk pergerakan unit empat arah tanpa penskalaan atau tanpa memeriksa admissibility.
• Menambahkan biaya sel saat ini, bukan biaya untuk memasuki sel tetangga.
• Mengembalikan jalur ketika tujuan diambil dari rekaman heap yang usang.
• Lupa menangani start == goal atau mengizinkan titik akhir yang terblokir.

8. Pertanyaan lanjutan

Kapan jarak Manhattan bersifat admissible?

Untuk pergerakan empat arah dengan biaya non-negatif dan biaya lintasan minimum m, setiap langkah horizontal atau vertikal yang diperlukan membutuhkan biaya setidaknya m; jarak Manhattan dikalikan m tidak mungkin melebihi sisa biaya sebenarnya.

Bagaimana pergerakan diagonal mengubah heuristik?

Gunakan batas bawah gaya octile atau Chebyshev yang sesuai dengan biaya pergerakan diagonal dan lurus. Rumus tersebut harus mencerminkan kombinasi legal termurah dan tetap menjadi batas bawah (lower bound).

Bagaimana jika grid berubah selama pencarian?

Lakukan pencarian pada snapshot berversi dan validasi jalur sebelum digunakan, atau mulai ulang pencarian saat versi grid berubah. Mencampur biaya dari versi yang berbeda dapat merusak keoptimalan maupun keamanan jalur.