algorithm - 图中成本取决于遍历历史的最短路径

Question

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

如果这就是整个任务，我会使用 Dijkstra 算法找到最短路径(并将城市成本添加到它之前连接的道路的成本中)。

但是:

城市有类似合作协议(protocol)的东西 - 当您访问其中一个城市并支付费用时，进入这个特定合作伙伴关系中的其他城市是免费。

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

这种问题有算法吗？

谢谢。

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] 中。在图中添加边:

• START 和 (S[i], s[1]) 对于每个 S[i] 和 S[i] 中的 s[1]
• (S[i], s[n]) 并为每个 S[i] 和 S[i] 中的 s[n] 结束。
• (S[i], s[k]) 和 (S[i'], s[k+1]) 对于 1...n-1 中的每个 k 以及对于每个 S[i] 和 S[ i'] 包含相应的元素。

设边权全为1，设进入(S[i], s)的代价也为1。所有城市/顶点(S[i], s), (S[i], t)分摊相同的费用。没有两条道路/边缘共享成本。

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