Dijkstra最短路径算法的一个变化

Question

我被困在这个问题上(我的解决方法太慢了)。我会描述这个问题然后我的解决方案。

问题：给定的N站，每个站在数字线上的x_i位置，我们希望以最低的货币成本将机器人从第一个站移到最后一个站(按不递减的x_i顺序排序)。我们有一个机器人，从最大充电电池开始，电池的K (不一定是积分的)单位的功率，并可以移动E (不一定是积分)单位长度单位的功率消耗。在第一站和最后一站之间的任何一站，我们都可以充电。每个站收取相同的统一费率F美元开始充电，加上每单位电力补充c_i美元。机器人只有当其功率在或低于K/2时才能充电，或者在不充电的情况下不能到达下一个站；每次机器人充电时，它都必须充电到100% (即K)。

我的解决方案：，我很确定这是最短路径问题的一个变化，除了我们正在优化货币成本。我在运行Dijkstra SSSP。然而，对于每一个州，我们都需要跟踪货币成本和剩余能源，因为早些时候通过在廉价的车站充电来增加成本可能比把钱存到最后更好。因此，我没有继续维护cost[i]=cheapest known way to get to station i，而是维护了cost[i][energy]=cheapest known way to get to station i with a certain energy。在优先级队列中，我只按成本排序状态，因为我不确定是否有一种方法可以同时为成本和剩余能量创建一个启发式方法。这种算法在某些测试案例中速度很慢，因为如果E和K都很大，那么每个站点都有可能到达前面的每个站点，从而生成一个庞大的图形。我想我必须修剪搜索边界，但我不确定怎么做。有什么想法吗？

Answer 1

这听起来更像是动态规划的工作，而不是Dijkstra的工作。站i的最佳成本是不考虑你到达那里之前所做的选择。

向后穿过车站。对于i站点，请考虑您可以从那里到达的所有站点j > i (您已经计算了它们的最佳成本)。在这些选择中选择最优。

伪码：

opt[N-1] = 0                                        // cost of the last station is 0
for i = N-2 down to 0                               // loop backwards over the stations
    opt[i] = infinity
    for j = i+1 to N-1 where (x_j - x_i) * E <= K   // loop over all next stations that can be reached without a flat battery
        energyToJ = (x_j - x_i) * E
        if (energyToJ >= K/2                        // we are allowed to recharge
          or j == N-1                               //  or we cannot reach the next station because there is none
          or x_{j+1} - x_i) * E > K)                //   or because it is too far
            costJ = F + energyToJ * c_j + opt[j]    // total cost via j is cost to j + cost from j
            if (costJ < opt[i])                     // keep track of the optimal cost
                opt[i] = costJ                      

return opt[0]

编辑

由于动态编程对您来说不是一种选择，所以我将使用Dijkstra的方法来处理它：

从一个站点i，您可以直接移动到每个站j，其中之一持有以下内容：

• K/2 <= x_j - x_i <= K
• 0 <= x_j - x_i < K/2，并且没有j' > j为其x_j' - x_i <= K

用N顶点创建一个图，每个站点一个。有一个有向边e_ij从站i到站j，当且仅当上述两种条件之一成立。e_ij的重量就是在那里充电的成本，也就是F + (x_j - x_i) * c_j。

现在您可以在这个图上运行Dijkstra，以找到到达最终站点的最经济的方法。我们不需要同时跟踪距离和金钱的原因是，距离已经被编码在图的结构中:图的边缘完全是从一个站到另一个站的所有可能的移动。