基于邻接矩阵法的穿越沙漠路线研究

王天龙

【摘 要】本文主要针对穿越沙漠问题进行了相关研究，利用邻接矩阵法制定了不同地图不同天气变化条件下游戲玩家的最优策略。首先利用邻接矩阵先对第一关和第二关分别情况讨论，通过分析得出最优路径。其次第三关的天气变化情况不同通过分析得出最优路径。最后对第五关和第六关进行求解第五关中每天的天气已知，但两名玩家的路线只能当天确定，为使得他们获得的总资金最大，他们的路线应尽可能的不同，第六关天气与第四关一样未知，且地图与第四关相同，因此三名玩家的路线尽可能不重复，且最终所获得的总资金最高。

引言

本文介绍了穿越沙漠小游戏，玩家用地图购买一定数量的水和食物（包括日常必需品），然后从沙漠步行，行走时会有不同的天气（晴天、高温、沙尘暴），当经过矿山和村庄时可以补充资金和资源。游戏开始时间为第0天，游戏者再出发前必须在最后期限之前达到终点线，如果没有达到终点，水或食物耗尽，这被认为游戏失败，如果到达终点线后，玩家可以归还剩下的水和食物。

1、问题分析

在游戏规定的条件下，建立数学模型，在整个游戏时段内每天天气状况事先全部已知，试给出一般情况下玩家的最优策略。首先先求解“第一关”和“第二关”，并将相应结果分别填入Result.xlsx中，其次玩家仅知道当天的天气状况，可据此决定当天的行动方案，并对“第三关”和“第四关”进行具体讨论。

最后对第六关求解，假设有n名玩家，求当n=2时，两位玩家的最优化路线，当n=3时，三位玩家的最优化路线。

2、模型的建立与求

首先采用邻接矩阵 [5]表示沙漠中任意两点之间可行走路线，邻接矩阵平方是表示顶bai点之间相邻关系的矩阵的平方。先对第一关和第二关分别情况讨论，在只有一名玩家，且知道每天的天气变化情况下，要求在30天之内从起点到达终点。需要对玩家行走的路线进行分类，通过最短路径分析出最优的几条路线[2]。在不违背游戏规则情况下，分别对第一关和第二关进行求解。

针对第一关分三种情况：

（1）从1（起点）-27（终点）;

（2）1（起点）-12（矿山）-27（终点）;

（3）1（起点）-15（村庄）-12（矿山）-27（终点）。

在起始点购买物资消耗的钱小于初始资金：ω1<=η，从起始点到终点天数的约束：

其中，β=nd，η=10000，ω=ω1 +ω2，d= 1000，a=190，b=104，c=150，最后得到起点a1-村庄a15（经过且停留一天）-矿山a12（挖矿）-终点a27的最短路径为1-25-24-23-22-9-15-13-12-14-15-9-21。得出即从起点出发经过村庄并停留一天购买物资，然后到达矿山，挖八天的矿物，赚取资金，最后返回终点的过程获得的资金为 13130 元。

针对第二关同样也分三种情况：

（1）1（起点）-64（终点）;

（2）1（起点）-30（矿山）-39（村庄）-64（终点）;

（3）1（起点）-30—（矿山）-64（终点）。

对比三种情况，选出所剩资金最多的一种情况。由于第二关的与第一关的条件相同，仅地图不同。由1（起点）-64（终点）;由起点-上矿场-村庄购买物资-下矿场-村庄（/无）-终点。

最后得到路线从起点直接出发到终点，仅消耗资金，没有任何收益，到达55（矿山）后挖矿7天，去62（村庄）购买所需物资后回到终点，累计资金最大，为9635元。

第三关：（1）1（起点）-13（终点）;

（2）1（起点）-9（矿山）-13（终点）。

对比两种情况，选出所剩资金最多的一种情况，从起点到矿山挖矿挣取资金，最后回到终点。其次途中一直行走不停留，由于起点到矿山，矿山到终点的最短路径已经确定，且不存在沙暴天气，因此可以得到在路上行走消耗的天数是固定的五天，由于挖矿天数越多，获得的收益也越多，在起点购买的物资，最大只能支持行走五天和五天的挖矿时间消耗，若高温条件下不停留，在起点购买的物资，最多可以支持五天挖矿的消耗。

针对第四关：（1）1（起点）-25（终点）;

（2）1（起点）-18（矿山）-14（村庄）-25（终点）;

（3）1（起点）-18（矿山）-25（终点）。

对比三种情况，选出所剩资金最多的一种情况。得出玩家仅知道当天的天气状况，最短路得到从起点直接到终点的最短途径为1-6-11-16-21-22-23-24-25路线。在该路线下，八天晴朗的天气情况下，获得最大收益为9120元。

将游戏规则复杂化，随着玩家数目的变化，挖矿收益和资源消耗也随着发生变化。在不违背游戏规则情况下，针对不同的天气变化情况分别对第五关和第六关进行分情况讨论。针对第五关：

（1）玩家一和玩家二都从1（起点）直接到13（终点）;

（2）玩家一从：1（起点）-13（终点），玩家二从：1（起点）-9（矿山）-13（终点）;

（3）两个玩家：1（起点）-9（矿山）-13（终点）。

选出所剩资金最多的一种情况：由两个玩家同时从起点走向终点，两个玩家一同行走，消耗的物资是一般情况下的二倍，因此为了减少不必要的消耗，尽可能的使得两个人分开走，一个玩家走矿山，一个玩家且不走矿山，最终得出起点直接到终点的最短路径为：1-5-6-13（经过三个区域）. 其次为1-4-7-12（或11）-13（经过四个区域）。因此，两人最终剩余金钱总和为18965元，重量总和为333kg，远远小于重量限制。

针对第六关由第四关可知，直接从起点直接到矿山最后回到终点，是一个玩家获得资金最大的时刻，24150元。且从起点到达矿山，以及从矿山回到终点的最短路线有多条，从起点到矿山，任选三条路线，至少有2个区域是相重合的。（原因：从起点出发只有两条路，3 个人必有两个人一起出发;从最后一个区域到达矿山，同起点出发）。从矿山到终点，无论三个人如何选择，必有一个人，至少与其他两个人的路线有重合。

玩家一的行走路线为1（起点）-2-3-8-13-18（矿山）-19-20-25（终点）;

玩家二的行走路线为1（起点）-6-11-16-17-18（矿山）-23-24-25（矿山）;玩家三的行走路线为1（起点）-2-7-12-17-18（矿山）-19-20-25（终点）。最后收益为求得三人的总收益为11370元。

结论

关卡1和关卡2都已知天气条件，因此考虑行走路线及是否在村庄买物资和挖矿时间的变化，对于不同行走路线分别考虑挖矿时间，得到最终结果。第四关忽略了较少出现的沙暴天气，只讨论了在晴朗和高温两种天气变化情况。第六关只讨论以最大的挖矿时间十六天获得的收益，没有详细讨论两人其它挖矿时间变化。

参考文献：

[1]任洛漪. 基于协同过滤推荐系统优化地图软件路线推荐[J].计算机产品与流通，2020，（09）：133.

[2]徐波，张玉敏.计及恶劣气象条件的系统状态检修决策模型[J].广东电力，2019，32（06）：61-69.

（作者单位：河北工程大学材料科学与工程学院）