A *検索アルゴリズムの実装

Question

私は、練習用のA *検索アルゴリズムを実装しようとする初心者です。私はそれについて最善の方法は何か疑問に思っています。私はグラフ構造（隣接行列）を作成しました。私の計画はA *を初期と目標の頂点に適用することでした。また、ヒューリスティックを作成し、それを改善します。問題は、これは機能するのでしょうか？私は他の実装を見てきましたが、別のデータ構造を使って実装しました。

Answer 1

どのように隣接行列を実装したかによって異なります。

A *の1つの重要な点は、ノードの隣人を見つけることです。単純な密なビットフィールドとして行列を実装すると、隣接するノードには1、隣接しないノードには0があります。すべてのノードをチェックする必要があるため、この検索は非常に非効率的です。これは非効率的ですが、A *の実装を妨げるものではありません。

隣接行列の実装がより複雑な場合（例：あなたが直接隣人に照会することを可能にする疎マトリックスとして、これはA *の方が適しています。