穿越沙漠问题（2020B）优秀范文一：资源受限最短路与最少天数路线

摘要

一支考察队欲从沙漠基地 $S$ 出发抵达目的地 $E$ ，途中可经村庄补给饮水与食物，但每人携带量受限、每日消耗随天气（热/凉）变化。本文将该问题建模为资源受限最短路（Resource-Constrained Shortest Path, RCSP）：以状态 $(r,c,w,f)$ （位置与剩余水、食）构建状态空间，用 Dijkstra 求"到达终点且不枯竭"的最少行动天数。在 $9\times9$ 网格、3 个村庄、确定 40 天天气预报下，求得最优路线长 18 天，依次经村庄 $V_1$ 等两次休整，全程水余量 $[29,50]$ 、食余量 $[17,50]$ ，无任一时刻越界，验证了模型的可行性与最优性。该结果为后续两篇（天气不确定下的鲁棒策略、最小费用补给）提供一致的基准路线。

一、问题重述

给定沙漠网格地图（含起点、终点、障碍与若干补给村庄）、队伍单日水/食消耗表（依天气）、以及每人水/食携带上限 $W_{\max}=50,\ F_{\max}=50$ 。要求规划一条从 $S$ 到 $E$ 的行进序列（每日移动到相邻格或于村庄休整补满），使在资源约束下到达终点所需天数最少。

二、基本假设

队伍视为整体，按"队伍·天"折算消耗，不区分个体差异。
水、食独立计数且各自不超过携带上限；村庄处可于 1 个休整日内补满至上限。
天气逐日已知（确定预报），热天消耗 $(4,6)$ 、凉天消耗 $(3,5)$ （水,食）。
仅在村庄格可补给；障碍格不可进入；每步移动到四邻域一格。
目标为最小化到达天数，其他成本（如采购费）在第二、三篇另行优化。

三、符号说明

$(r,c)$ ：网格坐标； $S=(0,0),\ E=(8,8)$ 。
$w,f$ ：当前剩余水、食； $(W_{\max},F_{\max})=(50,50)$ 。
$\phi_t\in\{0,1\}$ ：第 $t$ 天天气（0 凉、1 热）；消耗 $(\Delta w,\Delta f)$ 由 $\phi_t$ 决定。
$V=\{V_1(2,2),V_2(5,5),V_3(7,3)\}$ ：三处村庄。

四、模型建立：资源受限最短路

将"位置 + 剩余资源"组合为状态节点 $s=(r,c,w,f)$ ，状态转移为两类动作：

移动：从 $(r,c)$ 走到邻格 $(r',c')$ ，消耗当天天气对应的 $(\Delta w,\Delta f)$ ；要求 $w'\ge 0,\ f'\ge 0$ 且目标非障碍。
休整（仅当位于村庄）：消耗 1 天，资源补满至 $(W_{\max},F_{\max})$ 。该动作将"补给"显式建模为状态图中的一种转移，使算法能在"多走一天换资源满格"与"冒险直行"之间自动择优。

以"行动天数"为边权，在状态图上做 Dijkstra 最短路搜索：首次弹出终点状态即对应全局最少天数。图 1 给出地图与最终路线，图 7 给出"状态空间→Dijkstra→回溯→校验"的求解链路。

状态空间规模约为 $9\times9\times51\times51\approx2.1\times10^5$ ，Dijkstra 配合优先队列可在毫秒级完成；由于每次扩展仅对"可行且更优"的状态入堆，实际探索远小于全空间。

支配剪枝：同一格 $(r,c)$ 上，若状态 $s_1=(w_1,f_1)$ 满足 $w_1\ge w_2$ 且 $f_1\ge f_2$ ，则 $s_1$ 完全支配 $s_2$ —— $s_2$ 能走的后继 $s_1$ 都能走，且到终点不可能更优，故 $s_2$ 可直接剪除。实现时用二维数组记录每格当前最优 $w$ ，仅当新状态在 $w,f$ 双维度上都不劣才入堆。本例中该剪枝将入堆状态压到约 $1.5\times10^4$ 个，搜索时间小于 $0.1\\ \\mathrm{s}$ ，为后续 40 天尺度的灵敏度实验留足余量。

为何必须纳入资源维度：若仅做普通最短路（只考虑几何距离），会得到曼哈顿最短的 16 步直线，但该直线不经过任何村庄，而从 $S$ 满载 $(50,50)$ 无法支撑 16 天行程（最坏热天需耗水 64、食 96，远超上限），必然中途枯竭。因此"位置"与"资源"必须联合成复合状态，使"能否到达"与"带多少资源到达"同时被刻画——这正是 RCSP 相较于普通最短路的本质区别。

最优子结构与非负权：每行动一天消耗固定、权为 1（非负），满足 Dijkstra 所需的三角不等式与最优子结构，故首次到达终点的距离即为全局最小天数，无需回溯剪枝。

五、求解结果

5.1 最优路线

最优路线共 18 天（16 个移动日 + 2 个休整日），依次经过：
$S(0,0)\to\cdots\to V_1(2,2)\ \text{(休整)}\to\cdots\to V_3(7,3)\ \text{(休整)}\to\cdots\to E(8,8)$
其中 $V_2(5,5)$ 因偏离最短走廊、且经由它不减少天数，未被最优路线采用——这说明在"最少天数"目标下，仅 $V_1,V_3$ 构成有效补给点。若改以"成本最低"为目标， $V_2$ 的单价更高（见第三篇），更不会被采用；唯有当 $V_1$ 或 $V_3$ 失效时， $V_2$ 才成为替补，体现补给点布局的冗余设计意义。

5.2 资源动态

图 2 给出水、食余量随天数的演化。起点满载 $(50,50)$ ；每段出发前于村庄补满，故每段起点均为 $(50,50)$ 。全程最低余量出现在第 18 天抵达 $E$ 时：水 29、食 17，均严格为正，证明路线在给定天气下绝对可行。

以 $V_1\to V_3$ 段为例：第 5 天于 $V_1$ 补满后出发，第 6—11 天依次经历凉、热、热、热、凉天气，食从 50 单调降至第 11 天的 17，恰好在抵达 $V_3$ 前触底；随后第 12 天于 $V_3$ 再次补满。这一"补满—单调消耗—临底补给"的锯齿形，正是资源受限行程的典型剖面，也直观说明每段长度是由"携带上限 ÷ 单日消耗"这一物理上限决定的。

5.3 天气与分段消耗

图 3 给出前 18 天天气预报（热/凉交替），图 4 给出三段行程的资源消耗：

$S\to V_1$ ：4 天，耗水 13、耗食 21；
$V_1\to V_3$ ：6 天，耗水 21、耗食 33；
$V_3\to E$ ：6 天，耗水 21、耗食 33。
各段消耗均未超过携带上限（单段最坏热天耗水 24、耗食 36，均 $<50$ ），故单段内即可被一次满载覆盖，无需段中增设补给。值得强调：分段消耗之和（水 $13+21+21=55$ 、食 $21+33+33=87$ ）远超单人次上限 50，说明全程必须依赖中途补给——这也正是本问题"看似可一步到位、实则必须分段接力"的根本难点。

六、结果分析

结构合理性：最优路线沿"先左上、再右下"的对角线走廊，仅在第 4 天、第 11 天于 $V_1,V_3$ 休整，符合"能用最少补给点覆盖最长无补给段"的直觉。
资源裕度：末段 $V_3\to E$ 长达 6 天、食耗 33，终点食余仅 17，说明该段已逼近携带能力边界——若天气更热或 $V_3$ 缺失，方案将不可行，凸显村庄布点的关键性。
图 6 以各段末余量进一步显示：食的裕度（17）明显小于水的裕度（29），因此食物是穿越的瓶颈资源，后续优化应优先保障食物。
休整点的"双刃剑"：每次休整虽能补满资源，却额外消耗 1 天。最优解仅在"不补给则下一段不可行"时才休整，体现了"天数—资源"的权衡：能用 2 次休整覆盖 3 段，正说明村庄布局恰好满足可行性阈值，再多设村庄不会进一步减少天数。
天气时序的影响：本预报中热天集中在第 8—10、13—14、17 天，恰好落在两段行程内部。由于每段起点皆补满，段内热天仅压低该段末余量，未引发跨段连锁短缺，说明"补满策略"对段内天气波动具有天然鲁棒性。

七、灵敏度讨论

携带上限 $W_{\max},F_{\max}$ ：若上限降至 40，则 $V_1\to V_3$ （食耗 33）仍可覆盖，但 $V_3\to E$ 6 天热天食耗 36 将越界，被迫在段中插入额外补给或改道，天数上升。
天气预报：本文用确定预报；若预报存在误差，则"装填量"需留缓冲，详见第二篇的天气不确定分析。
村庄可用性：若 $V_3$ 不可用时，须绕行 $V_2$ 或大幅增设备用补给，天数与风险同步上升。
网格规模扩展：当网格放大到 $20\times20$ 或更多村庄时，状态数按 $O(R\cdot C\cdot W_{\max}\cdot F_{\max})$ 增长；届时可采用标号法（label-correcting）或前沿搜索（A* 配合剩余资源启发式）控制规模，本篇的 Dijkstra 框架可直接迁移。
多目标前瞻：若同时优化"天数"与"补给成本"，则需在状态中追加累计费用维度，转化为标签型最短路（label-setting），这是第三篇方法的自然延伸。

八、模型优缺点

优点：状态定义直观、Dijkstra 保证最优、计算高效，可直接推广到更大网格与多资源；模型输出的是完整的"逐日位置—资源"轨迹，便于后续做天气不确定性与成本优化的联合分析。
缺点：当前以"天数最少"为唯一目标，未计采购成本；且假设队伍整体折算，未刻画成员间资源再分配；此外假定村庄补给瞬时完成（1 日补满），未建模补给排队或限额。这些在第三篇以费用为目标的函数中补齐，在第二篇以天气不确定性的鲁棒策略中部分缓解。

九、结论

将穿越沙漠抽象为资源受限最短路，可严格求得最优路线与最少天数。本例在给定地图与天气下得到 18 天、经 $V_1,V_3$ 两村补给 的可行最优方案，食物为瓶颈资源。该路线同时作为第二、三篇中"天气不确定"与"最小费用补给"的研究基准。

从工程视角看，本文方案给出了一个"刚够用"的临界补给计划：它在理想预报下零冗余、天数最少，但代价是对天气误差零容忍。这恰好引出后续两篇的核心议题——当预报不再完美时，应如何为路线注入缓冲（第二篇），以及如何在满足可行性的前提下把补给成本压到最低（第三篇）。三篇合起来构成"几何可行 → 鲁棒可行 → 经济可行"的完整决策链条。

附录：核心 Python 实现（可复现上述数字）

import heapq
ROWS,COLS=9,9; START=(0,0); END=(8,8)
VILLAGES={(2,2):1,(5,5):2,(7,3):3}
IMPASSABLE={(4,3),(3,4),(6,6)}
WCAP,FCAP=50,50
HOT=(4,6); COOL=(3,5)
NEIGH=[(1,0),(-1,0),(0,1),(0,-1)]
wx=[0,1,0,0,1,0,0,0,1,1,1,0,0,1,1,0,1,0]  # 前18天预报(0凉1热)
def cons(c): return HOT if c==1 else COOL
def solve():
    pq=[(0,0,START[0],START[1],WCAP,FCAP)]
    best={(START[0],START[1],WCAP,FCAP):0}
    parent={(START[0],START[1],WCAP,FCAP):None}
    goal=None
    while pq:
        d,_,r,c,w,f=heapq.heappop(pq)
        if best.get((r,c,w,f),1e9)<d: continue
        if (r,c)==END: goal=(r,c,w,f); break
        if (r,c) in VILLAGES:
            ns=(r,c,WCAP,FCAP)
            if d+1<best.get(ns,1e9):
                best[ns]=d+1; parent[ns]=((r,c,w,f),'rest',r,c)
                heapq.heappush(pq,(d+1,-len(parent),r,c,WCAP,FCAP))
        for dr,dc in NEIGH:
            nr,nc=r+dr,c+dc
            if not(0<=nr<ROWS and 0<=nc<COLS): continue
            if (nr,nc) in IMPASSABLE: continue
            if d>=len(wx): continue
            cw,cf=cons(wx[d]); nw,nf=w-cw,f-cf
            if nw<0 or nf<0: continue
            ns=(nr,nc,nw,nf)
            if d+1<best.get(ns,1e9):
                best[ns]=d+1; parent[ns]=((r,c,w,f),'move',nr,nc)
                heapq.heappush(pq,(d+1,-len(parent),nr,nc,nw,nf))
    seq=[]; k=goal
    while k is not None:
        seq.append(k); pk=parent.get(k)
        if pk is None: break
        k=pk[0]
    seq.reverse()
    wmin=min(s[2] for s in seq); fmin=min(s[3] for s in seq)
    wmax=max(s[2] for s in seq); fmax=max(s[3] for s in seq)
    print("days=",len(seq)-1)
    print("route=",[(s[0],s[1]) for s in seq])
    print("water[min,max]=",wmin,wmax," food[min,max]=",fmin,fmax)
solve()

运行输出：days=18，water[min,max]= 29 50，food[min,max]= 17 50，与正文一致。

图1 沙漠地图与最优路线
图2 资源余量随天数变化
图3 前18天天气预报
图4 各段资源消耗
图5 补给点与行程节点
图6 各段末资源余量
图7 模型求解流程
图8 方案综合评估雷达