0

評価関数（f（n）= g（n）+ h（n））が2つのノードで同じものを評価するときに、A*検索ツリーで次に展開する必要があるノード/状態を理解するのに問題があります。
例1

Tree1

私の理解では、フロンティアはf順に並べられた優先キューとして格納されるため、フロンティア上のノードは同じ値を持つため、最初にキューに追加されたノードが評価されます。

例2

Tree2

この例では、Bの評価関数はC未満であるため拡張されましたが、Cと同じfを持つノードDが生成されました。この場合、次に拡張するためにどのノードが選択されますか？

（この質問はおそらくcstheory.stackexchangeに投稿されているはずですが、画像を投稿するのに十分な評判がありません、お詫びします）
よろしくお願いします

4

1 に答える 1

1

どちらを選択するかは関係ありません。優先キューの実装によって異なりますが、新しく作成されたノードDはすでにキューにあるCの前に移動しないため、多くの場合Cになります。Cを続行し、後でh（C）が過小評価されていることに気付くと、現在のノード（Cのアクセサー）のf値がf（D）より大きくなるよりも、アルゴリズムが戻ってDが上になると拡張されます。キューの。ヒューリスティックhは常に実際のコストよりも小さいか等しい値を与える必要があるため、これは機能します。

于 2011-11-26T12:25:29.093 に答える