图中的最短路径,其中成本取决于遍历的历史

Question

我的目标是找到与道路(边缘)相关的给定城市(顶点)之间的最短路径(最低成本).每条道路和每个城市都有进入该道路/城市之前必须支付的费用(成本).

如果那将是完整的任务,我将使用Dijkstra算法来找到最短路径(并将城市成本添加到之前连接的道路的成本).

但是:

城市有类似合伙协议的东西 - 当你访问并支付其中一个时,在这个特殊合作关系中进入其他城市是免费的.

因此,顶点(在它之前连接的边)的成本取决于已经遍历的顶点.

这种问题有算法吗？

谢谢.

Answer 1

您可以将设置封面问题减少到这个问题.这意味着你的问题是NP难,你不应该期望找到一个有效的解决方案(一般来说).

这意味着你应该希望合作伙伴的数量很少,也许你可以考虑所有可能的非单一道路/城市合作伙伴关系,并为每个合作伙伴寻找最短的路径(假设你的路径只会通过)您正在考虑的给定子集中的道路/城市).然后你的算法将在2 ^ P*(N + M)时间内运行,其中P是伙伴关系的数量,N和M分别是城市和道路的数量.

为了完整起见,这是从集合覆盖到图形问题的减少:

集合覆盖问题是你得到一个有限集S = {s [1],...,s [n]},以及S:S [1],S [1],S [2]的子集,...,S [N].您被要求找到涵盖S的这些子集的最小数量.

要使用城市问题查找最小封面,请构建一个这样的图形.设图的顶点是START,END和对(S [i],t)其中和t在S [i]中.在图表中添加边缘:

让边权重为1,让进入的成本(S [i],s)也为1.所有城市/顶点(S [i],s),(S [i],t)共享相同成本.没有两条道路/边缘共同承担费用.

现在,从START到END的最低成本路径对应于找到覆盖S的最小S [i]集合.该路径的成本将是1 + n + p,其中p是最小覆盖的大小.

Answer 2

您在这里要做的是聚类。

在开始运行 Dijkstra 或某种其他算法之前，请对图表进行一些更改，其中所有彼此达成协议的城市都将转换为一个新节点。
从这个节点，您可以到达从其中任何一个城市到达的任何城市（当然选择最便宜的边缘）。

这与将相关道路的收费更改为0达成协议的两个城市之间的边缘非常相似。