5

さまざまな種類の分岐がある列車ゲームで経路探索の解決策を見つけようとしています。電車をあるレールから別のレールに移動させたいのですが、パスファインディング以外はすべて実装されています。

列車が追従できるように、レールのリストを取得する必要があります。さて、問題はどうやってリストを取得するかです。

  • A* を試しましたが、ノード (レール) が既にアクセスされている場合は検索が停止するため、機能しませんでした。ポイントに到達する方法は、おそらく最長のルートを移動することであるため、これは問題です。
  • フラッド フィルを試してみましたが、今回は、既にアクセスした場合でも検索を停止しませんでした。問題は、パスを再構築する方法と、再び逆戻りできないことをどのように選択するかです。

列車が目的地に着くまでに何度もレールを通過しなければならない場合があります。

何か案は？

始点は A、終点は B です。ご覧のように、緑色のパスが進むべき道です。黒い円は、列車が複数回 (この場合は 2 回) 踏むレールです。

A->B

ここに画像の説明を入力

そして明らかに、2 黒から 3 赤に到達する必要があります。1black -> 2red -> 1red -> 3red だけではいけません。

4

2 に答える 2

6

この絵を見ると

ジャンクション

あなたの問題は有向グラフでうまく表現されるようです。各ストップと各ジャンクションに、グラフ内の2 つのノード (列車の方向ごとに 1 つずつ) を指定します。 Dijkstra のアルゴリズムは有向グラフで完全に機能するため、問題がその形に分かれば、あとは簡単です。

たとえば、上の図では、 から始まりA、 に移動しjunction 1ます。そこから移動する場所は 1 つだけjunction 2なので、 --> からの矢印と-- A>junction 1からの矢印があります。どちらを選択しても最終的には になりますが、反対方向に移動するため、そこから別のノードを作成します。そこから、またはに行くオプションがあります。junction 1junction 2junction 1AB

グラフ

の の1 つを削除したことに注意してくださいJ1。これは不要であるためです(移動する場所は 1 つだけです)。

列車が のような停留所で停止して方向転換できる場合、Aこれら 2 つのノードを両方向のエッジで接続するか、単にそれらを 1 つのノードに結合することができます。

エッジに重みを付けて距離を指定できます。

于 2013-10-01T13:36:14.607 に答える
0

フラッド フィルは実際に機能するはずですが (同様のケースで使用しました)、スイッチとセグメントを慎重に操作する必要があるだけです。

アルゴリズムは、同じセグメントを異なる方向に渡すことを許可する必要がありますが、同じ方向に渡すことはできません。つまり、各セグメントは実際には 2 つの別個のものと見なされるべきです。

パスを再構築するには、フラッディング中にセグメントに番号を割り当てる必要があります。これにより、到達した各セグメントが -N-1でマークされNます。次に、後方に移動している間、セグメントを追跡して、番号が着実に 1 ずつ減少するようにする必要があります。

それは本当に一種のBFSです。

于 2013-10-01T10:12:44.737 に答える