2

A* 検索と幅優先検索を使用して、8 パズルで勝利のゲーム状態を見つけています。勝利状態はこんな感じ

123
456
780

このようなリストとして保存されます

[1,2,3,4,5,6,7,8,9,0]

ヒューリスティック関数を使用して各ノードに (その状態に基づいて) スコアを付けましたが、最高のスコアが付けられたノードに優先順位を付ける方法が、プログラムの速度を大幅に低下させていると思います。実際、私が作成した幅優先探索アルゴリズムは、A* アルゴリズムよりもはるかに優れています (ただし、内部の仕組みのほとんどは同じですが)。

A* 検索を遅くしている主な原因は、フリンジ (ノードを保持するリスト) 内の位置を使用して、優先順位を付ける次のノードを示していることだと思います。 

def aStartSort(node):
    if not fringe:
        fringe.append(node)
    else:
        fl = len(fringe)
        if node.score >= fringe[fl-1].score:
            fringe.append(node)
        else:
            for i in range(fl):
                if node.score < fringe[i].score:
                    fringe.insert(i, node)

ご覧のとおり、ノードがフリンジに追加されるたびに、スコアがそれよりも悪いノードを探し、その前に自分自身を挿入します。これにより、fringe.pop(0) を実行したときに、最高スコアのノードと少なくとも同点になることが保証されます。しかし、巨大なリストの真ん中にアイテムを挿入するのは、とても速いアクションではありませんか? より良い代替手段は何ですか？

また、フリンジ リストを並べ替えないことも検討しましたが、それも同様に悪いか悪いように思えます (ノードがポップ アウトされるたびにリスト全体を検索する必要があるためです。

4

1 に答える 1

1

特定の質問に答えるには、スコアが整数であると仮定して、リストの辞書を作成し、スコアをそのスコアを持つノードにマッピングします。これにより、挿入は O(1) になり、可能なスコア範囲を反復できるため、取得も高速になるはずです。

于 2016-02-25T00:58:34.643 に答える