7

你会使用什么算法来创建一个应用程序，给定适当的数据（城市列表、火车路线、火车站）能够返回任意两个用户选择的城市之间的连接列表？应用程序必须只选择那些落入接受的列车变化限制的连接。

示例：如果我需要从巴黎前往莫斯科，我会询问应用程序乘坐哪列火车。1 站/切换 - 应用程序返回一条路线：火车 1（巴黎-柏林）-> 火车 2（柏林->莫斯科）（不存在直接连接）。

图形示例 地图

http://i.imgur.com/KEJ3I.png

如果我向系统询问从A镇到G镇的可能连接，我会得到回应：

  • 棕线（0 个开关 = 直接）
  • 棕线到B镇/橙线到G镇（1个开关）
  • 棕线到B镇/橙线到D镇/红线到G（2个开关）
  • ...所有其他可能性

第 2 和第 3 选项比第 1 选项短，但第 1 选项应该有优先权（因为不涉及换车）。

4

2 回答 2

10

假设唯一重要的是“停止/切换次数”，那么问题实际上是在未加权有 向图中找到最短路径。

图模型是G = (V,E)whereV = {all possible stations}和E = { (u,v) | there is a train/route from station u to station v }
注意：假设你有一列从 a_0 开始的火车，经过 a_1、a_2、...a_n 的路径：那么 E 将包含：(a_0,a_1),(a_0,a_2),..,(a_0,a_n)并且(a_1,a_2),(a_1,a_3),...正式地：对于每个i < j: (a_i,a_j) ∈ E .

BFS解决了这个问题，并且是完全的[总是找到一个解决方案，如果有一个解决方案] 和最优的[找到最短路径]。

如果边 [路线] 被加权，则需要类似dijkstra 算法的东西。

如果您想要所有可能路线的列表，可以使用迭代深度 DFS，而无需维护访问集，并将找到的所有路径打印到目标的相关深度。[BFS 无法返回所有路径与集团的反例]

于 2012-04-04T16:15:22.903 回答
0

我认为您需要计算所有对的最短路径。检查http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm。

于 2012-04-04T16:19:04.870 回答