山登り探索と分枝限定探索は、人工知能で使用される 2 つのヒューリスティック探索アルゴリズムです。これら2つのアプローチの違いは何ですか?
3428 次
2 に答える
16
山登り探索は、解の最初の推測から始めて、解が見つかるかヒューリスティックが極大値に行き詰まるまで、局所的な変更を繰り返し行うことで機能します。多くの検索を並行して実行したり、後続の状態を確率的に選択したりするなど、局所的な最大値に行き詰まらないようにする方法はたくさんあります。多くの場合、山登りアルゴリズムは正しい答えに急速に収束します。ただし、これらのアプローチのいずれも、最適なソリューションを見つけることが保証されているわけではありません。
分岐限定ソリューションは、検索スペースを断片に分割し、1 つの部分を探索してから、各検索中に得られた情報に基づいて検索スペースの他の部分を除外しようとすることで機能します。最終的に最適な答えを見つけることが保証されていますが、そうするのに長い時間がかかる場合があります。多くの問題では、分枝限定アルゴリズムが非常にうまく機能します。これは、少量の情報で検索スペースが急速に縮小される可能性があるためです。
要するに、山登りは正しい答えを見つける保証はありませんが、多くの場合、非常に高速に実行され、適切な近似が得られます。分枝限定法は常に正しい答えを見つけますが、そうするのに時間がかかる場合があります。
お役に立てれば！
于 2013-01-30T18:05:53.727 に答える
3
ヒル クライミングは次のように機能します。
剪定を伴う深さ優先検索 (これは単純な形式の枝限定) は次のように機能します。
一般に、分岐限定は 1000 以上の変数と 1000 以上の値にスケーリングしません。ヒル クライミングは可能ですが、タブー検索を追加することで修正できるローカル オプティマでスタックします。
于 2013-01-31T12:40:07.530 に答える