赵凯龙 杜 庚 臧玉婷 王乐宁 李思琦
（青岛理工大学 山东 青岛 266500）
摘要：本文主要针对解决穿越沙漠游戏的相关问题的研究。利用图论中Floyd算法，借助MATLAB软件求解得所需要的最短路径，做了多种情形下的不同地图模式，对穿越沙漠的行程安排问题进行了探究。首先基于沙漠实际情况建立相关的线性规划模型求解收益最优化问题。其次使用0-1整数规划对各天气下的具体情况进行独立分析，确定最短路时，将各区域画点建立邻接矩阵赋权图。最后对未知的天气情况进行预测，得到三种天气出现的概率分布，将其作为权值对消耗资源对应的资金数进行加权，将各路线上的天气资源消耗量进行加权，得到线路完成后的剩余资金量，对其得到的值进行比较以可以确定最优方案。
关键词：最短路径；线性规划最优化；邻接矩阵
引言
虚拟的一切皆源于现实，游戏中物理空间采用现实地理背景，扩展了人所在的空间，从而为人类的发展提供实验借鉴价值，并对现实物理世界起启示作用[1]。基于以上背景完成游戏，最终目标是在规定时间内到达终点并保留最大资金数。游戏成功或失败。游戏从第0天开始，每天消耗不同数量的水和食物。若玩家在截止日期或之前到达终点即为成功，若资源耗尽或未达到终点则为失败。每天天气为高温、晴朗或沙暴三者的其中一个，地图内所有区域天气相同，玩家每天仅可从一个区域行至相邻区域（具有公共边界的两个区域），行走一天的消耗资源数为基础消耗量的2倍，也可以在停留，停留一天的消耗资源数为基础消耗量。玩家第0天可以在起点以基准价格使用初始资金购买水和食物等资源，允许回到起点，但不能多次在起点购买资源。玩家到达终点后可退回剩余资源，退回价格为基准价格的一半。
1、问题分析
由于任务一中的第一关和第二关已给定1名玩家和每天天气情况，数据齐全，可进行不同情况具体分析。第一关的行进路线考虑两个方面：从起点以最短路线直接到达终点与途中经过矿山和村庄后达到终点，分别根据具体数据进行分析，利用线性规划得出到达村庄资源补给的最大数量，选择最终资金受益最多的路线。第三关的全部天气未知，仅知道当天天气状况，为改善这一条件，可使用马尔科夫预测出全部天气出现的概率，再通过Floyd算法得出地图的最短路线，并结合每种天气的资源消耗量进行计算，较好的弥补了全部天气未知的状态。若全部天气为高温，则资源也足够使用，很好保证了资源的供给。
2、模型的建立与求解
已知此游戏第一关只有一名玩家，也已知整个游戏时间段里每天天气状况，玩家在规定的30天内经历不同天气、不同区域，可购买物资和挖矿获取资金，到达终点时所剩资金效益最大化。第一关的选择方案整体可以分为两种情况，一种不经过矿山、村庄直接到达终点；另一种经过村庄补给且在矿山工作换取资金效益在30天内最终到达终点，当玩家从起点出发不经过矿山、村庄直接到达终点。 此时最优路径如图1 所示：
.jpg)
图1 不经过矿山、村庄最终直接到达终点的最短路径
可以看出，从1（起点）→25→26→27（终点）为此种情况的最优路径，需行走3天。设每天为第i天，晴朗天气为xi=0或1（0表示是其他天气，1表示当天是晴朗天气），高温天气为yi=0或1（0表示是其他天气，1表示当天是高温天气），沙暴天气同理，zi=0或1；根据游戏规则可得目标函数为资金效益最大，则有以下目标函数：
.jpg)
i=1,2,3 式中：Wx、Wy、Wz——晴朗、高温、沙暴天气的水资源基础消耗量，
Vx、Vy、Vz——晴朗、高温、沙暴天气的食物基础消耗量，
iw、iv——水和食物的价格，
mw、mv——水和食物的质量，
Q表示最终资金效益，P表示初始资金。从起点到终点需要3天时间，这3天分别是高温、高温、晴朗，其消耗的物资数量和资金如表1所示：
表1 第一关的方案一期间每天消耗物资量与资金
.jpg)
另外这种情况下的两种物资质量之和每天均不超过负重上限，玩家到达终点后所剩的资金为
10000-590=9410（元）
此为第一关的的方案一，最终玩家剩余资金为9410元。当玩家经过矿山、村庄时，根据第一次到达村庄时是否补充物资可分为两种情况。在讨论第一次经过村庄时是否补充物资之前，先求出玩家从起点经过矿山、村庄最后到达终点的最短路径。对于地图1中的27个区域，可以构造一个赋权图G=（V,E,A0），要计算赋权图中每对顶点之间距离最短路径，利用Floyd算法求出。每次递推产生一个矩阵序列A1,…,Ak,…A27，其中矩阵Ak的第i行第j列元素Ak（i,j）表示从顶点ai到aj的路径上所经过的顶点序号不大于的最短路径长度[2］。经过计算求得在起点购买物资最大量有水242箱、食物237箱，需要消耗资金3580元。当玩家到达矿山时是第9天，此时物资剩余有水128箱、食物127箱，经过计算得出可以在矿山A挖矿4天、获取收益为4000元，即从第10天到第13天所消耗的物资有水35箱、食物40箱，资金总计10420元，此时需要第14天出发到村庄A补充物资，减去途中一天所消耗的物资还剩物资水19箱、食物28箱。在村庄A第一次购满物资，同理按照公式计算得出需要补满的物资数量为水194箱、食物180箱，需要消耗资金5540元, 加上之前所剩物资总共物资是水213箱、食物208箱，剩余资金4880元。已给定天气状况晴朗、高温、沙暴两种，而沙暴天气时消耗水和食物等资源量均比晴朗时多，故假设整个关卡天气全部为高温的极端情况（因为沙暴天气较少出现因此不以沙暴天气出现基准考虑，即当物资量符合高温天气情况，也一定符合晴朗天气情况下的需求），若在此情况下按照路线进行能够到达终点，则第四关中出现任意天气组合玩家皆可顺利到达终点。运用群体优化等机器学习理念对整个地图进行多元搜索优化，可得到玩家的最优策略。
结论
本文三个任务的基本模型是线性规划模型，其中结合实际情况加入了0-1整数规划模型求解目标最优化，模型经典通用、计算方便，使模型更贴近实际、适用范围广。用图论问题中的Floyd算法求解，此算法简单有效、容易理解，代码编写较容易实现。然后采用马尔科夫预测模型描述随机天气进行预测，模型预测效果良好且具有全面性。基于沙漠生存规划问题，亦可应用于其他生存游戏的问题，建立一个单目标整数线性规划模型，这个模型不仅适用于游戏资源配置问题，它对于规划类问题的求解都可以起指导性作用。适用范围非常广泛，在解决工程技术、经济计划、行政管理、交通运输等方面有广泛应用。
参考文献：
[1]应申,侯思远,苏俊如,陈业滨,陈学业,郭仁忠.论游戏地图的特点.武汉大学学报(信息科学版)[J].2020, 卷 (期) :12.
[2]司守奎,孙兆亮,孙玺菁.数学建模算法与应用[M].北京:国防工业出版社,2015.