私は、最小コストのルートを見つけるためにパスファインディングを実行する必要があるプロジェクトに取り組んでいます。最短ルートで構いません。これまでのところ、A* は問題外のようで、正直に言って Prim のアルゴリズムを理解していません。
ルートを見つけるために必要な地図の種類について説明しましょう。これはマップの例です:
+------|-*----
+------|----|-
+--|--------|-
+@-|----------
「*」は出発地、「@」は目的地です。行内の「+」記号は、a) 1 つのステップと同じコストがかかり、b) ルート全体のコストが半分になる直接ルートを示します。
これは、開始位置から「+」ルートを経由して目的地まで 10 の「ステップ」があることを意味し、最終的にコストは 5 になります。左端の「|」を使用するには 15 のステップがあります。ルート (「|」は「-」よりも低コストですが、「+」よりは劣ります)、最終的にコストは 15 になります。明らかに、コストが 5 のルートが使用するルートです。
現在、これを C# で実装するのに問題があります。私は現在、方法がブロックされた場合、またはステップのコスト、および新しい位置に移動して戻る「ステップ」機能を持っています。これはうまく機能しますが、現時点では「|」で終わるという点で非常に単純です。「+」の前に見つかった場合 (より速いルートが見つからないため、移動全体の費用が大幅に高くなることを意味します)。
各場所を「訪問済み」としてマークすることを考えていましたが、最低コストのルートがループバックすることは完全にありえます。また、多くの異なるパスがあり、それぞれが一意であり、それぞれが異なるパス セグメントを使用する場合があります (以前の実行で既にアクセスされている可能性があります)。明らかに、最も安価なパスを見つけるために各パスをたどる必要がありますが、同じルートを何度も何度も検索することなしにそれを行う方法を理解することはできません.
より簡単にする場合は、移動を目的地に向かってのみに制限できます (つまり、下降した後に再び上昇することはできません)。
誰かが洞察を提供できれば、それは素晴らしいことです!