0

我目前正在android中开发一个导航系统，我正在使用dijkstra的最短路径算法我的顶点类包含如下所示的成员：

-------------------------------------
|                 Vertex            |
-------------------------------------
|    |      |           |           |
| id | name | longitude | latitude  |
-------------------------------------

以及具有如下所示成员的边：

---------------------------------------------
|                Edge                       |
---------------------------------------------
|    |      |        |             |        |
| id | name | source | destination | weight |
---------------------------------------------

由于顶点和边具体基于真实数据：交叉点为顶点，一个交叉点与另一个交叉点为边，简单地说，我的应用程序的整个图表就是我所在城市的道路网络。

我的问题是，我仍然无法提出一种算法或算术方程来计算基于一个交叉点到另一个交叉点的距离以及它到达一个交叉点到另一个交叉点的时间的边权重。

4

1 回答 1

1

这取决于您要优化的内容（您可以让用户选择）：

如果你想要最短的路线，一条边的成本就是街道的长度。

如果您想要最快的路线，成本将是预期的街道旅行时间。

如果您想要在油耗方面最经济的路线，成本将是“街道长度/每加仑英里数（预期速度）

燃油经济性因汽车而异，但您可以假设经济性（以每加仑英里数为单位）随着速度线性增长，直到达到一定速度，然后开始下降[维基百科]。因为你总是可以比最大速度慢。速度，假设一个恒定的效率。(miles/gallon) / (miles/hour) = (hours/gallon)，因此成本大约与时间成正比，并以汽车的最有效速度（可由用户输入）应用速度限制。

如果您有准备好的拥堵数据源，请使用它来确定预期的汽车速度。

通过观察汽车来测量预期行驶时间的一种方法是对过去 {interval} 离开街道的所有汽车取平均值（小时？分钟？只有最后一辆车？最后十辆车？）。但是，这并不会很快导致拥堵。你可以取所有汽车的平均速度仍然存在的速度。但是，这会高估红绿灯的效果。

你可以取过去一小时内进入街道的所有汽车的平均速度。average(distance traveled/time spent)或average(distance traveled)/average(time spent)。如果街道没有生命，只需限制其速度或使用更长的测量间隔。

请记住，两个方向的预期速度可能不同（取决于您的数据源），因此请始终使用成对的有向边并分别在每个方向上进行测量。

[1] http://en.wikipedia.org/wiki/File:Fuel_economy_vs_speed_1997.png

于 2012-10-14T09:13:38.080 回答