我试图用一个算法解决这个问题至少一个星期，但没有结果我有一组路（1，2，3，…），每条路至少有一辆车可以通过（A，B，C，…）。我的问题是如何使一个到达另一条道路的乘车次数最少。例如：
道路车辆
1甲，乙
2甲、乙、丙
3 C、D
4 C、D
公元5年
输出应为：
从1，乘A或B到2
从2，乘坐C到4
从4，骑D到5
这里的政策是尽可能耗尽一次行程，但输出的行程变化次数应该最少。
例2：
道路车辆
1 |甲，乙
2甲、乙、丙
3 C、D
4 C、D
5 |甲，乙
6东、西
华氏7度
华氏8度
华氏9度
10华氏度，克
华氏11度
12华氏度，克
13 |克，高
14小时
输出：
从1，乘A到5
从5，骑E到6
从6，乘F到8
从8，骑H到14
请帮我写这道题的算法。我需要为我的项目解决这个问题。谢谢！
注：如果你需要其他的例子或说明，请在下面的评论中告诉我。
最佳答案
考虑这个问题的一种方法是将它建模为一个图搜索问题。对于每个不同的车辆v，构造一个图Gv，其节点是网络中的所有道路，并且由车辆v连接的节点之间有弧。例如，在您的第一个示例中，图GA将有五个节点，其中只有一个从节点1到节点2的连接而图GC将有5个节点，边缘分别为2到3、3到4和4到2。
现在，考虑最后一个图g的构造，如下所示。G是通过取所有车辆v的所有图形Gv（意味着原始图形中每个节点有多个副本）形成的，然后如果有多个不同的车辆都到达一条道路，则在不同图形中的相应节点之间添加边例如，对于原始问题，在图G中，G包含子图GA和GB，…，GE由于道路1由车辆A和B提供服务，您将在图GA和GB中的道路1的节点之间添加一条边，并且由于道路2由车辆A、B和C提供服务，因此将存在连接子图GA、GB和GC的所有道路2节点的边。
您对最小化需要进行的传输的数量感兴趣，因此我们希望在这个图中设置一些度量该值的成本。特别是，我们说，完全包含在其中一个子图gv中的任何边都是零成本的，因为一旦你在一辆给定类型的车辆上，你就不需要做任何更改就可以在车辆服务的道路上移动。但是，我们为连接不同车辆的子图的每一个边分配一个成本，因为遵循这种边意味着您要更改使用的车辆如果您现在跟踪此图中的任何路径，则该路径的总成本是您所做的车辆更改数。
为了最终完成施工，我们需要找到一种方法来确定从起点到终点的成本。为此，我们将向表示旅程开始和结束的图中添加两个新节点s和t。节点s的每一个子图的第一条路的成本为零，因为当您开始旅程时，您可以选择任何车辆作为您的第一步。类似地，最终道路的每个子图节点都有一个零成本的t边缘，因为一旦你到达目的地道路，你在哪辆车上并不重要。
在此设置中，从s到t的任何路径的成本都等于您需要进行的传输总数因此，在这个图中找到从s到t的最短路径会给您提供要走的路径和该路径的代价。例如，可以使用dijkstra的算法来解决这个问题。
这个算法的运行时间不是恒星，但它仍然是多项式时间。假设有n条道路和m辆不同的车辆。我们创建的图中有m个不同的子图，每个子图都是针对一辆车的，在最坏的情况下，这些图中有o（n2）边。如果我们将这些子图的所有对应节点连接在一起，在这里您可以改变线，那么在最坏的情况下，将有o（（m n）2）这样的边，因为有n个节点的m个图，所有节点可能彼此连接。因此，我们有一个具有O（mn）节点和O（（mn）2）边的图，因此我们可以在O（（mn）2+mn log mn）时间内运行Dijkstra算法。
我认为重要的是要摆脱这个问题，你通常可以通过创建一个由旧图的多个副本组成的新图，然后为该图提出一个好的边代价函数，来解决在受某些约束的图中寻找路径的问题。
希望这有帮助！
关于algorithm - 最少乘坐次数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5287435/