沙漠旅行者最小付费问题：贪心与动态规划求解咨询

算力阿峰

2026-8-9

问题解答

a) 贪心算法及最优性判断

贪心策略：仅在无法到达下一个点（或终点）时才停留补水，其余情况直接继续行程。
最优性判断：该贪心策略无法保证最优。例如，提前在某个绿洲补水虽会产生当前费用，但能大幅降低终点的倒水费用，最终总费用更低。比如：起点到A为6公里，A到B为3公里，B到终点为3公里，水壶容量10升。贪心策略会在B点补水（费用1），终点倒水费用49，总费用50；而提前在A点补水（费用16），终点倒水费用16，总费用32，远低于贪心方案。因此贪心算法无法得到全局最优解。

1. 最优解结构与最优性证明

最优解结构：若从起点到第i个点并在i点补水的方案是最优的，那么该方案中最后一个停留点j（j < i）对应的从起点到j点并在j点补水的方案也必须是最优的。
最优性证明（反证法）：假设存在一个最优路径到i点，但其前序停留点j对应的路径不是最优的，那么必然存在一个费用更低的路径到j点。将该路径替换原方案中的j点路径，得到的新路径总费用会比原最优路径更低，与原路径最优矛盾。因此最优解满足最优子结构；同时，计算不同点的paid值时会重复计算子问题，满足重叠子问题性质，适合动态规划求解。

2. `paid`的递归定义

首先定义点索引：起点为0，途中绿洲为1~n，终点为n+1；d[k]为第k个点距起点的距离，C为水壶容量。

基础情况：paid(0) = 0（起点初始满水，无补水费用）
对于途中绿洲i（1 ≤ i ≤ n）：
paid(i) = min{ paid(j) + (C - (d[i] - d[j]))² | j ∈ [0, i-1], d[i] - d[j] ≤ C }
其中(C - (d[i]-d[j]))²是在i点补水的费用：从j到i消耗d[i]-d[j]升水，剩余C - (d[i]-d[j])升，倒掉这部分的费用为其平方。
最终最小总费用：
total_min = min{ paid(j) + (C - (d[n+1] - d[j]))² | j ∈ [0, n], d[n+1] - d[j] ≤ C }
其中(C - (d[n+1]-d[j]))²是到达终点时的倒水费用。

3. 多项式时间求解算法与复杂度分析

自底向上动态规划伪代码：

输入：C（水壶容量），oases（有序绿洲距离数组），end（终点距离）
输出：最小总费用，停留点路径

// 构建包含起点、绿洲、终点的完整距离数组
d = [0] + oases + [end]
m = len(d) - 1  // 终点索引
paid = 数组，大小为m+1，初始值为无穷大
paid[0] = 0
prev = 数组，大小为m+1，初始值为-1（记录前驱停留点）

// 计算每个途中绿洲的最小费用
for i from 1 to m-1:
    for j from 0 to i-1:
        if d[i] - d[j] <= C:
            current_cost = paid[j] + (C - (d[i] - d[j])) ** 2
            if current_cost < paid[i]:
                paid[i] = current_cost
                prev[i] = j

// 计算到达终点的最小总费用
total_min = 无穷大
final_j = -1
for j from 0 to m-1:
    if d[m] - d[j] <= C:
        end_cost = paid[j] + (C - (d[m] - d[j])) ** 2
        if end_cost < total_min:
            total_min = end_cost
            final_j = j

// 推导路径（见问题4）
path = get_path(prev, final_j, d)

return total_min, path

复杂度分析：

时间复杂度：两层循环遍历所有点，时间为O(m²)，其中m为总点数（起点+绿洲+终点），属于多项式时间。
空间复杂度：存储paid和prev数组，空间为O(m)。

4. 行程方案推导

通过prev数组回溯得到停留点：

从final_j（到达终点前的最后一个停留点）开始，依次回溯prev数组，直到起点0。
将回溯得到的点索引反转，得到停留点的顺序（起点→...→final_j），最后加上终点。
回溯函数伪代码：

function get_path(prev, final_j, d):
    path_idx = []
    current = final_j
    while current != -1:
        path_idx.append(current)
        current = prev[current]
    path_idx.reverse()
    // 转换为实际距离
    return [d[idx] for idx in path_idx] + [d[-1]]

5. 示例应用

参数：C=10，绿洲[8,9,16,18,24,27]，终点32。
构建d = [0,8,9,16,18,24,27,32]。

计算paid数组：

paid[0]=0
paid[1]=4（j=0，费用(10-8)²=4）
paid[2]=1（j=0，费用(10-9)²=1）
paid[3]=8（j=1，费用(10-8)²=4，4+4=8）
paid[4]=2（j=2，费用(10-9)²=1，1+1=2）
paid[5]=12（j=3，费用(10-8)²=4，8+4=12）
paid[6]=3（j=4，费用(10-9)²=1，2+1=3）

计算终点最小费用：

j=5：32-24=8≤10，费用(10-8)²=4，总费用12+4=16
j=6：32-27=5≤10，费用(10-5)²=25，总费用3+25=28
最小总费用为16，对应final_j=5。

行程路径：
回溯prev[5]=3 → prev[3]=1 → prev[1]=0，反转后得到停留点：0（起点）、8、16、24，最终到终点32。
总费用：4（8公里处）+4（16公里处）+4（24公里处）+4（终点）=16。

内容的提问来源于stack exchange，提问作者Moudjahed Mohamed