C++ での Greedy Best-First 検索アルゴリズムの実装

コンピュータ サイエンスにおける優れた問題解決は、Greedy Best First Search (GBFS) などの効率的なアルゴリズムに大きく依存しています。 GBFS は、経路探索や最適化の問題に対する最適なソリューションとしての信頼性を確立しています。したがって、この記事では、C での実装を検討しながら、GBFS について詳しく説明します。

＃＃＃文法＃＃＃ リーリー ＃＃＃アルゴリズム＃＃＃

貪欲な最良の最初の検索アルゴリズムは、グラフ内の特定の開始ノードからターゲット ノードまでのパスを見つけることを目的としています。以下はアルゴリズムの一般的な手順です -

空の優先キューを初期化します。

• 開始ノードを優先キューに入れます。

• 訪問したノードを追跡するために空のセットを作成します。

• プライオリティキューが空でない場合 -

• 最高の優先順位を持つノードをキューからデキューします。

• デキューされたノードがターゲット ノードの場合、アルゴリズムは終了し、パスが見つかります。

• それ以外の場合は、デキュー ノードを訪問済みとしてマークします。

• デキューされたノードのすべての未訪問の隣接ノードを優先キューに入れます。

• 宛先ノードに到達する前に優先キューが空になった場合、パスは存在しません。

• 方法 1: ユークリッド距離に基づくヒューリスティック関数

  ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー
イラスト

このコードには 2 つの重要な要素が含まれています。まず、隣接リストを使用してグラフ構造を表す Graph クラスの定義が含まれています。

2 番目に、CompareEuclideanDistance を導入します。これは、ユークリッド距離公式を使用してターゲット ノードからの距離を推定することでノードを評価するためのカスタム コンパレーターです。

greedyBestFirstSearch 関数は、貪欲な最良の最初の検索アルゴリズムを実装します。優先キューを使用して、ヒューリスティック値に基づいてノードを保存します。

このアルゴリズムでは、まず開始ノードを優先キューに入れます。

各反復で、最も優先度の高いノードをキューから取り出し、それがターゲット ノードであるかどうかを確認します。

ターゲット ノードが見つかった場合は、「パスが見つかりました!」というメッセージが出力されます。それ以外の場合、アルゴリズムは、デキューされたノードを訪問済みとしてマークし、未訪問の隣接ノードをキューに入れます。

プライオリティ キューが空になり、ターゲット ノードが見つからない場合は、「パスが存在しません!」というメッセージが出力されます。

main 関数は、グラフを作成し、開始ノードとターゲット ノードを定義し、greedyBestFirstSearch 関数を呼び出すことにより、アルゴリズムの使用法を示します。

方法 2: マンハッタン距離に基づくヒューリスティック関数

この問題を解決するための私たちの戦略には、マンハッタン距離の概念に依存するヒューリスティック関数の使用が必要です。この距離測定はタクシー距離とも呼ばれ、ノード間の水平距離と垂直距離を加算することを含みます。

＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

イラスト

このコードは、方法 1 と同様の構造に従いますが、カスタム コンパレーター CompareManhattanDistance を使用します。このコンパレーターは、マンハッタン距離の式を使用して、ターゲット ノードまでの推定距離に基づいてノードを比較します。

greedyBestFirstSearch 関数は、マンハッタン距離ヒューリスティックを使用した貪欲な最良の最初の検索アルゴリズムを実装します。

main 関数は、アルゴリズムの使用法を示し、グラフを作成し、開始ノードとターゲット ノードを定義して、greedyBestFirstSearch 関数を呼び出します。

＃＃＃結論は＃＃＃

この記事では、貪欲なベストファースト検索アルゴリズムとその C での実装について説明します。これらの方法を採用することで、プログラマはグラフ内のパスを効率的に見つけて、最適化問題を解決できます。ユークリッド距離やマンハッタン距離などのヒューリスティック関数の選択は、さまざまなシナリオでのアルゴリズムのパフォーマンスに大きく影響する可能性があります。

以上がC++ での Greedy Best-First 検索アルゴリズムの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。