Bagaimanakah anda akan melaksanakan A* pada grid berwajaran?

1. Masalah

Laksanakan aStar(grid, start, goal). Sesuatu sel disekat atau mempunyai kos laluan positif. Pergerakan adalah dalam empat arah; memasuki sel jiran menambah kos jiran tersebut. Kembalikan laluan dan jumlah kos, atau NO_PATH apabila matlamat tidak boleh dicapai.

2. Kekangan dan penjelasan

• Koordinat ialah pasangan integer (row, column) di dalam grid; titik mula dan matlamat mestilah boleh dilalui.
• Heuristik tidak boleh sesekali terlebih anggap (overestimate) kos yang tinggal jika keputusan mestilah optimum. Dengan pergerakan empat arah dan kos sel minimum m, jarak Manhattan didarab dengan m adalah admissible.
• Gunakan min-heap yang disusun mengikut f, diikuti penentu seri koordinat yang deterministik. Heap mungkin mengandungi entri lapuk selepas skor g yang lebih baik ditemui.
• Kos sel negatif adalah tidak sah. Pelaksanaan satu benang (single-threaded) adalah mencukupi; kemas kini grid serentak memerlukan snapshot atau pemeriksaan versi.

3. Pendekatan teras

Kekalkan gScore untuk kos termurah yang diketahui bagi setiap sel dan cameFrom untuk pembinaan semula laluan. Tolak (f, g, cell) setiap kali pengenduran (relaxation) menambah baik gScore. Semasa operasi pop, langkau nod jika g yang disimpan lebih besar daripada gScore semasa; pendekatan malas (lazy) ini mengelakkan operasi decrease-key heap yang sembarangan.

Bagi heuristik yang konsisten, pop bukan lapuk pertama bagi matlamat adalah optimum. Jika heuristik hanya admissible, benarkan nod yang telah ditutup dibuka semula apabila g yang lebih murah ditemui. Red Blob Games menerangkan corak baris gilir keutamaan ini dan kesan kualiti heuristik terhadap kerja yang dilakukan.

4. Pelaksanaan rujukan

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 menjejaki cameFrom dari matlamat ke mula dan menyongsangkan sel yang dikumpul. Baris gilir keutamaan hanya menjadualkan calon; gScore kekal sebagai punca kebenaran (source of truth).

5. Kerumitan dan kompromi

Dengan V sel yang boleh dicapai dan E tepi jiran, binary heap memberikan masa O((V + E) log V) dan ruang O(V) dalam pelaksanaan lazy-entry. Pada grid empat jiran, E ialah O(V). Heuristik konsisten yang lebih kuat biasanya mengurangkan sel yang dikembangkan tanpa mengubah batas kes terburuk. Heap dengan operasi decrease-key yang tepat boleh mengurangkan entri pendua tetapi menambah kerumitan pelaksanaan.

6. Pengesahan dan kebolehcerapan

• Uji titik mula bersamaan matlamat, titik akhir yang disekat, grid kosong, dinding dengan celah, lencongan berwajaran, dan matlamat yang tidak boleh dicapai.
• Bandingkan kos yang dikembalikan dengan Dijkstra menggunakan h=0 pada grid bukan negatif rawak.
• Sahkan (assert) setiap langkah yang dikembalikan adalah bersebelahan dan boleh dilalui, serta hitung semula kos laluan secara berasingan.
• Jejaki sel yang dikembangkan, pop lapuk, saiz heap maksimum, dan pelanggaran heuristik; lonjakan pop lapuk mungkin menunjukkan penjadualan pendua atau sempadan struktur data yang lemah.

7. Kesilapan lazim

• Menandakan nod sebagai ditutup secara kekal semasa penemuan pertama dan bukannya semasa operasi pop yang sah.
• Menggunakan jarak Euclidean untuk pergerakan unit empat arah tanpa penskalaan atau pemeriksaan kebolehterimaan (admissibility).
• Menambah kos sel semasa dan bukannya kos memasuki sel jiran.
• Mengembalikan laluan apabila matlamat diambil daripada rekod heap yang lapuk.
• Terlupa untuk mengendalikan start == goal atau membenarkan titik akhir yang disekat.

8. Soalan susulan

Bilakah jarak Manhattan dianggap admissible?

Bagi pergerakan empat arah dengan kos bukan negatif dan kos laluan minimum m, setiap langkah mendatar atau menegak yang diperlukan menelan kos sekurang-kurangnya m; jarak Manhattan didarab dengan m tidak boleh melebihi kos baki sebenar.

Bagaimanakah pergerakan pepenjuru mengubah heuristik?

Gunakan batas bawah gaya octile atau Chebyshev yang sepadan dengan kos pergerakan pepenjuru dan lurus. Formula mestilah mencerminkan gabungan sah yang paling murah dan kekal sebagai batas bawah.

Bagaimana jika grid berubah semasa carian?

Lakukan carian pada snapshot berversi dan sahkan laluan sebelum digunakan, atau mulakan semula apabila versi grid berubah. Mencampurkan kos daripada versi berbeza boleh membatalkan keoptimuman dan keselamatan.