-1

を使用するコードを実装しましたDijktra's Algorithm。ダイクストラのおかげで、目的のソースから目的の目的地までの最短経路を印刷できます。ただし、私がやりたいことは、 turn left 、 turn right コマンドで道順を教えてくれる機能を追加することです。

例:

A から D まで:

A が通り 1 にあり、B が通り 2 にあり、D が通り 2 の左 60 メートルにあるとします。

A から D まで:

通り 2 に移動します。左折してください 。約60m先左側。

あなたのアイデアが必要です。ありがとうございました！

4

1 に答える 1

0

パスから運転指示を生成するには、グラフに追加情報を保存する必要があります。

道路ごとに、その長さ。これは簡単です

各交差点について、各対のインシデント道路間の関係。

交差点周辺の各道路の方位角を保存し (道路 1-2 は交差点 1 から西に向かいます)、2 つの道路間の相対角度、交差点のタイプ (通常/ラウンドアバウト)、およびトポロジーの順序から運転指示を生成し、他のすべての道路の相対角度。

このアプローチには、よりコンパクトな表現という利点がありますが、より多くのプログラミングが必要です。

または、各ペア間の関係を個別に保存することもできます。これは信頼性が高くなります (世界で考えられる交差点の種類の複雑さを真に理解できるのは人間だけです) が、更新はより手作業になります (結局のところ、たとえエラーがあったとしても、小さな AIが理論的には交差点の種類を延期することができます)。

巨大なマップがある場合は、最初のアプローチに固執する必要があります。マップを手動で作成している場合は、2 番目のものを好むかもしれません。ただし、実際には各道路のペアに文字列を格納しないようにしてください (言語によってインターンされている場合を除く)。そうしないと、メモリの需要が急増する可能性があります。これは、マップをファイルにシリアル化するときに特別な注意が必要です (これも、ZIP 圧縮を選択した場合、大幅に緩和される可能性があります)。

マップが単純な 4 方向の交差点のみをleft/straight/right考慮している場合、各ペアで格納される情報は単なる列挙型 (アプローチ #2)、または交差点周辺のエッジの順序付け (アプローチ #1) です。null.

たとえば、交差点は（最も単純なケース、アプローチ＃1）のようになります

private Road[] roads = new Road[4];

public enum Direction{
  Left, Straight, Right, Back;
  // utility methods
}

public Direction getDir (Road from, Road to){
  // input checking stripped for clarity
  int iFrom = roads.indexOf(from);
  int iTo = roads.indexOf(to);
  // more input checking
  int iDiff = (iFrom - iTo) % 4;
  if(iDiff < 0) iDiff +=4 ;
  return Direction.getRelative90(iDiff);
  //Direction.getRelative90 is just a switch statement.
}

ルート案内を生成するには、マップに保存されている情報を使用します。論理的に続く道路を連結する (それらの長さを合計する) ことを忘れないでください (その交差点に指示がない = 暗黙の「直進」 - 複数の道路が 1 つに続く可能性がありますが、それぞれから 1 つのみが続く必要があります)。残りは簡単です。

于 2012-12-27T19:52:13.200 に答える