“穿越沙漠”最佳策略研究 Research on the Best Strategy of “Crossing the Desert”

doi:10.12677/ORF.2021.111009

Operations Research and Fuzziology
Vol. 11 No. 01 ( 2021 ), Article ID: 40292 , 5 pages
10.12677/ORF.2021.111009

“穿越沙漠”最佳策略研究

朱传辉，杨赵苡宏，王树艳

●How to Cite this Article

临沂大学，山东临沂

收稿日期：2021年1月4日；录用日期：2021年1月31日；发布日期：2021年2月7日

摘要

本文主要研究“穿越沙漠”游戏的最佳策略。“穿越沙漠”游戏，实质是以剩余资金最大化为目标的策略最优化问题。在只有一名玩家，且整个游戏时段天气状况事先已知的情况下，首先，根据是否补给物资和挖矿的条件，将全部路径分为三类，运用Dijstra算法计算每类最短路径。其次，针对每类路径建立单目标最优化模型，结合物资的携带率和天气情况，对比得到最佳策略。最后，分析算法的复杂度，可知本文算法复杂度低于遍历算法。

关键词

单目标最优化模型，复杂度，Dijkstra算法

Research on the Best Strategy of “Crossing the Desert”

Chuanhui Zhu, Zhaoyihong Yang, Shuyan Wang

Linyi University, Linyi Shandong

Received: Jan, 4^th, 2021; accepted: Jan. 31^st, 2021; published: Feb. 7^th, 2021

ABSTRACT

In this paper, the best strategy of “crossing the desert” is studied. The essence of “crossing the desert” game is a strategic optimization problem aiming at maximizing the remaining funds. When there is only one player and the weather condition of the whole game period is known in advance, firstly, according to the conditions of supplying materials and mining, all paths are divided into three categories, and the shortest path of each type is calculated by Dijstra algorithm. Secondly, a single objective optimization model is established for each type of path, and the best strategy is obtained by comparing the material carrying rate and weather conditions. Finally, the complexity of the algorithm is analyzed, which shows that the complexity of this algorithm is lower than that of the traversal algorithm.

Keywords:Single-Objective Optimization Model, Complexity, Dijkstra Algorithm

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

现有如下“穿越沙漠”游戏：玩家利用初始资金购买不超过负重上限的水和食物(包括食品和其他必需品)，并根据一张地图，从起点出发，在沙漠行走。途中玩家将遇到不同天气情况，最终目标是在规定时间内顺利到达终点并剩余尽可能多的资金。根据游戏规则：遇到沙暴天气，玩家必须停留在原地，到达终点后可退回剩余水和食物，每箱退回价格为基准价格的二分之一。不同天气消耗水和食物的数量不同，玩家可抵达矿山挖矿获得资金，也可选择抵达村庄购买物资。

2. 问题分析

游戏中存在村庄、矿山的设定，玩家可在矿山挖矿获得资金，挖矿一天获得的资金为基础收益，其物资消耗为基础消耗的3倍，沙暴日可以挖矿。玩家在村庄可用任意资金购买资源，物资价格为基准价格的2倍。“穿越沙漠”的最佳策略由路径、物资、天气三方面构成。当只有一名玩家，且整个游戏时段天气状况事先已知，需在充分考虑物资、天气的基础上，得到花费最少资金的最优路径，还需考虑特殊天气(如“沙暴”天气)玩家状态。针对物资，需比较水和食物的携带率，在不超过负重的情况下，携带尽可能多的携带率高的物资，以合理安排水和食物的购买数量。得到最佳策略后，进一步优化算法，降低算法复杂度。

3. 模型建立与求解

经归纳，全部路径可分为三类，第一类：玩家从起点出发，直接抵达终点；第二类：玩家经过矿山挖矿不经过村庄补给物资；第三类：玩家经过村庄补给物资也经过矿山挖矿，根据最短路径的计算，三类最短路径具体见图1。

如图1中，短路径为第一类路径：玩家从起点出发，直接抵达终点。长路径为第二类和第三类路径，区别在于是否在村庄补给物资。

针对第一类路径，运用Dijstra算法，建立邻接矩阵，结合物资、天气的影响可得到最大剩余资金 $E_{1}$ 为9410元。

针对第二类路径，由于村庄补给物资价格为基准价格的2倍，应在起点购买尽可能多的物资，以剩余资金最大化为目标函数，可建立单目标最优化模型 [1]：

目标函数： $E_{2} = M_{原} + S_{挖} \sum_{i = 1}^{3} x_{i} - N (t_{i}, x_{i})$ (1)

约束条件： ${\begin{cases} 0 \leq \sum_{i = 8}^{10} (x_{i} + t_{i}) + \sum_{i = 1}^{3} t_{i} \leq 30 \\ w e i g h t \leq 1200 kg \\ p r i c e \leq 10000 y \end{cases}$

式中， $N (t_{i}, x_{i})$ 表示穿越沙漠过程中消耗的物资金额。 $x_{i} (i = 1, 2, 3)$ 分别对应在矿山时晴朗、高温、沙暴对应的天数。 $t_{i} (i = 8, 9, 10)$ 分别对应从矿山到终点晴朗、高温、沙暴对应天数。通过matlab程序即可得到最佳策略， $E_{2}$ 剩余资金为7690元。

Figure 1. Path classifications

图1. 路径分类

针对第三类路径，玩家选择在村庄补给物资、在矿山挖矿，比较挖矿结束后直接到达终点和挖矿结束后到村庄补给物资，再抵达终点这两种路径的剩余资金，游戏地图可简化，见图2。

Figure 2. Region classifications of the third kind of path

图2. 第三类路径区域划分

其中，起点至村庄的路程称为第一部分，村庄与矿山之间的往返路程称为第二部分，村庄至终点的路程称为第三部分。计算得知，任意路径第一部分的最佳策略固定不变。第三部分的最佳策略，仅需考虑由第二部分不同策略引起的天气变化情况，第二部分玩家收益 [2] 为：

$P = S_{1} - S_{2} - S_{3}$ (2)

阐述了通过挖矿获得的资金、矿山与村庄之间补给消耗金额和挖矿过程消耗金额的关系，得到第二部分的收益。求解时，模糊控制，假设游戏期间都为“高温”天气，“挖矿结束后直接抵达终点”路线的收益为1200元，“挖矿结束后到村庄补给物资，再抵达终点”路线的收益为800元。因此，“挖矿结束后直接抵达终点”路线为最佳路线。以剩余资金最大化为目标函数，可建立单目标最优化模型：

目标函数： $E_{3} = M_{原} + S_{挖} \sum_{i = 1}^{3} x_{i} - N (t_{i}, x_{i}) - \sum_{\begin{array}{l} i = 1, 2 \\ j = 1, 2 \end{array}}^{n} x_{i j} D i f f e r e n c e_{i j}$ (3)

约束条件： ${\begin{cases} \sum_{i = 1}^{3} (x_{i 1} + x_{i 2}) \leq 1200 kg \\ \min (\sum_{i = 1}^{3} x_{i 1}) > 379 \\ \min (\sum_{i = 1}^{3} x_{i 2}) > 349 \end{cases}$

式中， $D i f f e r e n c e_{i j}$ 代表不同地点物资差价， $x_{i j}$ 代表购买物资箱数( $i = 1, 2$ 分别表示起点、村庄，分别表示水和食物)。根据条件，可知需在起点购买最大数量的物资，村庄所购物资仅需保证存活即可。为确定水和食物的购入比例，可定义如下占重率公式 [3]，即：

$ω = \frac{p r i c e_{u n i t}}{w e i g h t_{u n i t}} \times \sum_{i = 1}^{3} a_{i} c_{i j}$ (4)

其中， $p r i c e_{u n i t}$ 代表物资单价， $w e i g h t_{u n i t}$ 代表每箱物资重量， $a_{i} (i = 1, 2, 3)$ 分别代表30天内晴天、高温、沙暴占比， $c_{i j}$ 代表不同情况下所需物资( $j = 1$ 代表水， $j = 2$ 代表食物)。 $ω$ 越大，表示相同物资单价，所占重量越小，水和食物的携带率见表1。

Table 1. System resulting data of standard experiment

表1. 物资携带率

观察表1可知，食物的携带率大于水，因此仅购买生存所需水即可，剩余负重全部用于购买食物，得到最大剩余资金 $E_{3}$ 为10,430元。

最终，已知天气情况时一名玩家的最优策略为：1→25→24→23 (停留一天)→22→9 (停留一天)→15 (补给物资)→13→12 (停留九天，第17、18天原地停留，剩余七天挖矿)→14→16→17→21→27，剩余资金为10,430元。

设玩家花费d天完成游戏，地图共p个区域，可携带的食物或水n箱。算法最外层对i (天数)的循环 $O (d)$ ，对j (所在区域)的循环 $O (p)$ 。对每个 $(i, j)$ 判断，若在村庄，更新购买物资复杂度为 $O (n^{2})$ 。根据复杂度计算程序，可得三种路径算法复杂度为： $O (b \times p \times (n^{2} + n^{2} + n^{2})) = O (b p n^{2})$ ，Dijstra算法优化路径算法复杂度为： $O (b n q n^{2}) = O (b d n^{2})$ ，其中 $p > q$ ，则算法得到优化，程序运行时间减少。

4. 结论

综合考虑路径、物资、天气要素，结果更接近最优策略。根据是否补给物资和挖矿，将路径分成三大类，进一步细分第三类路径，运用Dijstra算法求出每类路径的最短路径，建立单目标最优化模型，结合物资携带率和天气情况，得到已知天气情况下的最佳策略。最后，经复杂度分析，可知本文算法复杂度低于遍历算法复杂度。

文章引用

朱传辉,杨赵苡宏,王树艳. “穿越沙漠”最佳策略研究
Research on the Best Strategy of “Crossing the Desert”[J]. 运筹与模糊学, 2021, 11(01): 70-74. https://doi.org/10.12677/ORF.2021.111009

参考文献

1. 姜启源, 谢金星. 数学模型(第三版) [M]. 北京: 高等教育出版社, 2003.

2. 王莉. 动态不确定路径优化模型与算法[D]: [博士学位论文]. 北京: 北京交通大学, 2017.

3. 闫登福. 基于距离可达矩阵的自驾游路线优化研究[D]: [硕士学位论文]. 沈阳: 东北大学, 2012.

期刊菜单