पायथन - एक स्टार पाथफाइंडिंग एल्गोरिदम

Question

को गति दें मैंने अपने पहले थोड़ा-जटिल एल्गोरिदम को कोड किया है, A Star Pathfinding एल्गोरिदम का कार्यान्वयन। मैंने ग्राफ़ को कार्यान्वित करने पर कुछ Python.org advice का पालन किया ताकि एक शब्दकोश में प्रत्येक नोड को भी जुड़े हुए सभी नोड्स शामिल हों। अब, चूंकि यह सब एक गेम के लिए है, इसलिए प्रत्येक नोड वास्तव में नोड्स के ग्रिड में सिर्फ एक टाइल है, इसलिए मैं कैसे ह्युरिस्टिक और मेरे प्रासंगिक संदर्भ में काम कर रहा हूं।

समय के लिए धन्यवाद मुझे पता है कि मैं इस समारोह को एक सौ बार एक से अधिक बार सफलतापूर्वक चला सकता हूं। समझ में आता है कि यह मुझे थोड़ा असहज बनाता है, यह किसी भी अन्य 'गेम स्टफ' के बिना ग्राफिक्स या गेम लॉजिक की गणना करने के बिना है। तो मुझे यह देखना अच्छा लगेगा कि आप में से कोई भी मेरे एल्गोरिदम को तेज कर सकता है, मैं साइथन या उसके रिश्तेदारों से पूरी तरह से अपरिचित हूं, मैं सी

किसी भी रैंपिंग के बिना कोड नहीं कर सकता, यहां मेरा ए है स्टार समारोह

def aStar(self, graph, current, end): 
    openList = [] 
    closedList = [] 
    path = [] 

    def retracePath(c): 
     path.insert(0,c) 
     if c.parent == None: 
      return 
     retracePath(c.parent) 

    openList.append(current) 
    while len(openList) is not 0: 
     current = min(openList, key=lambda inst:inst.H) 
     if current == end: 
      return retracePath(current) 
     openList.remove(current) 
     closedList.append(current) 
     for tile in graph[current]: 
      if tile not in closedList: 
       tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10 
       if tile not in openList: 
        openList.append(tile) 
       tile.parent = current 
    return path 

Answer 1

खुले और बंद सेट के लिए सूचियों के बजाय सेट का उपयोग करना एक आसान अनुकूलन है।

openSet = set() 
closedSet = set() 

यह in और not in परीक्षण हे के सभी कर देगा (1) हे के बजाय ( n)।

Answer 2

जैसा ऊपर बताया गया है, closedSet को एक सेट में बनाएं।

मैं एक ढेर import heapq रूप openList कोडिंग करने की कोशिश की:

import heapq 

def aStar(self, graph, current, end): 
    closedList = set() 
    path = [] 

    def retracePath(c): 
     path.insert(0,c) 
     if c.parent == None: 
      return 
     retracePath(c.parent) 

    openList = [(-1, current)] 
    heapq.heapify(openList) 
    while openList: 
     score, current = openList.heappop() 
     if current == end: 
      return retracePath(current) 
     closedList.add(current) 
     for tile in graph[current]: 
      if tile not in closedList: 
       tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10 
       if tile not in openList: 
        openList.heappush((tile.H, tile)) 
       tile.parent = current 
    return path 

हालांकि, आप अभी if tile not in openList पर खोज करने के लिए की जरूरत है, तो मैं इस करना होगा:

def aStar(self, graph, current, end): 
    openList = set() 
    closedList = set() 

    def retracePath(c): 
     def parentgen(c): 
      while c: 
       yield c 
       c = c.parent 
     result = [element for element in parentgen(c)] 
     result.reverse() 
     return result 

    openList.add(current) 
    while openList: 
     current = sorted(openList, key=lambda inst:inst.H)[0] 
     if current == end: 
      return retracePath(current) 
     openList.remove(current) 
     closedList.add(current) 
     for tile in graph[current]: 
      if tile not in closedList: 
       tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10 
       openList.add(tile) 
       tile.parent = current 
    return [] 

Answer 3

मैं सेट का उपयोग होता है के रूप में कहा गया है, लेकिन मैं न्यूनतम तत्व खोजने के लिए एक ढेर का भी उपयोग करता हूं (वह जो अगले current होगा)। इसके लिए ओपनसेट और ओपनहेप दोनों को रखने की आवश्यकता होगी, लेकिन स्मृति वास्तव में कोई समस्या नहीं होनी चाहिए। इसके अलावा, ओ (1) में हेप डालें और ओ (लॉग एन) में ढेर ताकि वे तेज़ हो जाएंगे। एकमात्र समस्या यह है कि हेपैक मॉड्यूल वास्तव में इसके साथ कुंजी का उपयोग करने के लिए नहीं बनाया जाता है। निजी तौर पर, मैं इसे चाबियों का उपयोग करने के लिए बस संशोधित करता हूं। यह बहुत मुश्किल नहीं होना चाहिए। वैकल्पिक रूप से, आप केवल ढेर में टाइल (टाइल.एच, टाइल) का उपयोग कर सकते हैं।

इसके अलावा, मैं पुनरावृत्ति के बजाय पुनरावृत्ति का उपयोग करने के लिए अरोर्नस्टरिंग के विचार का पालन करता हूं, लेकिन साथ ही, मैं तत्वों को path के अंत में जोड़ दूंगा और अंत में path को उलट दूंगा। इसका कारण यह है कि सूची में 0 वें स्थान पर कोई आइटम डालना बहुत धीमा है, (ओ (एन) मुझे विश्वास है), जबकि संलग्न करना ओ (1) है यदि मुझे सही याद है। उस भाग के लिए अंतिम कोड होगा:

def retracePath(c): 
    path = [c] 
    while c.parent is not None: 
     c = c.parent 
     path.append(c) 
    path.reverse() 
    return path 

मैं अंत में वापसी पथ डाल क्योंकि ऐसा लगता है कि यह अपने कोड से करना चाहिए।

यहाँ अंतिम कोड सेट, ढेर और नहीं क्या का उपयोग कर रहा है:

import heapq 


def aStar(graph, current, end): 
    openSet = set() 
    openHeap = [] 
    closedSet = set() 

    def retracePath(c): 
     path = [c] 
     while c.parent is not None: 
      c = c.parent 
      path.append(c) 
     path.reverse() 
     return path 

    openSet.add(current) 
    openHeap.append((0, current)) 
    while openSet: 
     current = heapq.heappop(openHeap)[1] 
     if current == end: 
      return retracePath(current) 
     openSet.remove(current) 
     closedSet.add(current) 
     for tile in graph[current]: 
      if tile not in closedSet: 
       tile.H = (abs(end.x - tile.x)+abs(end.y-tile.y))*10 
       if tile not in openSet: 
        openSet.add(tile) 
        heapq.heappush(openHeap, (tile.H, tile)) 
       tile.parent = current 
    return []