具有燃料约束和可变加油的最短路径算法

Question

假设您有一个无向加权图.您希望找到从源到目标节点的最短路径,同时从一些初始"燃料"开始.每条边的重量等于你在边缘丢失的"燃料"量.在每个节点,您可以为燃料计数添加预定量的燃料 - 该值可以为0.可以多次访问节点,但只有在您第一次到达节点时才会添加燃料.**所有节点可以提供不同数量的燃料.

这个问题可能与从A镇到B镇的火车有关.尽管两者都是通过简单的轨道直接连接,但是煤炭短缺,所以火车没有足够的燃料来进行旅行.相反,它必须进行从A镇到C镇的更短的旅程,已知有足够的燃料来覆盖返回A然后继续前往B.因此,最短的路径是从A到C的距离加上从C到A的距离加上从A到B的距离.我们假设燃料成本和距离是相等的.

我已经看到一个例子,节点总是填充"坦克"达到其最大容量,但我还没有看到一种算法在不同的节点处理不同的加油量.什么是解决此问题的有效算法？

Answer 1

不幸的是这个问题是 NP 困难的。给定一个从 s 到 t 且决策阈值为 d 的旅行商路径实例（是否存在一条访问长度最多为 d 的所有顶点的 st 路径？），将该问题作为一个实例如下。添加一个通过很长的边连接到 t 的新目标顶点。提供启动燃料 d．设置新边的长度和除目的地之外的每个顶点的燃料，以便 (1) 所有顶点的总燃料等于新边的长度 (2) 如果没有收集所有燃料。当且仅当存在一条较短的旅行商路径时，才有可能到达目的地。

因此，该问题的算法将类似于 TSP 的算法。通过使用非零燃料在源、目标和顶点上构建完整的图来进行预处理。每条边的长度等于距离。

如果特殊顶点足够少，则指数时间 (O(2^n poly(n))) 动态规划是可能的。对于由顶点子集（按非递减大小的顺序）和该子集中的一个顶点组成的每一对，确定访问所有子集并在指定顶点结束的最便宜的方式。通过使用子集的预先计算结果减去顶点和每个可能的最后路径点，可以有效地完成此操作。有一种优化可以修剪比已知解决方案更糟糕的子解决方案，如果不需要使用很多航路点，这可能会有所帮助。

否则，该游戏可能是整数规划。这是一种表述，很可能可以改进。如果将x(i, e)有向边作为e第i步（从零开始计数），则令 为 1，否则f(v)为 0。令 为 顶点 处可用的燃料v。让y(i)是一个变量，它是步骤后手中的燃料i。假设总步数为T。

minimize sum_i sum_{edges e} cost(e) x(i, e)
subject to
for each i, for each vertex v,
    sum_{edges e with head v} x(i, e) - sum_{edges e with tail v} x(i + 1, e) =
        -1 if i = 0 and v is the source
         1 if i + 1 = T and v is the target
         0 otherwise
for each vertex v, sum_i sum_{edges e with head v} x(i, e) <= 1
for each vertex v, sum_i sum_{edges e with tail v} x(i, e) <= 1
y(0) <= initial fuel
for each i,
    y(i) >= sum_{edges e} cost(e) x(i, e)
for each i, for each vertex v,
    y(i + 1) <= y(i) + sum_{edges e} (-cost(e) + f(head of e)) x(i, e)
for each i, y(i) >= 0 
for each edge e, x(e) in {0, 1}