3

標準的な方法は次のとおりです。AI: 最新のアプローチ

function UNIFORM-COST-SEARCH

node <- INITIAL-STATE
frontier <- priority queue ordered by PATH-COST, with node as the only element
explored <- an empty set
loop do
    if frontier is empty then return failure
    node <- POP frontier  /* chooses the lowest-cost node in frontier */
    if GOAL-TEST(node) then return SOLUTION(node)
    add node to explored
    for each action in ACTIONS(node) do
        child <- CHILD-NODE(problem, node, action)
        if child is not in explored or frontier then
            frontier.INSERT(child)
        else if child is in frontier with higher PATH-COST then
            replace that frontier node with child

ここで、この手順を実行するのは複雑です。通常の優先度キューでは、特定の要素の優先度を効率的に更新できません。

        else if child is in frontier with higher PATH-COST then
            replace that frontier node with child

アルゴリズムを次のように変更することを考えています。

function UNIFORM-COST-SEARCH-Modified

node <- INITIAL-STATE
frontier <- priority queue ordered by PATH-COST, with node as the only element
explored <- an empty set
loop do
    if frontier is empty then return failure
    node <- POP frontier  /* chooses the lowest-cost node in frontier */
  > if node is in explored then continue
    if GOAL-TEST(node) then return SOLUTION(node)
    add node to explored
    for each action in ACTIONS(node) do
        child <- CHILD-NODE(problem, node, action)
  >     if child is not in explored then
            frontier.INSERT(child)

したがって、フロンティアに繰り返し状態が含まれているかどうかは気にしません。フロンティアで繰り返される最初の状態のみを展開します。パスコストはconsistentであり、フロンティアは を使用して実装されてpriority queueいるため、より高いコストを持つ他の繰り返される状態を無視しても害はありません。

それは合理的ですか？

アップデート

申し訳ありませんが、一貫したヒューリスティックなケースに特に興味があることを忘れていました。

4

2 に答える 2

3

考え方は原則として正しいですが、バグがあります:

  > if node is in explored then continue

ヒューリスティック関数が単調でない (許容性と矛盾しない) 場合、この行は失敗を引き起こす可能性があります。

A* は、新しいコストが以前に見つかったコストよりも優れている場合、ノードを再探索できます。これらの状況は、非単調ヒューリスティック関数で発生します。

continue新しいコストが の頂点にアタッチされたものよりも「大きい」場合にのみ必要exploredであり、そこにのみ存在する場合はそうではありません。

編集：（コメントと質問の編集に関する質問に基づく）

の場合h=0、A* は実際に Dijkstra のアルゴリズムに減衰します。また、Dijkstra のアルゴリズムは、既に「探索された」ノードを変更する必要がないため (もちろん、正の重みが仮定されます)、アルゴリズムはこれらのケースに対して正しいです。

一般に、既に訪問したノードへの再訪問は単調ヒューリスティック関数では発生しないため、これは問題ではなく、これらのケースではアプローチは正しいですが、非単調ヒューリスティック関数に適用しないように注意してください。

于 2012-10-02T13:37:43.457 に答える
1

はい、これは機能するはずです。A* と UCS がAIMAの第 2 版で説明されている方法だと思います。優先キューで状態が繰り返されますが、ソリューション/パスを 1 つだけ生成したい場合は、最小コストのバージョンのみが返されます。

編集：プログラムを読み間違えました。if child is not in exploredノードの隣接ノードを展開するときは、この手順をスキップする必要があります。

于 2012-10-02T13:34:27.850 に答える