1. 引言
现有如下“穿越沙漠”游戏:玩家利用初始资金购买不超过负重上限的水和食物(包括食品和其他必需品),并根据一张地图,从起点出发,在沙漠行走。途中玩家将遇到不同天气情况,最终目标是在规定时间内顺利到达终点并剩余尽可能多的资金。根据游戏规则:遇到沙暴天气,玩家必须停留在原地,到达终点后可退回剩余水和食物,每箱退回价格为基准价格的二分之一。不同天气消耗水和食物的数量不同,玩家可抵达矿山挖矿获得资金,也可选择抵达村庄购买物资。
2. 问题分析
游戏中存在村庄、矿山的设定,玩家可在矿山挖矿获得资金,挖矿一天获得的资金为基础收益,其物资消耗为基础消耗的3倍,沙暴日可以挖矿。玩家在村庄可用任意资金购买资源,物资价格为基准价格的2倍。“穿越沙漠”的最佳策略由路径、物资、天气三方面构成。当只有一名玩家,且整个游戏时段天气状况事先已知,需在充分考虑物资、天气的基础上,得到花费最少资金的最优路径,还需考虑特殊天气(如“沙暴”天气)玩家状态。针对物资,需比较水和食物的携带率,在不超过负重的情况下,携带尽可能多的携带率高的物资,以合理安排水和食物的购买数量。得到最佳策略后,进一步优化算法,降低算法复杂度。
3. 模型建立与求解
经归纳,全部路径可分为三类,第一类:玩家从起点出发,直接抵达终点;第二类:玩家经过矿山挖矿不经过村庄补给物资;第三类:玩家经过村庄补给物资也经过矿山挖矿,根据最短路径的计算,三类最短路径具体见图1。
如图1中,短路径为第一类路径:玩家从起点出发,直接抵达终点。长路径为第二类和第三类路径,区别在于是否在村庄补给物资。
针对第一类路径,运用Dijstra算法,建立邻接矩阵,结合物资、天气的影响可得到最大剩余资金
为9410元。
针对第二类路径,由于村庄补给物资价格为基准价格的2倍,应在起点购买尽可能多的物资,以剩余资金最大化为目标函数,可建立单目标最优化模型 [1]:
目标函数:
(1)
约束条件:
式中,
表示穿越沙漠过程中消耗的物资金额。
分别对应在矿山时晴朗、高温、沙暴对应的天数。
分别对应从矿山到终点晴朗、高温、沙暴对应天数。通过matlab程序即可得到最佳策略,
剩余资金为7690元。
针对第三类路径,玩家选择在村庄补给物资、在矿山挖矿,比较挖矿结束后直接到达终点和挖矿结束后到村庄补给物资,再抵达终点这两种路径的剩余资金,游戏地图可简化,见图2。
Figure 2. Region classifications of the third kind of path
图2. 第三类路径区域划分
其中,起点至村庄的路程称为第一部分,村庄与矿山之间的往返路程称为第二部分,村庄至终点的路程称为第三部分。计算得知,任意路径第一部分的最佳策略固定不变。第三部分的最佳策略,仅需考虑由第二部分不同策略引起的天气变化情况,第二部分玩家收益 [2] 为:
(2)
阐述了通过挖矿获得的资金、矿山与村庄之间补给消耗金额和挖矿过程消耗金额的关系,得到第二部分的收益。求解时,模糊控制,假设游戏期间都为“高温”天气,“挖矿结束后直接抵达终点”路线的收益为1200元,“挖矿结束后到村庄补给物资,再抵达终点”路线的收益为800元。因此,“挖矿结束后直接抵达终点”路线为最佳路线。以剩余资金最大化为目标函数,可建立单目标最优化模型:
目标函数:
(3)
约束条件:
式中,
代表不同地点物资差价,
代表购买物资箱数(
分别表示起点、村庄,分别表示水和食物)。根据条件,可知需在起点购买最大数量的物资,村庄所购物资仅需保证存活即可。为确定水和食物的购入比例,可定义如下占重率公式 [3],即:
(4)
其中,
代表物资单价,
代表每箱物资重量,
分别代表30天内晴天、高温、沙暴占比,
代表不同情况下所需物资(
代表水,
代表食物)。
越大,表示相同物资单价,所占重量越小,水和食物的携带率见表1。
Table 1. System resulting data of standard experiment
表1. 物资携带率
观察表1可知,食物的携带率大于水,因此仅购买生存所需水即可,剩余负重全部用于购买食物,得到最大剩余资金
为10,430元。
最终,已知天气情况时一名玩家的最优策略为:1→25→24→23 (停留一天)→22→9 (停留一天)→15 (补给物资)→13→12 (停留九天,第17、18天原地停留,剩余七天挖矿)→14→16→17→21→27,剩余资金为10,430元。
设玩家花费d天完成游戏,地图共p个区域,可携带的食物或水n箱。算法最外层对i (天数)的循环
,对j (所在区域)的循环
。对每个
判断,若在村庄,更新购买物资复杂度为
。根据复杂度计算程序,可得三种路径算法复杂度为:
,Dijstra算法优化路径算法复杂度为:
,其中
,则算法得到优化,程序运行时间减少。
4. 结论
综合考虑路径、物资、天气要素,结果更接近最优策略。根据是否补给物资和挖矿,将路径分成三大类,进一步细分第三类路径,运用Dijstra算法求出每类路径的最短路径,建立单目标最优化模型,结合物资携带率和天气情况,得到已知天气情况下的最佳策略。最后,经复杂度分析,可知本文算法复杂度低于遍历算法复杂度。