-1

我已经实现了一个使用Dijktra's Algorithm. 感谢 Dijkstra，我可以打印从所需来源到所需目的地的最短路径。但是，我想做的是添加一个功能，通过左转、右转命令告诉我们方向。

例子：

从 A 到 D：

假设 A 位于街道 1 ，B 位于街道 2 ，D 位于街道 2 左侧 60 米处。

从 A 到 D：

去街 2 。转左 。走大约 60 米。它会在你的左边。

我需要你的想法。谢谢！

4

1 回答 1

0

要从路径生成驾驶指令，您需要在图表中存储其他信息：

对于每条道路，它的长度。这很简单

对于每个十字路口，每对事件道路之间的关系。

您可以存储十字路口周围每条道路的方位角（道路 1-2 从十字路口 1 向西），然后根据两条道路之间的相对角度、十字路口的类型（正常/环形交叉路口）和拓扑排序生成驾驶指令和所有其他道路的相对角度。

这种方法的好处是更紧凑的表示，但它需要更多的编程。

或者，您可以分别存储每对之间的关​​系。这更可靠（只有人类才能真正理解世界上每种可能的十字路口类型的复杂性），但更新起来更加手动（毕竟，理论上一点人工智能可以推迟十字路口类型，即使有错误）。

如果你有一张巨大的地图，你会想要坚持第一种方法。如果您手动构建地图，您可能更喜欢第二个 - 只需确保不实际存储每个道路对的字符串（除非它们被语言所占用），否则您的内存需求可能会飙升。在将映射序列化为文件时，这需要格外注意（同样，如果您选择 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.
}

要生成方向，请使用与地图一起存储的信息。记住要连接逻辑上遵循的道路（总结它们的长度）（在那个交叉路口没有指令=隐含的“直行” - 几条道路可能会合为一条，但每条只能遵循一条），其余的很简单。

于 2012-12-27T19:52:13.200 回答