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

Question

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

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

但是：

城市有类似于伙伴关系协议的东西——当你访问其中一个并支付费用时，进入这个特殊伙伴关系中的其他城市是免费的。

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

那种问题有算法吗？

谢谢你。

Answer 1

这里要做的是集群。

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

这将非常类似于将相关道路的收费更改为0对于有协议的两个城市之间的边缘。

Answer 2

Dijkstra非常适合这个问题，如果你对它进行适当的建模。

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

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

注：如果入场费是保守的，那么订单可能无关紧要（协议条款中的所有城市都提供相同的成本效益，无论订单如何？）。如果是这样，请将历史表示为一个集，您将获得更小的搜索空间：

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

所有这些都使得您的搜索空间相当大。如果您的合作模式允许，您可以再次重复使用它。例如，卡车的有用状态可能是其位置，以及一组未锁定的协议。如果这些不可锁定的协议少于城市，那么你就把你所在的州压缩到最低限度。

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

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

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

注意：使用A-star将非常困难，因为找到一个可接受的启发式将不那么简单。我不能提供建议，因为我不知道你的费用是否包括某种距离函数。目前，由于成本可能会根据状态变为零，因此唯一可接受的启发式算法可能是常量值。没有用。。。

Answer 3

您可以将集合覆盖问题简化为此问题。这意味着你的问题是NP难的，你不应该期望找到一个有效的解决方案（通常）。

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

为了完整起见，下面是从集合覆盖到图形问题的简化：

集合覆盖问题是给定一个有限集S={S[1]，…，S[n]}，以及S的子集：S[1]，S[1]，S[2]。。。，S【N】。我们要求您找到覆盖S的这些子集的最小数目。

要使用您的城市问题来找到最小覆盖率，请构建这样的图。设图的顶点为起点、终点和对（S[i]，t），其中和t在S[i]中。在图形中的以下位置之间添加边：

• 开始和（S[i]，S[1]），对于每个S[i]，S[1]在S[i]中

让边权重都为1，输入（S[i]，S）的成本也为1。所有城市/顶点（S[i]，S），（S[i]，t）共享相同的成本。没有两条道路/边缘共享成本。

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