一种基于动态规划和深度学习的沙漠穿越策略模型

发表于 2025/03/30

作者 Dignite

・・ 49 分钟阅读

摘要

本文通过动态规划的一般编程方法，分析了在固定天气和地图的情况下的最佳的采矿和移动策略。此外，我们还将通过人工智能深度学习来探寻该问题的一般策略，以直观深入地探寻各影响因子之间的关联。

关键词

动态规划图论最短路 **数学模型 策略问题深度学习神经网络 **算法

1 问题背景

1.1 基本规则

以天为基本时间单位，游戏的开始时间为第 0 天，玩家位于起点。玩家必须在截止日期或之前到达终点，到达终点后该玩家的游戏结束。
穿越沙漠需水和食物两种资源，它们的最小计量单位均为箱。每天玩家拥有的水和食物质量之和不能超过负重上限。若未到达终点而水或食物已耗尽，视为游戏失败。
每天的天气为“晴朗”、“高温”、“沙暴”三种状况之一，沙漠中所有区域的天气相同。
每天玩家可从地图中的某个区域到达与之相邻的另一个区域，也可在原地停留。沙暴日必须在原地停留。
玩家在原地停留一天消耗的资源数量称为基础消耗量，行走一天消耗的资源数量为基础消耗量的 2 倍。
玩家在第 0 天可在起点处用初始资金以基准价格购买水和食物。玩家可在起点停留或回到起点，但不能多次在起点购买资源。玩家到达终点后可退回剩余的水和食物，每箱退回价格为基准价格的一半。
玩家在矿山停留时，可通过挖矿获得资金，挖矿一天获得的资金量称为基础收益。如果挖矿，消耗的资源数量为基础消耗量的 3 倍；如果不挖矿，消耗的资源数量为基础消耗量。到达矿山当天不能挖矿。沙暴日也可挖矿。
玩家经过或在村庄停留时可用剩余的初始资金或挖矿获得的资金随时购买水和食物，每箱价格为基准价格的 2 倍。

1.2 具体安排

通过对问题的粗略分析，得到了有关采矿，行动，物资补充等的大致策略；
以 C++ 语言为载体，使用动态规划等算法实现最佳策略，计算出具体的策略与最大资金；
通过强化学习等人工智能算法，实现了在事先不知道最佳策略的情况下，通过大量数据积累分析隐藏规律，得出局部最优解；
对比两个解决方案得出最终答案；
分析对比两个解决方法的优缺点，且对于非固定地图的策略进行讨论。

2 问题分析

首先，根据对题意的理解，我们可以将问题策略大致分为以下两类：不采矿和采矿。并对这两种情况分别进行讨论。

对于不采矿的情况，由于本题中由起点到达终点可不经村庄，我们可以将问题简化为最优路径求解问题，即找到经过区域数最小的抵达方案，以实现用最少天数到达终点从而节省资金，在本文中我们使用 Dijkstra **算法[1]实现。**

对于采矿的情况，最后的资金数由采矿天数、采购资源方案、行动路径选择等多种因素决定，因此我们使用动态规划算法和强化学习来计算最佳策略并减少由于贪心导致无法全局最优的情况。

此外，由于退回资源价格为基准价格的一半且资源只能通过购买获得，在实现最优时应实现不退回资源，同理可知，在村庄应减少购买资源以节省资金。

3 方案实现

3.1 状态建立

为了求解最优策略，首先需要对游戏的状态进行建模。

用四个维度表示状态：天数、位置、水、食物。我们不妨令 dp_{day,\ position,\ water,\ food}表示在第day天、处于 position号节点、剩余有water量的水和food量的食物时，所能拥有的最大资金数。为了方便最终输出结果，我们不妨设定fr_{day,\ position,\ water,\ food}表示在第day天、处于 position号节点、剩余有water量的水和food量的食物、且剩余资金取到最大值的方案时，其前一步骤所在的day,\ position,\ water,\ food的状态。由此我们可以得到以下数组：

dp[day][position][water][food]; //这个数组表示当前的状态
fr[day][position][water][food]; //这个数组表示上次的状态，用于回溯

3.2 图的构建与最短路

地图是一个无向图。我们考虑到，关键节点只有起点、终点、村庄、矿山。容易知道：

我们只需在四点间走动；
我们需要走四点间的最短路，一旦走远了，将会增加装备消耗。

因此，求解问题的第一步，需要我们预处理整张图该四个节点两两之间的最短路，以简化整个问题，亦方便了后续计算。

我们不妨考虑这样的图：

其中，加粗点为关键节点。别看这个图看上去很复杂，其实我们真正能用到的有效路径是这样：

此时就需要我们用到 Dijkstra[^{[1]}](#) 算法预处理最短路和最短路径。相关过程如下：

Dijkstra(图, 源节点):
    对图中每个顶点 v 做如下操作:
        dist[v] = ∞  // 设置所有节点的距离为无穷大
        prev[v] = null  // 记录最短路径的前驱节点
    dist[源节点] = 0  // 源节点的距离为 0
    Q = 优先队列，包含图中的所有顶点


    当 Q 不为空时:
        u = Q 中距离最小的顶点
        从 Q 中移除 u


        对 u 的每个邻居 v 做如下操作:
            alt = dist[u] + 边长(u, v)
            如果 alt < dist[v]:
                dist[v] = alt
                prev[v] = u
                更新 v 在 Q 中的优先级


    返回 dist, prev

**该算法的基本思想是从源节点开始，逐步扩展到其它节点，并不断更新从源节点到各个节点的最短距离。具体来说，算法首先将图中每个顶点的距离（记为 **dist）初始化为无穷大，并将其前驱节点（记为 prev）设置为空；源节点的距离被初始化为 0。接着，所有顶点被置于一个优先队列（Q）中，该队列按照顶点到源节点的当前最短距离进行排序。

**在主循环中，只要优先队列 Q 非空，便选出距离最小的顶点 **u，并将其从队列中移除。然后，对 u 的每个邻接点 v，计算经过 u 到 v 的候选路径长度 alt = dist[u] + 边长(u, v)。若该候选长度小于当前记录的 dist[v]，则更新 dist[v] 为 alt，并设置 prev[v] = u。同时，更新顶点 v 在优先队列中的优先级，使得队列始终保持按最短距离排序的状态。最终，当所有节点均已被访问，算法返回每个节点到源节点的最短距离（dist）以及构成最短路径的前驱信息（prev）。

下图展示了算法的基本过程：从源节点开始，优先选择当前距离源节点最近的节点进行松弛操作，不断“扩散”到图中的其他节点，直至所有节点的最短路径确定。对于每一次距离更新，我们称之为一次“松弛”操作。

现在，我们已经成功得到了两点间的最短路。

3.3 动态规划之状态转移方程

状态转移方程作为动态规划算法[2]中最重要的部分，承担了有效率地寻找最佳策略的任务。

**状态转移的思路是，对于每一个当前状态 **dp[i][j][k][l]，我们枚举所有可能的下一步行动，计算出新的状态，并更新 dp 数组。具体来说，有以下几种转移情况：

3.3.1 原地停留

如果当前天气不是沙暴，玩家可以选择在当前地点停留一天。这种情况下，地点不变，消耗当天的水和食物（消耗量取决于天气），金钱数不变。

如果 今天天气不是沙暴:
    新水 = 当前水 - 当天耗水
    新食物 = 当前食物 - 当天耗粮
    如果 新水 >= 0 且 新食物 >= 0:
        dp[下一天][当前地点][新水][新食物] = max(dp[下一天][当前地点][新水][新食物], 当前金钱)

即：

\begin{cases} w_{new} = w_{cur} - w \\ f_{new} = f_{cur} - f \\ \text{if } w_{new} \ge 0 \text{ and } f_{new} \ge 0: \\ \quad dp[d+1][j][w_{new}][f_{new}] = \max(dp[d+1][j][w_{new}][f_{new}], m_{cur}) \end{cases}

其中，w 和 f 分别表示当天消耗的水和食物数量。

3.3.2 移动到相邻地点

如果今天天气不是沙暴，旅行者可以移动到与当前地点相邻的地点。这种情况下，需要消耗双倍的水和食物，金钱数不变。

如果 今天天气不是沙暴:
    对于 当前地点的每一个相邻地点 next_j:
        新水 = 当前水 - 2 * 当天耗水
        新食物 = 当前食物 - 2 * 当天耗粮
        如果 新水 >= 0 且 新食物 >= 0:
            dp[下一天][next_j][新水][新食物] = max(dp[下一天][next_j][新水][新食物], 当前金钱)
用公式表达：

即有：

\begin{cases} \text{for each } next\_j \in \text{Adjacent}(j): \\ \quad w_{new} = w_{cur} - 2w \\ \quad f_{new} = f_{cur} - 2f \\ \quad \text{if } w_{new} \ge 0 \text{ and } f_{new} \ge 0: \\ \qquad dp[d+1][next\_j][w_{new}][f_{new}] = \max(dp[d+1][next\_j][w_{new}][f_{new}], m_{cur}) \end{cases}

3.3.3 在矿山工作

**如果当前地点是矿山，旅行者可以选择在矿山工作一天。这种情况下，消耗三倍的水和食物，但金钱数会相应增加。 **

如果 当前地点是矿山:
    新水 = 当前水 - 3 * 当天耗水
    新食物 = 当前食物 - 3 * 当天耗粮
    如果 新水 >= 0 且 新食物 >= 0:
        dp[下一天][矿山][新水][新食物] = max(dp[下一天][矿山][新水][新食物], 当前金钱 + 矿山收入)

用公式表达：

\begin{cases} w_{new} = w_{cur} - 3w \\ f_{new} = f_{cur} - 3f \\ \text{if } w_{new} \ge 0 \text{ and } f_{new} \ge 0: \\ \quad dp[d+1][j][w_{new}][f_{new}] = \max(dp[d+1][j][w_{new}][f_{new}], m_{cur} + income) \end{cases}

3.3.4 在村庄补给

如果当前地点是村庄，旅行者可以选择购买水或食物。购买补给不会消耗天数。

如果 当前地点是村庄:
    // 购买水
    新金钱 = 当前金钱 - 买水花费
    如果 新金钱 >= 0:
        dp[当天][村庄][当前水 + 购买水量][当前食物] = max(dp[当天][村庄][当前水 + 购买水量][当前食物], 新金钱)
// 购买食物
新金钱 = 当前金钱 - 买食物花费
如果 新金钱 >= 0:
    dp[当天][村庄][当前水][当前食物 + 购买食物量] = max(dp[当天][村庄][当前水][当前食物 + 购买食物量], 新金钱)

即有：

购买水：

\begin{cases} m_{new} = m_{cur} - cost_w \\ \text{if } m_{new} \ge 0: \\ \quad dp[d][j][w_{cur} + buy\_w][f_{cur}] = \max(dp[d][j][w_{cur} + buy\_w][f_{cur}], m_{new}) \end{cases}

购买食物:

\begin{cases} m_{new} = m_{cur} - cost_f \\ \text{if } m_{new} \ge 0: \\ \quad dp[d][j][w_{cur}][f_{cur} + buy\_f] = \max(dp[d][j][w_{cur}][f_{cur} + buy\_f], m_{new}) \end{cases}

3.3.5 方程总结

将上述所有情况总结成一个公式：

dp[i][j][k][l] = \begin{cases} C - 5k - 10l, & \text{if } i = 0, j = 1 \\ \max(dp[i][j][k][l], dp[i-1][j][k + w][l + f]), & \text{if } sta[i] \ne 2 \\ \max(dp[i][j][k][l], dp[i-1][x][k + 2w][l + 2f]), & \text{if } sta[i] \ne 2, \forall x \in e[j] \\ \max(dp[i][j][k][l], dp[i-1][j][k + 3w][l + 3f] - CC), & \text{if } j = \text{mine\_id} \\ \max(dp[i][j][k][l], dp[i][j][k-1][l] + 10), & \text{if } j = \text{village\_id} \\ \max(dp[i][j][k][l], dp[i][j][k][l-1] + 20), & \text{if } j = \text{village\_id} \\ -1, & \text{otherwise} \end{cases}

** 其中：**

w = wat[sta[i]], f = fod[sta[i]]，表示当天消耗的水和食物。
e[j] 表示与地点 j 相邻的地点集合。
\text{mine\_id} 和 \text{village\_id} 分别表示矿山和村庄的编号。
CC = 1000，表示在矿山工作的收入。
C=10000表示初始金钱。
该公式中的max操作，表示在满足对应条件的所有可能转移中，取金钱数最大的那个状态。如果所有转移都不合法（例如资源不足），则 dp 值保持为 -1。
该公式中每一项和代码中的chk函数调用一一对应。

3.3.5 代码实现

for (short i = 0; i <= M; i++)
{
	short st = sta[i + 1], w = wat[sta[i + 1]], f = fod[sta[i + 1]];
}

最外层循环从第一天开始模拟，并记录资源基础消耗量。接下来的三层循环，分别遍历在这一天内每个区域可能的决策、这一天内每种剩余水量可能的决策、这一天内每种剩余食物量可能的决策。

对于我们遍历到的这些情况，我们先用 **`if (short q = dp[i][j][k][l]; q >= 0 && k * 3 + l * 2 <= N) 和 if (c < 0 || d < 0 || e < 0 || c * 3 + d * 2 > N)` 条件判断对其进行筛选，排除掉不符合题意的情况（如负重过大）**。

if (x < e)
	x = e, fr[a][b][c][d] = {i, j, k, l};

用这个语句选出剩余资金最大的情况：

if (j == end_id && q > ans)
	ans = max(ans, q), aa = i, bb = j, cc = k, dd = l;

如果已经到达终点，那么将剩余资金数进行比较，找出更优的策略：

if (i == M)
	continue;

如果已经是最后一天，那么不需要继续模拟沙漠穿越过程：

chk(i + 1, j, k - w, l - f, q);

对于停留在原地并不进行任何操作，我们将参数减去资源消耗量后继续：

if (st != 2)
	for (short x : e[j])
		chk(i + 1, x, k - w - w, l - f - f, q);

对于非沙暴天，我们将参数减去两倍资源消耗量后继续：

if (j == mine_id)
{
	chk(i + 1, j, k - w - w - w, l - f - f - f, q + CC);
}

如果在矿山，我们可以进行挖矿操作，我们将参数减去三倍资源消耗量并将剩余资金数加上基础收益后继续：

if (j == village_id)
	chk(i, j, k + 1, l, q - 10), chk(i, j, k, l + 1, q - 20);

如果在村庄，我们可以进行买水、买食物操作，同时因为天数参数 i 并没有加一我们可以保证每一种购买方案均得到考虑，我们将参数减去资金消耗量并加上购买资源量后继续。

完整代码详见 ** final.cpp 。其余代码为答案及详细方案输出，由于与算法无太大关系我们不作赘述。**

4 深度学习

在已经通过一般编程方法实现该问题后，我们进一步探索该问题的一般情况，即改变题设各参数与图。我们针对具有多场景决策需求的数据（包括村庄、路上、矿山三种场景），提出了一种基于深度学习的多任务决策模型构建方法。不同于传统仅依赖当前时刻数据的模型，我们通过构造滑动窗口（前 5 步和后 5 步，总共 11 步）以捕捉更丰富的时序信息，并引入多头自注意力机制，对窗口内信息进行融合建模。实验结果表明，该方法在决策预测（如资源采购、前进与否、挖矿与否）上具有更高的鲁棒性和准确性。

与近期热门技术深度学习结合，我们不难得到以下思路：

随机生成大量参数；
通过已经完成的一般程序，得到对应结果（即参数-结果对）；
把上述数据喂给模型，训练其解决该类问题；
由此得到经过训练的模型。

我们明确一下模型的任务：

输入参数：位置、天气、剩余天数、剩余资金、剩余食物量、剩余水量。
要求预测：买水量、买食物量、前进与否、挖矿与否。

我们进行深度学习的目的有：

人类在游戏过程中无法像计算机一样进行精密的计算，我们需要通过分析各个参数对决策影响的趋势，得出普遍性的指导意义。
通过深度学习，推广策略模型到更广泛的情况上。
分析各参数的趋势，深入理解该数学模型的内在影响与关联性。

4.1 模型建立

在资源采集与行进决策问题中，不同场景下的决策往往依赖于当前状态以及前后时刻的信息，而在实际应用中，前后状态信息往往能够提供更丰富的背景和趋势信息。为此，我们提出一种基于滑动窗口和多头自注意力机制的模型架构，并针对不同场景（村庄、路上、矿山）设计了专用决策模型：

村庄场景：预测买水量、买食物量（回归任务）以及是否前进（分类任务）。
路上场景：仅预测是否前进（分类任务）。
矿山场景：同时预测是否前进和是否挖矿（均为分类任务）。

4.2 输入数据的生成

为简化问题，我们不妨规定和题设一样的条件，即：起点位于 1，终点位于 27，村庄位于 15，矿山位于 12。此外，每天的天气状况也与题设保持一致。为了使生成数据覆盖尽可能多的情况，我们使用随机方法来生成不同的图。然而，并非任意生成的图都能满足较好机器学习的条件。具体地，我们需要保证在起点、终点、村庄、矿山任意两点之间都有一条通路，这样才能有效地对神经网络进行训练。

此外，我们还需讨论生成数据的规模。对于数据范围，我们需要确保节点数在 27 个以内。这是由于程序内存本身的限制，更是考虑到真正有效的关键节点仅有起点、终点、村庄、矿山四处。其他节点均为过程节点，无法进行丰富的操作。对于数据数量，也并非多多益善。仅在 27 个点之间生成合理的图无法形成无穷多种情况，如果数据数量过多，则会造成过拟合的情况，过犹不及。最终，我们决定生成 30000 张图，共约 740000 条决策记录。

4.3 生成输出结果

我们使用前几节中完成的代码计算最优结果。为了输出结构化数据，我们需要对输出格式稍加修改。我们选择使用 **csv 格式[3]储存大量数据，这是一种被推荐的数据格式。为了提供上文所述的详细信息，我们需要根据规则计算出买水量、买食物量、前进与否、挖矿与否。**

接着，我们使用 Python 多线程调用程序运行结果以生成输出。最后，我们将零散的 csv 输出进行合并。最终，我们得到的 csv 数据集的格式示例如下：

数据存储于 csv 文件中，格式示例如下：

位置,天气,剩余天数,剩余资金,剩余食物量,剩余水量,买水量,买食物量,前进与否,挖矿与否
路上,高温,30,6335,250,233,8,6,0,0
矿山,高温,29,6335,238,217,9,7,1,0
矿山,高温,28,7335,220,193,9,7,0,1
晴朗,高温,27,8335,199,178,9,7,0,1
...

4.4 模型训练

4.4.1 特征分类

我们需要对以下预测值进行分类：

类别特征：（位置、天气）使用 One-Hot编码。
数值特征：（剩余天数、剩余资金、剩余食物量、剩余水量）经过标准化处理。
将类别和数值特征拼接，形成最终的输入矩阵。

4.4.2 滑动窗口

不仅如此，为充分利用时序信息，我们还需设计滑动窗口构造函数。对于每个数据样本：

提取前 5 步与后 5 步共 11 步的信息；
对于边界不足部分，采用边缘复制策略；
**生成的窗口数据形状为 **(11, d)，其中 d 为特征维度。

4.4.3 注意力子网络

为了有效整合窗口内的上下文信息，本文在基础网络中引入了多头自注意力层。该层能够对窗口内所有时刻的信息进行建模，并通过残差连接和层归一化得到鲁棒的特征表示，最终提取当前时刻（窗口中间）的特征作为预测依据。

由于我们具有三种不同时态的特征预测模式，即“村庄模型”“路上模型”和“矿山模型”。

数据解基于注意力骨干网络，设计不同场景的决策模型：

村庄模型：输出包含回归分支（买水量、买食物量）与分类分支（是否前进）。
路上模型：仅输出前进与否（二分类）。
矿山模型：同时输出前进与否与挖矿与否（二分类）。

最后，我们基于预处理和滑动窗口数据，对三个场景分别构造训练集与验证集。训练过程中利用 GPU 加速，并保存训练好的模型。

此外，我们还对训练结果进行了测试，达到的效果非常可观：

276/276 ━━━━━━━━━━━━━━━━━━━━ 2s 3ms/step - buy_food_loss: 4.4697 - buy_water_loss: 1.3148 - loss: 5.7847 - move_forward_loss: 5.0175e-10
Village Model Test Loss: [6.1254167556762695, 1.2825570106506348, 4.82736873626709, 5.117979817725882e-09]
1046/1046 ━━━━━━━━━━━━━━━━━━━━ 3s 3ms/step - loss: 5.9283e-05
Road Model Test Loss: 6.833732913946733e-05
3316/3316 ━━━━━━━━━━━━━━━━━━━━ 10s 3ms/step - loss: 3.6904e-04 - mine_loss: 1.8531e-04 - move_forward_loss: 1.8373e-04
Mine Model Test Loss: [0.00018224114319309592, 9.079145092982799e-05, 9.143214992946014e-05]

5 数据解释

在成功训练完上述模型后，我们尝试导出其中的模型层参量，并且通过绘制图表，来展示相关参数对最终决策的影响。

我们另外创建了一份用于绘制图表的代码。在份代码中，我们使用 Python 的相关扩展库来展示如何直观地理解神经网络模型的预测行为。具体来说，我们构造了一个“滑动窗口”数据结构，即由多个相同数据行组成的矩阵，其中某一行（位于窗口的中心）会依次改变一个特定的数值特征。通过这种方法，我们可以观察到随着该特征取值的变化，模型预测结果（例如买水量、是否前进等）的变化趋势。整体思路类似于数学中讨论函数图像如何随自变量变化而变化，能够让我们直观地看到输入参数对函数输出的影响。这样的可视化不仅帮助我们验证模型的稳定性，也使复杂的深度学习模型变得更加透明和易于理解。

5.1 村庄模型

村庄模型阐述的是：当玩家在村庄时，进行购买行为的决策。

5.1.1 剩余天数的影响

由图表可以看出：

当剩余天数在一半日程（即 15天）之前，买水的行为一直保持较高水平，且还在小范围升高；但是时间一来到后 15天，购买水的行为急剧下降。这可能是因为挖矿者在前期需要做好充足的准备，而在后期进行“冲刺”，无需买水。
对于买食物，不难发现，在游戏前期该需求较低，直到接近第 15天时，该需求上升至顶点，在后期下降并保持一定的水这当然也可能与村庄的位置有关，因为村庄大约出现在路程的中途处。

5.1.2 剩余资金的影响

由图表可以看出：

当剩余资金充足时，购买水的行为呈现下降趋势，表明玩家更倾向于提前储备水资源以应对长途消耗。但当资金短缺时，购买量却上升，可能因为此时资金需优先用于应急物资。
对于购买食物，图表显示出了类似的趋势，但是总体购买行为比水稍弱些。这说明了水可能在游戏中发挥了更为重要的作用。

5.1.3 剩余食物的影响

由图表可以看出：

当剩余食物充足时，购买水的量先增加后减少，呈现出一种储备行为。但在食物短缺时，购买水的量持续增加，表明在食物不足的紧急情况下，玩家依然会选择购买水，说明水的重要性。
当剩余食物充足时，购买食物的量迅速增加并达到饱和。而在食物短缺时，购买食物的量很低，说明玩家在食物极度缺乏时会优先考虑其他策略，而非购买食物。
** 随着剩余食物的减少, 前进的概率逐步下降, 当食物极度缺乏时, 前进的概率接近于0。但这其实是因为食物不足无法前进了（规则限制）。**

综合来看，该图表揭示了一个生存策略：在资源充足时，玩家倾向于平衡购买水和食物，并积极前进。但在资源匮乏时，水的优先级高于食物，且玩家会减少前进以保存资源。这是因为在游戏设定中，缺水比缺食物更加致命，而停止前进可以减少消耗。

5.1.4 剩余水量的影响

由图表可以看出：

当剩余水量充足时，购买水的量迅速增加并趋于稳定。但在剩余水量短缺时，购买水的量接近于0，说明在极度缺水的情况下，玩家可能没有资源购买水，或者优先考虑其他生存策略。
当剩余水量非常充足的时候，玩家倾向于不买食物，说明食物的优先级比较低。只有当剩余水量减少到一个阈值以下时，玩家才开始大量购买食物。这可能是因为食物可以用来回复体力。
随着剩余水量的减少，前进的概率逐步下降。当剩余水量极度缺乏时，前进的概率接近于0。这与之前的图表结论一致，即缺水会严重限制玩家的前进。

5.2 路上模型

路上模型阐述的是玩家在路上时是否要前进的决策。

5.2.1 剩余食物的影响

由图表可以看出：

整体趋势： 前进概率随着剩余食物的增加先快速上升，然后趋于平稳，最后略有下降。呈现一个倒U型。
上升阶段（食物匮乏）： 当剩余食物非常少时，前进概率随食物增加而迅速增加。这表明在食物极度缺乏的情况下，少量食物的增加对产出有显著的正面影响。
平稳阶段（食物充足）： 当剩余食物量处于中间范围时，前进概率基本保持稳定，并达到最大值。说明食物供应充足保障了产出。
下降阶段（食物过剩）： 当剩余食物非常多时，前进概率略有下降。

5.2.2 剩余水量的影响

由图表可以看出：

整体趋势： 当剩余水量较少时，前进概率维持在一个很高的恒定值。但随着剩余水量增加，产出呈现阶梯式下降。
恒定高产出区：当剩余水量较少时，玩家会保持前进。
阶梯式下降： 随着剩余水量增加，前进概率出现几次明显的下降。每次下降都形成一个平台期, 说明达到某些特定的水量阈值后, 前进的概率会降低。

5.3 矿山模型

矿山模型阐释的是，当玩家在矿山时，到底要停留下来挖矿还是继续前进的决策。

5.3.1 剩余天数的影响

由图表可以看出：

U型曲线： 前进的概率随着剩余天数的变化呈现一个U型曲线。在剩余天数非常多或者非常少的时候，前进的概率都较高；而在剩余天数处于中间值时，前进的概率最低。
时间充裕阶段： 当剩余天数非常多时（图表左侧），前进概率较高。这可能表明在时间充裕的情况下，玩家更倾向于探索或前往下一个目标。
时间紧迫阶段： 当剩余天数非常少时（图表右侧），前进概率也较高。这说明在时间紧迫的情况下，玩家被迫前进以完成目标。
中间阶段：在游戏时间中期，玩家有充足的时间，可以选择暂时不前进。

5.3.2 剩余资金的影响

由上图可以看出：

当剩余资金非常少时，前进概率迅速下降并接近于0。资金充足时，玩家有概率前进。
当剩余资金非常少时，采矿概率迅速增加并接近于1。资金充足时，玩家几乎必定采矿。

6 问题解答

6.1 方案表

日期	所在区域	剩余资金数	剩余水量	剩余食物量
0	1	5780	178	333
1	25	5780	162	321
2	24	5780	146	309
3	23	5780	136	295
4	23	5780	126	285
5	22	5780	116	271
6	9	5780	100	259
7	9	5780	90	249
8	15	4150	243	235
9	14	4150	227	223
10	12	4150	211	211
11	12	5150	181	181
12	12	6150	157	163
13	12	7150	142	142
14	12	8150	118	124
15	12	9150	94	106
16	12	10150	70	88
17	12	10150	60	78
18	12	10150	50	68
19	12	11150	26	50
20	14	11150	10	38
21	15	10470	36	40
22	9	10470	26	26
23	21	10470	16	12
24	27	10470	0	0
25	27	10470	0	0
26	27	10470	0	0
27	27	10470	0	0
28	27	10470	0	0
29	27	10470	0	0
30	27	10470	0	0

6.2 一般策略

6.2.1 核心原则

水 > 食物： 优先保证水的充足。
时间管理： 早期、晚期多前进，中期看情况。
资金 = 水 > 食物, 用于挖矿: 资金主要用于水和食物，在矿山尽量挖矿。

6.2.2 策略要点

早期（>15天）： 前进，村庄多买水，少量食物。
中期（≈15天）： 村庄补给，食物需求增加，保持水储备，有矿就挖。
后期（<15天）： 冲刺，少买东西，控资源，时间紧就别挖矿。
路上： 食物/水充足可前进，极度缺乏则停止。
村庄: 根据资源情况补给。
矿山： 时间多/钱少就挖，时间少/钱多就走。

7 反思

动态规划和深度学习在解决沙漠穿越问题时展现出不同的优势和局限。动态规划能够求得严格的最优解，并且不需要进行训练，但它容易遭遇维度灾难，扩展性较差，同时高度依赖完整的先验信息。这使得动态规划更适合于那些参数稳定、场景相对简单的任务。

相比之下，深度学习展现出更强的泛化能力，可以进行实时决策，并且能够处理变量之间复杂的非线性关系。然而，深度学习存在陷入局部最优解的风险，需要大量的训练数据，并且模型的可解释性相对较弱。因此，深度学习更适用于那些环境复杂、动态变化且需要快速做出适应性决策的场景。未来的研究方向包括结合两种方法的优点，例如混合策略、模型轻量化、动态地图优化以及引入灾害预警机制，从而为复杂的路径规划问题提供更全面和高效的解决方案。

8 引用

**[1] **图论：Dijkstra算法——最详细的分析，图文并茂，一次看懂！-CSDN博客

**[2] **Reinforcement Learning-based Heuristics to Guide Domain-Independent Dynamic Programming

**[3] **Mapping Large Scale Research Metadata to Linked Data: A Performance Comparison of HBase, CSV and XML

9 鸣谢

感谢人工智能实验室的服务器为我们提供计算资源。

笔记本, 数学

数学建模学习

本文由作者按照 CC BY 4.0 进行授权

摘要

关键词

1 问题背景

1.1 基本规则

1.2 具体安排

2 问题分析

3 方案实现

3.1 **状态建立**

**3.2 **图的构建与最短路

3.3 动态规划之状态转移方程

3.3.1 原地停留

3.3.2 移动到相邻地点

3.3.3 在矿山工作

3.3.4 在村庄补给

3.3.5 方程总结

3.3.5 代码实现

4 深度学习

4.1 模型建立

4.2 输入数据的生成

4.3 生成输出结果

4.4 模型训练

4.4.1 特征分类

4.4.2 滑动窗口

4.4.3 注意力子网络

5 数据解释

5.1 村庄模型

5.1.1 剩余天数的影响

5.1.2 剩余资金的影响

5.1.3 剩余食物的影响

5.1.4 剩余水量的影响

5.2 路上模型

5.2.1 剩余食物的影响

5.2.2 剩余水量的影响

5.3 矿山模型

5.3.1 剩余天数的影响

5.3.2 剩余资金的影响

6 问题解答

6.1 方案表

6.2 一般策略

6.2.1 核心原则

6.2.2 策略要点

7 反思

8 引用

9 鸣谢

热门标签

3.1 状态建立

3.2 图的构建与最短路