山登り法と最良優先探索
1. 概要
検索はコンピュータサイエンスの根本的な問題です。 結果として、与えられた問題に対する最適な解決策を見つけるために検索するための多くのアルゴリズムがあります。 山登り法と最良優先探索（BeFS）は、よく知られている検索アルゴリズムの2つです。 いくつかの点で似ていますが、違いもあります。
このチュートリアルでは、最初に山登り法と最良優先探索（BeFS）アルゴリズムについて説明し、それらの特性を比較します。
2. 山登り法検索
山登り法は、単純なヒューリスティック検索アルゴリズムです。 グローバルな最適値を見つけるために、あるポイントからランダムに開始し、隣接するポイントを調べます。 現在のポイントよりも良いポイントを見つけたら、その方向に移動します。 次に、新しいポイントについても同じことを行い、近くにこれ以上良いポイントがないポイントに到達します。 これは、Javaソースコードを使用した山登り法の例です。
プロセスを擬似コードで表現することもできます。
3. 最良優先探索
幅優先探索（BFS）と混同しないように、最良優先探索（BeFS）には、アルゴリズムの大規模なファミリーが含まれています。 たとえば、 A*とB*はこのカテゴリに属します。 これは、BFSと深さ優先探索（DFS）の長所を組み合わせたアルゴリズムです。 BFSとDFSはパスコストを知らずにグラフをトラバースしますが、
次に、各ステップで、BeFSは、検索スペースの深さまたは幅のみを盲目的にトラバースするのではなく、ヒューリスティックが最も低いノードを展開します。 加えて、
最良優先探索アルゴリズムの擬似コードは次のとおりです。
4. 山登り法と最良優先探索の比較
2つのアルゴリズムには多くの共通点があるため、それらの長所と短所は多少似ています。 たとえば、どちらも最適なソリューションを見つけることが保証されていません。
山登り法の場合、これはローカルオプティマでスタックすることによって発生します。 それらをバイパスする1つの方法は、さまざまな初期化と並行してアルゴリズムを実行することです。 このようにして、グローバルな最適化につながる「丘」を見つける可能性を高めることができます。 BeFSの場合、後続ノードが親ノードであるノードにアクセスすると、ループに陥る可能性があります。 これは、ヒューリスティック関数を適切に選択することで回避できます。
さらに、山登り法は高原や橋がありがちです。 高原は、周囲のポイントが現在の状態と等しい状態です。 この場合、次の動きを見つけることができないため、アルゴリズムが混乱する可能性があります。 ランダムに選択すると、どこにも通じない道に私たちを置く可能性があります。 一方、尾根は勾配がゼロではない局所的な最適値です。 これにより、アルゴリズムがすべての方向に移動できないため、アルゴリズムが尾根上を移動するのが困難になる可能性があります。 したがって、アルゴリズムは目標に到達するためにジグザグ型のパスを選択する必要があり、それにより速度が低下します。
良い面として、山登り法は、各ステップで目標の状態と現在の状態を保存する必要があるため、メモリをほとんど必要としません。 逆に、BeFSでは、最適な次の状態を選択するために、開いているノードと閉じているノードをすべて2つのキューに格納する必要があります。 したがって、より多くのストレージが必要になります。
最後に、山登り法が現在の状態よりも優れていると判断した最初のネイバーを選択する一方で、BeFSはより多くのネイバーをチェックし、それらをヒューリスティック関数と比較します。 これにより、いくつかの州の中から最適なものを選択することができます。
2つのアルゴリズムの長所と短所を次のように要約できます。
5. 結論
このチュートリアルでは、2つのよく知られた検索アルゴリズム、山登り法と最良優先探索について学び、それらを互いに区別するいくつかの機能を比較しました。
