A *アルゴリズムの実装ノード - 親バグ

Question

私はA *での試行に問題があります - これは実行されるたびに発生しますが、頻繁に2つのセルがお互いの親になるようにします。 これは、パスを再作成しようとすると無限ループになります。私はこれがなぜ今のところ起こるのかを調べようとしてきましたが、それを理解することはできないので、どんな助けもありがたいです。ここで

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/closedSet convensionを使用します。私に際立っ

ことの一つは、あなたがすぐにopenSet（notEvaled）からそれを削除した後closedSet（evaled）にcurrentノードを追加しています。

第2の点は、ノードがエンドポイントであるかどうかを確認してから、openSetに追加することです。これは最適化のように見えるかもしれませんが、実際に訪れたオープンノードのサブセットではなく、開いているノードごとにチェックを実行するように強制します。

ここでは、期待どおりに動作するA *アルゴリズムを採用しています。

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