Скорость упрощения A *

Question

Я пытался некоторое время оптимизировать собственную реализацию алгоритма поиска A * и в итоге немного изменил алгоритмическую часть.

Мне было интересно, будет ли этот подход быстрее обычного A * или нет. Почему или почему нет? Если да, то каковы причины для использования обычного A * над этим немного другим методом?

def find_path(a, b): 
    seen = set() 
    opened = set() 

    parent = {} 
    distance = {a: path_distance(a, b)} 

    while opened: 
     node = min(opened, key=lambda x: distance[x]) 

     if node == end: 
      path = [] 

      while node in parent: 
       path.append(node) 
       node = parent[node] 

      return path 

     opened.remove(node) 

     for neighbor in node.neighbors: 
      if neighbor not in seen: 
       seen.add(neighbor) 
       opened.add(neighbor) 

       parent[neighbor] = node 
       distance[neighbor] = pathDistance(neighbor, b) 

def path_distance(a, b): 
    return sum(y - x for x, y in zip(a.position, b.position)) 

Я знаю об использовании очередей кучи, но это не в центре внимания этого вопроса.

Answer 1

Оригинал имеет открытый комплект и закрытый комплект. Он проверит, находится ли сосед в в закрытом наборе, и если этот предварительный балл выше, то он пропустит его. Если это не в открытом наборе, либо предварительный балл ниже, он будет использовать это как лучший путь.

У вас вместо этого установлен открытый набор и видимый набор. Вы проверяете, не в видимом комплекте, и в этом случае вы добавите его, чтобы его увидеть, и используйте его.

Это очень по-другому и, вероятно, даст неверные результаты. Насколько я могу судить, ваш алгоритм не приводит к кратчайшему пути, он всегда будет использовать последнего соседа в качестве пути.