3

スターアルゴリズムで8パズルソルバーを実行しています。このソルバーにマンハッタンと置き忘れたヒューリスティック関数を実装します。場合によっては、ソルバーは正常に機能します。しかし、場合によっては、解決策を見つけるのに多くの時間がかかります。私の問題の1つは、オープンリスト（拡張を待機中）で最も低い値を持つノードを検索する関数にあると思います。

 a part of psedocode(from wiki)
 while openset is not empty
     x := the node in openset having the lowest f_score[] value
     if x = goal
         return reconstruct_path(came_from, came_from[goal])
     ................................

では、最小のf_score値を見つけるための最良の方法は何ですか？最小値を見つけるか、追加する状態があるときにリストを変更する必要があります（状態を追加するときにリストを並べ替えます）。これにより、最小値が最初の位置になります。

4

1 に答える 1

3

ヒープを維持します。

与えられnた要素は、時間内にそれらをヒープに変えることができますO(n)。それらがヒープになったら、時間内に要素を追加および削除でき、時間O(log(n))内に最小の要素を見つけることができますO(1)。

1つを実装するために必要なのは、配列だけです。ルートノードはであり、 '番目0より下のノードはとにあります。ヒープ条件は、すべてのノードがその上のノードよりも小さいことです。最小のものは常にルートです。要素を追加するには、その要素を配列にプッシュして、自然なレベルに「フォールダウン」させます。要素を削除するには、ルート要素を取り出し、配列から最後の要素を取り出し、ルートに配置して、適切な場所に「バブルアップ」させます。（「バブリングアップ」フェーズでは、2つの子ノードのうち小さい方と交換して、最終的にその下に小さい子ノードがなくなるまで続けます。）配列を効率的に作成するには、中央値要素から開始して、各要素を「バブル」させます。上"。i2*i+12*i + 2O(n log(n))O(n)。

于 2011-04-05T00:35:21.707 に答える