algorithm - Dijkstra 最短路径算法的变体

Question

我被这个问题困住了(我的解决方案太慢了)。我将先描述问题，然后再描述我的解决方案。

问题:给定 N 个站，每个站都位于数轴上的 x_i 位置，我们想从第一个站移动一个机器人以最低的货币成本到最后一个站点(站点按非递减 x_i 顺序排序)。我们有一个机器人，它从充满电的电池开始，电池具有 K(不一定是整数)个单位的功率，并且可以移动 E(不一定是整数)个长度单位消耗的功率单位。在第一站和最后一站之间的任何一站，我们都可以充电。每个站收取相同的统一费率 F 美元开始充电，加上 c_i 美元的每单位电力补充。如果机器人当时的电量等于或低于K/2，只有可以充电或者如果不充电就无法到达下一站；每次机器人充电时，它都必须充电到 100%(即 K)。

我的解决方案:我很确定这是最短路径问题的变体，除了我们针对货币成本进行优化。我正在运行 Dijkstra SSSP。然而，对于每个州，我们都需要跟踪货币成本和剩余能源，因为通过在便宜的充电站充电来提前支付更高的成本可能比把钱存到最后要好。因此，我不再维护cost[i]=cheapest known way to station i，而是维护cost[i][energy]=cheapest known way to station i能量。在优先级队列中，我仅按成本对状态进行排序，因为我不确定是否有办法为成本和剩余能量创建试探法。这个算法在某些测试用例上真的很慢，因为如果 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 即可找到到达终点站的最经济方式。我们不需要同时跟踪距离和金钱的原因是距离已经编码在图的结构中:图的边缘恰好是从一个站到另一个。