基于Bellman- Ford 算法的穿越沙漠策略研究

臧 洋 师 艳 景港澳 陈萌琪 赵 怡

（1、兰州理工大学土木工程学院，甘肃 兰州730050 2、兰州理工大学理学院，甘肃 兰州730050 3、兰州理工大学材料科学与工程学院，甘肃 兰州730050 4、湖北汽车工业学院，湖北 十堰442000）

玩家凭借一张地图，利用初始资金购买一定数量的水和食物（包括食品和其他日常用品），从起点出发，在沙漠中行走。途中会遇到不同的天气，也可在矿山、村庄补充资金或资源，目标是在规定时间内到达终点，并保留尽可能多的资金。游戏开始的时间为第0 天，玩家位于起点。玩家必须在截止日期或之前到达终点，到达终点后该玩家的戏结束。穿越沙漠需水和食物两种资源，每天玩家拥有的水和食物质量之和不能超过负重上限。玩家在矿山停留时，可通过挖矿获得资金，挖矿一天获得的资金量称为基础收益。玩家经过或在村庄停留时可用剩余的初始资金或挖矿获得的资金随时购买水和食物，若未到达终点而水或食物已耗尽，视为游戏失败。

1 问题分析

假设只有一名玩家，在整个游戏时段内每天天气状况事先全部已知，第一关和第二关路线全部分设定为经过矿山和村庄以及不经过矿山和村庄这两种路线进行建模，两者结合更加科学合理的帮助玩家穿越沙漠以及得到最大资金，规划以最短流程经过矿山和村庄以及停留矿山最久时间，所达到资金最大化，同时又保证食物充足以及在30 天内完成。我们分别从玩家路线一致且经过矿山的情况和不经过矿山的情况以及玩家路线不一致经过或不经过矿山的情况进行对比分析，最终确定两名玩家路线不一致时，且不经过矿山，该路线是最优策略。我们基于所计算的最短路线的基础上分别考虑了晴朗天气和高温天气的所有情况，最终得到在不经过矿山的最短路线为，且全是晴天的情况下，达到终点的最佳收益最高为9670 元，该路线为最优策略。

2 模型的建立与求解

我们通过对路线实际情况的分析，把两种情况路线全部分为经过矿山和村庄以及不经过矿山和村庄两种路线进行建模，两者结合进行比较更加科学合理的确定玩家穿模沙漠的最佳策略。初始化：将除源点外的所有顶点的最优距离估计值：d[v]←+∞，d[s]←0。分布式迭代求解:反复对边集E 中的每条边进行松弛操作，使得顶点集V 中的每个顶点v 的最优距离估计值逐步接近其最优距离（运行v-1 次）。检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v 的最优距离保存在d[v]中。[2]我们先假设不经过矿山和村庄，最短时间到达终点时在穿越沙漠中水和食物最小消耗量以及剩余的的资金总和，利用Matlab 建立模型并绘图。

以经过矿山和村庄建立模型，规划以最短路径经过矿山和村庄以及停留矿山最久时间，所达到资金的最大化，同时又保证食物充足以及在截止日期30 天内完成，根据Bellman-Ford算法得出从起点到达矿山的最近距离，以及得到从矿山出发到达终点的最短路线，找到最小损耗路线。

通过建立目标函数和约束条件，得出线性规划问题，最终通过求解线性规划问题，得到每种情况的最优策略。线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件可以是不等式也可以是等式，变量可以有非负要求也可以没有非负要求。为了避免这种由于形式多样性而带来的不便，规定线性规划问题的标准型为[3]：

线性规划的标准形式要求目标函数最小化，约束条件取等式，变量非负。由于题目所给玩家数量确定，所以该问题间接转化成定量分析讨论，其规则是若某天其中的任意k（2燮k燮n）名玩家均从区域A 行走到区域B（B≠A），则他们中的任一位消耗的资源数量均为基础消耗量的2k 倍；n=2，则有2 名玩家，由题意可知2 人是一同行动的。所以他们每人平均基础消耗量为一人（单独行动）的2 倍。在两种方案的条件下进行路线规划，分别分为：从起点出发到达矿山，然后从矿山到达终点的最短路径（此时不考虑在矿山的停留时间）；从起点出发不经过矿山直达终点的最短路径。在最短路线的基础上考虑天气状况和玩家路线是否重合，从而确定最佳收益路线。对于天气状况已知，排除考虑，我们分别从玩家路线一致且经过矿山的情况和不经过矿山的情况以及玩家路线不一致经过或不经过矿山的情况进行对比分析，最终确定两名玩家路线不一致时，且不经过矿山，该路线是最优策略。由于每名玩家仅知道当天的天气状况，因此我们考虑建立时间序列模型，做出三十天的天气预测，并结合Bellman-Ford 算法与不同方案进行迭代，得到最优路线策略。经典的时间序列模型包括移动平均模型、自回归模型、自回归移动平均模型。假设xt表示t 时刻的时间序列的值，q 表示时间窗的大小，εt表示t 时刻的白噪声，

注意到对于ARMA 模型，当权重系数β1，…，βq全为0时，其可以被看作一个AR 模型[4]。因为MA，AR 和ARMA 都具有弱平稳性，其均值和协方差都不取决于t，即：E（Xt）=μ，cov（Xt，Xt+k）=E（Xt-u）（Xt+k-u）=γk，k∈Z 分别做出了四种情况下的最短路线：第一种情况是在不经过矿山情况下最短路径为路线11（此时视为两名玩家路线一致），第二种情况是经过矿山的最短路径是路线12（此时视为两名玩家路线一致），第三种情况是两名玩家路线均不一致经过矿山到达终点最短路径13，第四种情况是两名玩家路线均不一致不经过矿山到达终点最短路径是14。

根据建立的模型，分别假设经过矿山和村庄及不经过矿山和村庄这两种不同的假设确定两条最短路线（不考虑停留情况），在这两条的最短路线的基础上同时考虑天气情况和挖矿停留时间。因为玩家仅知道当天的天气状况，只能据此决定当天的行动方案。游戏条件不考虑沙暴，我们基于所计算的最短路线的基础上分别考虑了晴朗天气和高温天气的所有情况，最终得到在不经过矿山的最短路线为，且全是晴天的情况下，达到终点的最佳收益最高为9670 元，该路线为最优策略。考虑到沙暴天气的取值介于0～9 之间，通过建立目标函数和约束条件，得出线性规划问题模型，最终通过求解线性规划问题，得到每种情况的最优策略。在最短路线的基础上考虑天气状况和玩家路线是否重合，从而确定最佳收益路线。对于天气状况已知，故排除考虑，我们分别从玩家路线一致且经过矿山的情况和不经过矿山的情况以及玩家路线不一致经过或不经过矿山的情况进行对比分析，最终确定两名玩家路线不一致时，且不经过矿山，该路线是最优策略。

由于每名玩家仅知道当天的天气状况，因此我们考虑建立时间序列分析模型，做出三十天的天气预测，并结合Bellman-Ford 算法与不同方案进行迭代，得到最优路线策略2人共同挖矿，另一个人以最短路线经过所得资金最多，为57760元。最后对模型的优缺点进行了讨论，主要分析了未考虑到折返情况及特殊情况下天气对整个路线规划的影响。

3 结论

首先两种方案的条件下进行路线规划，分别从起点出发到达矿山，然后从矿山到达终点的最短路径，从起点出发不经过矿山直达终点的最短路径，在最短路线的基础上考虑天气状况和玩家路线是否重合，从而确定最佳收益路线。当天气状况已知，排除考虑，我们分别从玩家路线一致且经过矿山的情况和不经过矿山的情况以及玩家路线不一致经过或不经过矿山的情况进行对比分析，最终确定两名玩家路线不一致时，且不经过矿山，该路线是最优策略。对于每名玩家仅知道当天的天气状况，因此我们考虑建立时间序列模型，做出三十天的天气预测，并结合Bellman-Ford 算法与不同方案进行迭代，得到最优路线策略。