2

ここに問題があります：
私は以下の考慮事項で出発点から目的地までの道を見つけなければなりません。

与えられたグラフでは、ポイントは次のいずれかになります。

  • （1）チェックポイント->このポイントは計算された最終パスに存在する必要があります


  • （2）鉱山->このポイントは計算された最終パスに存在してはなりません

  • （3）ニュートラルポイント->このポイント
    は、計算された最終
    パスに存在する場合と存在しない場合があります

このためのアルゴリズムが必要です。

4

4 に答える 4

4

まず地雷を取り除き、チェックポイントのリストを作成します。

次に、ほぼ確実に、深さ優先または幅優先の検索を実行する必要があります。どちらがグラフに依存します。適切な剪定ヒューリスティックを使用して、幅優先探索を試すことをお勧めします。シーカーは開始点から開始し、それから自分自身をコピーすることを選択できるときはいつでも、双方向に進みます。訪問したチェックポイントと、最後のチェックポイント以降に訪問したニュートラルノードの2つのリストを保持します。ニュートラルノードにアクセスすると、壁にチェックポイントリストを書き込み、自身のサブセットであるリストをすべて消去します。次のいずれかの条件が発生すると、自動的に終了します。

  • すでにリストの1つにあるノードにアクセスします。
  • 独自のスーパーセットであるチェックポイントリストが壁に表示されます。
  • すべてのチェックポイントを訪問せずに目的地に到着します。

それはあなたが始めるのに十分なはずです。グラフによっては、他にも価値のある最適化（行き止まりの削除など）があります。

（編集：いくつかのグラフが不可能になることを私が見たとき、その最後の状態を傷つけました。）

于 2009-08-17T17:10:15.560 に答える
2

チェックポイントに特定の順序でアクセスする必要がある場合は、ダイクストラのアルゴリズムが簡単なソリューションです。グラフのサブセットに対してアルゴリズムを使用できます。サブセットは、開始ノードと終了ノードがチェックポイント（またはグラフの開始ノードまたは終了ノード）であるグラフになります。エッジの重みを使用して、アクセスしてはならないノードを表すことができます。

ただし、パスファインディング*は、おそらくあなたがやろうとしていることに適しているので、お勧めします。そこにはたくさんのサンプルコードがあります。

これがあなたが始めるための良いチュートリアルです：

A*初心者のためのパスファインディング

地雷とチェックポイントは、グラフ内の重みとして、またはヒューリスティックを使用して表すことができます。これは、チェックポイントが注文されているかどうかに依存する可能性があります。

Gamedev.netはあなたの友達です。幸運を！

于 2009-08-17T17:17:26.887 に答える
1

さて、私はあなたがダイクストラのアルゴリズムを使用できると思います（または同様のもの、それは網羅的で一般的であり、あなたはあなたのデータについてそれほど多くの情報を提供しなかったので、私はダイクストラのアルゴリズムを提案しています）...これらの変更で最短経路を見つける：

  1. チェックポイントの値は、ニュートラルポイントの数の負の値に等しくなります。
  2. 地雷は中立点の数に等しい値を持っています。
  3. ニュートラルポイントの値は1です。

ダイクストラは最短経路（重みが最も小さい経路）を見つけます。これは、すべてのチェックポイントを通過し、すべての地雷を回避することが保証されています。

ただし、これは高速なアルゴリズムではないため、マップが大きすぎると機能しない可能性があります。

于 2009-08-17T16:54:21.507 に答える
1

個人的には、これには深さ優先探索（DFS）を使用します。ダイクストラアルゴリズムは、いくつかのエッジ距離関数に基づいて最短経路を計算するためのものです（ノード間の距離については言及していないため、ノード間の距離はないと仮定しました）。

DFSは次のように変更できます（sがソースで、tが宛先であると想定）。

  • まず、すべての「マイニング」ノードとその隣接するエッジを削除します。地雷ノードにアクセスできない場合は、そこからの着信エッジまたは発信エッジをパスで使用できないため、削除することもできます。
  • ノードからDFSを実行します。
  • DFSが実行されると、[s、a、b、d、e、t]、[s、b、d、t、e]などのノードのシーケンスのセットが作成されます。
  • これらのシーケンスのいずれかにノードtの前にあるすべてのチェックポイントノードが含まれている場合、これは適切なパスです。
  • DFSの結果にそのようなシーケンスがない場合、基準を満たすパスはありません。チェックポイントを逃すか、目的地に到達するために鉱山を訪問する必要があります。

これは最も効率的なアルゴリズムではないかもしれませんが、パスを見つけるために機能するはずです。また、DFSの結果から選択したパスが最適なパスであるという約束もありません。

（これは、チェックポイントに任意の順序でアクセスできることを前提としています）

于 2009-08-17T17:33:34.797 に答える