algorithm - ダイクストラのアルゴリズムで隣人を見つけるにはどうすればよいですか?

Question

ノードの隣接ノードを見つけるにはどうすればよいですか? 特定のノードを別のノードの隣人にするものは何ですか? ちなみにコードはLuaで書いています

Answer 1

A* では、次の 3 つのことを定義します。

1. ある隣接ノードから別のノードに移動するコスト
2. 特定のノードとゴール ノードの間の距離
3. 特定のノードに隣接するノード

それらの最初のものは、必要に応じて単純にすることも複雑にすることもできます。すべてのノードが同じ距離にある単純なグリッドベースのパスファインディングを行っているときは、非常に単純な検索のために常に 1 を返します。

Dijkstra のアルゴリズムは、通常、0 を返すだけで、実際にはそれらの 2 番目をカバーします。

しかし、あなたの質問は3番目のことです：

グリッドでこれを行っていた場合、見ているグリッド空間のユークリッド隣接であるグリッド空間を見つけることができます。つまり、グリッド空間 x2y2 の場合、近傍はユークリッド空間の x1y2、x3y2、x2y1、および x2y3 です。

グリッドを扱っていない場合は、ノードをワールドに配置するとき、またはその直後に各ノードの兄弟データを入力し、関連付けられたリストに保存する方法が必要になると思いますそのノードで。ノードから他のすべてのノードまでの距離を計算し、最短のノードなどを見つけることで、これを行うことができます。非常にコストがかかる可能性がありますが、最初に 1 回しか実行しないため、これらのノードが動的でない場合は問題ありません。