आप एक वेटेड ग्रिड पर A* को कैसे लागू करेंगे?

1. समस्या

aStar(grid, start, goal) को लागू करें। एक सेल या तो ब्लॉक है या उसकी एक सकारात्मक ट्रैवर्सल लागत (traversal cost) है। मूवमेंट चार दिशाओं में होती है; किसी पड़ोसी सेल में प्रवेश करने पर उस पड़ोसी सेल की लागत जुड़ जाती है। पाथ और कुल लागत लौटाएं, या लक्ष्य अगम्य होने पर NO_PATH लौटाएं।

2. बाधाएं और स्पष्टीकरण

• निर्देशांक ग्रिड के अंदर पूर्णांक (row, column) जोड़े हैं; स्टार्ट और गोल दोनों का ट्रैवर्सिबल होना अनिवार्य है।
• यदि परिणाम इष्टतम (optimal) होना चाहिए, तो ह्यूरिस्टिक को शेष लागत का कभी भी अधिक अनुमान (overestimate) नहीं लगाना चाहिए। चार-तरफा मूवमेंट और न्यूनतम सेल लागत m के साथ, मैनहट्टन दूरी गुणा m एडमिसिबल है।
• f द्वारा क्रमबद्ध एक min-heap का उपयोग करें, जिसके बाद निर्देशांक-आधारित डिटर्मिनिस्टिक टाई-ब्रेकर हो। बेहतर g स्कोर मिलने के बाद हीप में पुरानी (stale) एंट्रीज़ हो सकती हैं।
• नकारात्मक सेल लागतें अमान्य हैं। सिंगल-थ्रेडेड कार्यान्वयन पर्याप्त है; समवर्ती (concurrent) ग्रिड अपडेट के लिए स्नैपशॉट या वर्ज़न चेक की आवश्यकता होती है।

3. मुख्य दृष्टिकोण

प्रत्येक सेल तक सबसे सस्ती ज्ञात लागत के लिए gScore और रीकंस्ट्रक्शन के लिए cameFrom बनाए रखें। जब भी कोई रिलेक्सेशन gScore में सुधार करता है, तो (f, g, cell) को पुश करें। पॉप करते समय, यदि नोड का संग्रहीत g वर्तमान gScore से अधिक है, तो उसे छोड़ दें (skip करें); यह लेज़ी (lazy) दृष्टिकोण हीप में आर्बिट्रेरी डिक्रीज़-की (decrease-key) ऑपरेशन से बचाता है।

एक सुसंगत (consistent) ह्यूरिस्टिक के लिए, गोल का पहला नॉन-स्टेल पॉप इष्टतम होता है। यदि ह्यूरिस्टिक केवल एडमिसिबल है, तो सस्ता g मिलने पर एक क्लोज़्ड नोड को फिर से खोलने की अनुमति दें। 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 का अनुसरण करता है और एकत्रित सेल को उलट (reverse) देता है। प्रायोरिटी क्यू केवल उम्मीदवारों को शेड्यूल करती है; gScore सत्य का स्रोत (source of truth) बना रहता है।

5. जटिलता और ट्रेड-ऑफ

लेज़ी-एंट्री कार्यान्वयन में, V पहुंच योग्य सेल और E पड़ोसी किनारों (neighbor edges) के साथ, एक बाइनरी हीप O((V + E) log V) समय और O(V) स्थान लेता है। चार-पड़ोसी वाले ग्रिड पर, E असल में O(V) है। एक अधिक मजबूत सुसंगत ह्यूरिस्टिक आमतौर पर सबसे खराब स्थिति की सीमा (worst-case bound) को बदले बिना विस्तारित (expanded) सेल की संख्या को कम करता है। एक सटीक डिक्रीज़-की हीप डुप्लिकेट एंट्रीज़ को कम कर सकता है लेकिन कार्यान्वयन की जटिलता को बढ़ाता है।

6. सत्यापन और दृश्यता

• स्टार्ट और गोल के समान होने, ब्लॉक किए गए एंडपॉइंट्स, एक खाली ग्रिड, अंतराल वाली दीवार, वेटेड डिटूर और अगम्य लक्ष्य का परीक्षण करें।
• यादृच्छिक (randomized) गैर-नकारात्मक ग्रिडों पर h=0 का उपयोग करके प्राप्त लागत की तुलना Dijkstra से करें।
• पुष्टि करें (assert) कि प्रत्येक लौटाया गया कदम सन्निकट (adjacent) और ट्रैवर्सिबल है, और पाथ की लागत को स्वतंत्र रूप से फिर से कैलकुलेट करें।
• विस्तारित सेल, स्टेल पॉप्स, अधिकतम हीप साइज़ और ह्यूरिस्टिक उल्लंघनों को ट्रैक करें; स्टेल-पॉप में अचानक वृद्धि डुप्लिकेट शेड्यूलिंग या खराब डेटा संरचना सीमा का संकेत दे सकती है।

7. सामान्य गलतियां

• नोड को मान्य पॉप के बजाय पहली बार मिलने पर ही स्थायी रूप से क्लोज़्ड चिह्नित करना।
• बिना स्केलिंग या एडमिसिबिलिटी जांच के चार-तरफा यूनिट मूवमेंट के लिए यूक्लिडियन दूरी का उपयोग करना।
• पड़ोसी सेल में प्रवेश करने की लागत के बजाय वर्तमान सेल की लागत को जोड़ना।
• हीप के किसी पुराने (stale) रिकॉर्ड से गोल पॉप होने पर पाथ लौटा देना।
• start == goal को संभालना भूल जाना या ब्लॉक किए गए एंडपॉइंट्स की अनुमति देना।

8. अनुवर्ती प्रश्न

मैनहट्टन दूरी कब एडमिसिबल होती है?

गैर-नकारात्मक लागतों और न्यूनतम ट्रैवर्सल लागत m के साथ चार-तरफा मूवमेंट के लिए, प्रत्येक आवश्यक क्षैतिज या लंबवत कदम की लागत कम से कम m होती है; इसलिए मैनहट्टन दूरी गुणा m वास्तविक शेष लागत से अधिक नहीं हो सकती।

डायगोनल मूवमेंट ह्यूरिस्टिक को कैसे बदलते हैं?

ऑक्टाइल (octile) या चेबीशेव (Chebyshev) शैली की निचली सीमा (lower bound) का उपयोग करें जो डायगोनल और सीधे मूवमेंट की लागतों से मेल खाती हो। फॉर्मूले को सबसे सस्ते वैध संयोजन को दर्शाना चाहिए और एक निचली सीमा बने रहना चाहिए।

यदि खोज के दौरान ग्रिड बदल जाए तो क्या होगा?

एक वर्ज़न्ड स्नैपशॉट में खोजें और उपयोग करने से पहले पाथ को मान्य करें, या ग्रिड वर्ज़न बदलने पर पुनः प्रारंभ करें। विभिन्न वर्ज़नों की लागतों को मिलाने से इष्टतमता (optimality) और सुरक्षा दोनों अमान्य हो सकते हैं।