-3

私はしばらくの間、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))

ヒープ キューの使用については知っていますが、それはこの質問の焦点では​​ありません。

4

1 に答える 1

2

オリジナルにはオープンセットとクローズドセットがあります。隣人がクローズド セットに含まれているかどうかを確認し、仮のスコアの方が高い場合はスキップします。オープン セットにない場合、または暫定スコアが低い場合は、それをより良いパスとして使用します。

代わりに、開いたセットと見たセットがあります。それが見られたセットにないかどうかを確認し、その場合は見たセットに追加して使用します。

これは大きく異なり、誤った結果をもたらす可能性があります。あなたのアルゴリズムが最短パスにならないと私が知る限り、それは常に最後の隣人をパスとして使用します。

于 2013-04-22T09:50:22.787 に答える