8

一般的な問題には局所的な最大値とプラトーが含まれることは知っていますが、この特定の検索に関連する問題が他にあるかどうか、およびこれらの問題を克服するための最善の行動方針について知りたいです。

この検索を使用するのに適した問題の例を誰かに教えてもらえますか？

4

1 に答える 1

15

最良優先探索の問題：

  1. 貪欲です。多くの場合、非常に迅速なソリューションにつながります（開発されたノードの数は指数関数的に増加しないため、ソリューションの深さに比例して増加します！）が、ヒューリスティック関数にエラーがあり、次のノードを探索するときに間違った答えが返されることがあります。

  2. 無限分岐にも問題があります。i深さのノードのヒューリスティック値が 。であるブランチをたどっていると仮定しますh(v_i) = 2^-i。ゼロになることは決してありませんが、最初に貪欲な人がこれらのノードを開発し続けます。
    例：

                            2
                       / \  
                      /   \
                     /     \
                    1      1.5
                    |       |
                   1/2      1
                    |       |
                   1/4      0
                    |
                   1/8
                    |
                   1/16
                    |
                   ...

上記は許容できるヒューリスティック関数ですが、それでも最良優先探索では解決策が得られず、無限分岐でスタックすることに注意してください。

ソリューション：

  1. これを克服するために、統一されたアルゴリズム（ダイクストラのアルゴリズムや重み付けされていないグラフのBFSなど）を使用できます。
  2. 「最良優先探索」と、A*アルゴリズムとして知られるダイクストラを組み合わせて使用​​できます。
    A *アルゴリズムは実際には貪欲な最良優先アルゴリズムですが、に従って選択する代わりに、h(v)次に探索するノードを選択しましたf(v) = h(v) + g(v)（ここg(v)で「これまでのコスト」です。アルゴリズムは完全であり（存在する場合は解決策を見つけます）、最適です（「最良」解を見つける）許容可能なヒューリスティック関数が与えられている場合。

とにかく最良優先探索を使用する場合：

  1. 完璧なヒューリスティック（文献に示されh*ている）がある場合、最良優先探索は最適な解決策をすばやく見つけます。
  2. 最適なソリューションを気にしない場合は、1つのソリューションをすばやく見つけたいだけです。通常はそれでうまくいきます（ただし、無限分岐の問題には注意する必要があります）。
  3. A *を使用する場合、実際には最良優先探索を使用しますが、onf:V->Rではなくonを使用しh:V->Rます。
于 2012-12-19T11:54:17.710 に答える