加重A *検索でフルg（n）対フルh（n）を使用する利点/欠点は何ですか？

Question

Weighted A* = (1 - weight) * g(n) + weight * h(n) 

私の理解では、コストに基づいた完全な検索を行うと、最適なソリューションが得られますが、完全なヒューリスティック検索よりも時間がかかります。これは正しいです？私が知るべき重要なことは他にありますか？

編集：私はもっと理解していると思います。コストに完全に基づいた検索を使用すると、より長いパスにつながる可能性があります。しかし完全なヒューリスティックについてはまだ分かりません。

編集2：ヒューリスティックのみを使用すると、ノードにつながりますが、本当に長いパスが使用されている可能性がありますか？

Answer 1

ケース1（フルグラム（n）は、別名ブラインド検索）：あなただけg(n)に基づいて検討されるべき次のパスを選択するための評価関数f(n)を使用する場合は

、あなたは基本的にダイクストラを使用していますアルゴリズム。つまり、f(n) = g(n) + h(n)とh(n) = 0の場合はf(n) = g(n)となり、各繰り返しで最小コストのパスを探索しています。これにより、最適なパスを見つけることが保証されます（グラフでは肯定的なコストのみ）が、最適ではないパスを探索する可能性があります。 例えば、我々はsからtへのパスを検索する次のグラフには：（

 n1    node | h(node) 
    /\     s | 3 
    2/ \ 1    n1 | 1     
    / \    n2 | 4 
    s  t 
    \ /
    1 \ /4 
     \/
     n2 

とテーブルは私たちに、各ノードのヒューリスティック評価を与えるヒューリスティック、すなわち、私たちは完璧なヒューリスティックを持っていると仮定してみましょう値は常に目標への最短経路に対応します）。したがって、最初の反復では、OPENリストにn1とn2が追加されます。 ブラインド検索が、その後、行われ（またはフルg(n)）されています

• f(n1) = g(n1) = 2。

• f(n2) = g(n2) = 1。

およびノー​​ドn2は、OPENリストに最小のg値を持つため、検討されます。しかし

、我々は*とヒューリスティック値を使用します。

• f(n1) = g(n1) + h(n1) = 2 + 1 = 3を。

• f(n2) = g(n2) + h(n2) = 1 + 4 = 5。

n1が検討され、tその後、最適解につながると道に沿ってn2で次善のパスを探索していません。

したがって、g(n)は、Dijkstra vs A *を意味します。ヒューリスティックが良い見積もり（このように単純化しよう）であれば、A *は常に望ましいでしょう。

ケース2（フルH（N））：

我々はすでに見つかっパスのコストを使用していないので、私たちは、ここでは異なる場合があります、私たちは私たちの機能のヒューリスティック評価を信頼しています。ヒューリスティックの質によっては、グラフ内のすべてのノードまたは最適な経路のみを探索することになりますが、A *の美しい理論的特性は失われてしまいます。