拡張されたノードの最適性

Question

私が許容される一貫したヒューリスティックを持っているとします。

本当ですか、私がノードを展開するとき、私がこのノードに見つけたパスが最適であることを保証したということですか？

ウィキペディアのこの擬似コードを見てください：

function A*(start,goal)
 closedset := the empty set    // The set of nodes already evaluated.
 openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
 came_from := the empty map    // The map of navigated nodes.

 g_score[start] := 0    // Cost from start along best known path.
 // Estimated total cost from start to goal through y.
 f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

 while openset is not empty
     current := the node in openset having the lowest f_score[] value
     if current = goal
         return reconstruct_path(came_from, goal)

     remove current from openset
     add current to closedset
     for each neighbor in neighbor_nodes(current)
         tentative_g_score := g_score[current] + dist_between(current,neighbor)
         if neighbor in closedset
             if tentative_g_score >= g_score[neighbor]
                 continue

         if neighbor not in openset or tentative_g_score < g_score[neighbor] 
             came_from[neighbor] := current
             g_score[neighbor] := tentative_g_score
             f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
             if neighbor not in openset
                 add neighbor to openset

 return failure

私はそれが真実であるべきだと思います。このため：

if current = goal
     return reconstruct_path(came_from, goal)

それが真実でなければ、このテストはソリューションが最適であることを私に保証するものではありませんか？

私が得られないものと私がこの質問をしている理由はこれです：

if neighbor in closedset
         if tentative_g_score >= g_score[neighbor]
             continue

隣人がクローズドリストにある場合、それはすでに拡張されていることを意味します。なぜ彼らはスコアをテストしているのですか？なぜ次の状態が機能しないのでしょうか？

if neighbor in closedset
         continue

Answer 1

いくつかの観察結果でこの質問に貢献させてください。それらのほとんどは、応答を参照しています シャウル.

まず、そして何よりも、私は答えが提供されたことを発見しました 質問が指し示しました Shaullは少し奇妙です。単調性の特性は奇妙な方法でそこに定義されており、実際、私は質問を投稿しました---私はそれが間違っていると言っているのではなく、私にとっては奇妙であり、あまり一般的で率直に言って、私はそれが少し疑わしいです間違っている。

元の質問では、さまざまな質問を見るので、段階的に行きましょう。

初め、 一貫性 通常、次のように定義されます[Pearl、1984]：ヒューリスティック$ h（n）$は、$ h（n） leq c（n、n '） + h（n'）$の場合にのみ一貫しています。 $ c（n、n '）$は、$ n $ n $と$ n' $を結ぶ最短経路のコストを表します。許容範囲（すなわち、$ h（n）<h^*（n）$が$ h^*（n）$がノード$ n $の真の最適なコストであることは、$の場合、一貫性からすぐに暗示されることは明らかだと思います。 h（t）= 0 $ここで、$ t $はゴールノードです。これや他の定義については、ヒューリスティック検索に関する一般的な誤解".

これまでのところ、言う必要はありません」私が許容される一貫したヒューリスティックを持っているとします「。「一貫したヒューリスティックを持っていると仮定して」と言って十分です。

さて、あなたの最初の質問について。一貫したヒューリスティックがある場合、ノードを再開する必要がないか、同等に、ノード$ n $が$^*$によって拡張されるたびに、発見されたパスが必然的に最適です。

証拠: ：これは真実ではないと仮定し、パス$ pi langle s、n_1、n_2、 ldots、n_k、n rangle $を介してノード$ n $を拡張した後、別のパス$ pi ' langle sがありました。 n'_1、n'_2、 ldots、n'_l、n rangle $など、$ g _ { pi}（n）> g _ { pi '}（n）$。 $ f（n）= g（n）+h（n）$は、私たちの仮定から$ f _ { pi}（n）> f _ { pi '}（n）$ $ h（n）$であることに注意してください。ノード$ n $に続いたパスにもかかわらず、同じ値を取得します。しかし、これは不可能です。なぜなら、$ n $は後継者またはパス$ pi $として拡張されたため、$ f _ { pi}（n） leq f _ { pi '}（n）$。もちろん、ノード$ n'_i $の$ h（n'_i）$の大きな値があるため、エラーはパス$ pi '$に沿ってどこかでコミットされたと言うかもしれません。 、しかし、これは一貫性の定義によって不可能です。

ここから、状態が明らかになるはずです：

if current = goal return reconstruct_path(came_from, goal)

目標を拡張しようとすると、発見されたパスが最適であることが保証されているため、スムーズに機能します。

あなたの2番目の質問、あなたの投稿の理由に関して、Shaullは彼の返信の脚注ですでに答えました：ヒューリスティック関数が一貫している場合、ノードは決して再開されず、あなたの状態：

if neighbor in closedset continue

十分です。ただし、実際には、単に別の状態に置き換えられます。ノードを拡張する場合、子供は拡張されていない場合にのみ開いて追加されます（クローズドセットではありません）。 ）。オープンリストとクローズドリストを管理するための適切な構造により、これは非常に早く実行できます。このトリックにより、そのステートメントを使用する必要はありません。

しかし、繰り返しますが、Shaullが言っていることを念頭に置いてください。あなたの投稿であなたが示す偽コードは、一貫性のないヒューリスティックな機能でも動作することを目的としています。あなたが求めているのは、実際、一貫性の仮定から生じる単純化です。

お役に立てれば、

Pearl、1984] Judea Pearl。経験則。アディソンウェスリー。 1984年

Answer 2

A*アルゴリズムは非網羅的な検索アルゴリズムであり、すべての可能性をチェックするものではありませんが、ヒューリスティックがグラフの特定のノードに到達するコストの正確な推定値を一貫して提供するという仮説に基づいています。アルゴリズムは、コストのために特定の可能性をスキップしますが、見積もりが間違っている場合、スキップされたノードのリストを通過するより良いパスがあるかもしれません。したがって、ガランティーはムルシティックガランティーに依存しています。

提示されたアルゴリズムに関して、実際にテストは間違っています。閉じたリストのノードは、完全に調査されており、新しいパスを拡大できないため、そこにあります。

Answer 3

これはヒューリスティックに依存します。 $をa to d to d to end and and $ start to b to c to d to d to end $を起動します。ここで、$ a $よりもはるかに高いスコアを与える$ b、c、d $を与えることを好む悪いヒューリスティックを持っていると仮定し、非最適なパスで$ end $に達するでしょう。特に、$ d $を開くと、最適ではないパスになります。