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

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

• 对每个 S[i] 进行 START 和 (S[i], s[1])，其中 s[1] 在 S[i] 中
• (S[i], s[n]) 和每个 S[i] 的 END，其中 s[n] 在 S[i] 中。
• (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 是最小覆盖的大小。

Answer 2

这里要做的是聚类。

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

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

0

非常相似。

Answer 3

Dijkstra 非常适合这个问题，如果你建模得当的话。

正确地说，我的意思是您需要认识到卡车的状态不仅是其当前位置，而且是其历史记录。

class TruckState {
    City current;
    List<City> visited;
}

注意：如果入场费保守，顺序可能并不重要（协议条款中的所有城市都提供相同的成本效益，无论顺序如何？）。如果是这样，将历史表示为

Set

，您将获得更小的搜索空间：

class TruckState {
    City current;
    Set<City> visited;
}

---

这一切使得你的搜索空间相当大。如果您的合作伙伴模式允许，您可能会再次进一步减少。例如，卡车的有用状态可能是其位置，以及未锁定的

Set

。如果这些可解锁的协议少于城市，则您可以将您的州压缩到最低限度。Agreements

---

[编辑]：看来顺序很重要：您向协议池的第一个城市支付入场费。您需要跟踪首先访问了协议中的哪个城市。那么我建议如下状态：

class TruckState {
    City current;
    Set<Agreement> unlocked;
}

注意：使用 A-star 将会是

非常困难，因为找到一个可接受的启发式将不是微不足道的。我无法提供建议，因为我不知道您的成本是否包括某种类型的距离函数。就目前情况而言，由于成本可能会根据状态而变为零，因此唯一可接受的启发式可能是恒定值

class TruckState {
    City current;
    Map<Agreement, City> visited;
}

。没用...

Answer 4