私はしばらくの間、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))
ヒープ キューの使用については知っていますが、それはこの質問の焦点ではありません。