A *算法實現節點 - 父母錯誤

Question

我對A *的嘗試存在問題 - 每次運行時都不會發生，但每隔一段時間就會發生這種情況，因此兩個單元成爲彼此的父母。 當我嘗試重新創建路徑時，這反過來導致無限循環。我一直在試圖找出爲什麼這會發生一段時間，但無法弄清楚，所以任何幫助將不勝感激。

def find_path(self, start, end): 
    tstart = time.time() 
    count = 0 
    evaled = set() 
    notEvaled = set([start]) 
    start.g_score(start) 
    start.h_score(end) 
    start.f_score() 

    while len(notEvaled) != 0: 
     current = min(notEvaled, key=attrgetter('f'))  
     notEvaled.remove(current) 

     for neighbour in current.neighbours: 
      if neighbour.full or neighbour in evaled: continue 
      if neighbour in notEvaled: 
       if neighbour.parent != None and neighbour.parent.g > current.g: 
        neighbour.parent = current 
        neighbour.g_score(start) 
        neighbour.f_score() 
      else: 

       neighbour.parent = current 

       neighbour.g_score(start) 
       neighbour.h_score(end) 
       neighbour.f_score() 
       notEvaled.add(neighbour) 

       if neighbour == end: 
        path = [] 
        while end != None: 
         path.insert(0, end) 
         end = end.parent 
        return path 

      evaled.add(current) 

    return None 

這裏是我的得分功能，但我懷疑他們不管

def g_score(self, start): 
    if self == start: 
     self.g = 0 
    else: 
     self.g = self.parent.g + 1 

def h_score(self, end): 
    self.h = abs(end.x - self.x) + abs(end.y - self.y) 

def f_score(self): 
    self.f = self.g + self.h 

Answer 1

我開始之前：通用命名約定是openSet/closedSet，而不是evaled/notEvaled。當您需要使用雙重否定符時，您使用的命名約定會變得混亂，如：aNode not in notEvaled。所以，在我的回答中，我使用了對比。該站出來給我

的一件事是你從openSet（notEvaled），取出後立即加入current節點到closedSet（evaled）。

突出的第二件事是在將其添加到openSet之前檢查節點是否是端點。雖然這可能看起來像是一種優化，但它實際上會迫使您在每個打開的節點上執行檢查，而不是在實際訪問的開放節點的子集上執行檢查。

這是您的A *算法的改編，應該按預期工作。它是基於pseudo code from Wikipedia除了它集成了reconstruct_path方法：

def find_path(self, start, end): 
    tstart = time.time() 
    count = 0 
    closedSet = set() 
    openSet = set([start]) 
    start.g_score(start) 
    start.h_score(end) 
    start.f_score() 

    while len(openSet) != 0: 
     current = min(openSet, key=attrgetter('f'))  
     openSet.remove(current) 
     closedSet.add(current) 

     #Check if goal is reached 
     if(current == end): 
      #Construct path from start to goal 
      path = [] 
      while end != None: 
       path.insert(0,end) 
       end = end.parent 
       return path 

     #Open neighbors 
     for neighbour in current.neighbours: 
      if neighbour.full: continue 
      if neighbour in closedSet: continue 

      tentative_g_score = 1 + current.g 

      if neighbour not in openSet or tentative_g_score < neighbor.g: 
       neighbour.parent = current 
       neighbour.g = tentative_g_score 
       neighbour.f_score() 
       if neighbour not in openSet: 
        openSet.add(neighbour) 

    return None