基于所谓枚举法的穿越沙漠游戏最优策略研究王欢--中国期刊网

字体：大中小

首页> 原创作品> 正文

基于所谓枚举法的穿越沙漠游戏最优策略研究王欢

发表时间：2021/3/3 来源：《论证与研究》2021年1期作者：王欢1 金秋彤2 &#

[导读] 摘要：本文主要针对穿越沙漠游戏的最短路径进行了相关研究，利用所谓枚举法、灰色预测模型制定了最短路径的策略。首先利用相邻区域为连接点，得出邻接矩阵图，通过Matlab编程，得到第一关和第二关最短路径。其次对第三关和第四关进行灰色预测，得出沙暴天气出现的概率，结合可能性推论。最后利用博弈论构建玩家到达终点的决策树模型，一人采用第四关的最优策略挖矿，另外两人不挖矿。第六关一人采用和第四关一样的策略，另外

                                                             王欢1 金秋彤2 刘小宁1
                           （1.甘肃农业大学信息科学技术学院甘肃兰州 730070；2.甘肃农业大学植物保护学院甘肃兰州 730070）
        摘要：本文主要针对穿越沙漠游戏的最短路径进行了相关研究，利用所谓枚举法、灰色预测模型制定了最短路径的策略。首先利用相邻区域为连接点，得出邻接矩阵图，通过Matlab编程，得到第一关和第二关最短路径。其次对第三关和第四关进行灰色预测，得出沙暴天气出现的概率，结合可能性推论。最后利用博弈论构建玩家到达终点的决策树模型，一人采用第四关的最优策略挖矿，另外两人不挖矿。第六关一人采用和第四关一样的策略，另外两人不挖矿并走最短路径。
        关键词：所谓枚举法；灰色预测模型；博弈论；决策树
        引言：
        随着社会现代化，游戏的出现深受人们的喜爱，“穿越沙漠”这款游戏，并没有想象中的那么简单，里面还融入了数学知识，它并不是在规定时间内走到终点那么简单，而且还要考虑资金尽可能的多，除此之外，还受到路径、天气、水、粮食等众多因素的影响，让人们在玩游戏消遣娱乐之时，还有着开发思维的作用。建立适当的模型，寻找在各个限定条件下的最优策略。
        1.问题分析
        首先运用图论中邻接矩阵求最短路径的模型，结合决策模型将求得的路径转化为选定的最优路线，再运用 Matlab 软件编程，得出必须通过矿山的最短路径，其次在确定的路线上用计算机模拟枚举出多种收益方案，通过灰色预测法，对天气状况进行预测，最后由于它出现了 n 名玩家，考虑 n 名玩家在游戏开始到到达终点的各种路线的可能，构建决策树模型，并结合游戏博弈论使玩家在最优路线下剩余的资金最多。
        2.模型的建立及求解
        首先对第一关以区域为点，以相邻区域为连接点，得出邻接矩阵图，通过Matlab 编程，得最短路径作为最优路线。

                                                                                  图1 邻接矩阵图
        当一个区域可通往另一个区域时数值设为1，人待在原地时设为0，不能通往时设为-1。将数据导入Matlab中并对此编程，通过[path，dis tan ce]=shortestpath（G，s，t）语句得出最短路径，其中s是起点，t是想要去的点。其次利用所谓枚举法，就是在列举所有可能的解，逐一检验直至找到真正的解，在最短路径的最优路线下，建立模型最优解。步骤如下：
       （1）对限制条件加以抽象成类通过计算机编程枚举算法。
       （2）模拟枚举算法。
       （3）给出最优路线下的决策。
        模拟过程中要考虑路径、天气、水、粮食、补给等因素，从而合理的编程进行求解，引出主过程，工具类和天气类三个概念。最后得出第一关起点到村庄经过矿山到达终点的最短路径1-- 25 -- 24 -- 23-- 22（或者21）--9--15 -- 13（14）-- 2--13（14）--15--9--21--27剩余资金为 10190 元，剩余物资为 2 箱水，最终资金为 10200 元。
        利用第一关的模型给第二关做出方案得出起点到第一个矿山（30），然后在矿山挖五天矿，再花一天到达第一个村庄补给，补给的是村庄到第二个矿山、在矿山挖 8 天矿、去第二个村庄、这三段路程的耗费，最后在第二个村庄补给两天到终点的耗费，最终资金为11920 元。
        第三关中没有沙暴出现只有高温和晴朗，最后剩余资金=开始的最大资金-中间三天高温耗费的资金，剩余 9400 元。利用灰色预测模型：1、给定原始时间序列, 并记作

显然, 当T=1时, 即是连续的每天数据组成的原始数列建立一阶灰色模型进行预测的方法。题中已知 30 天内较少出现沙暴天气，按照出现的最大概率 20% 算，也就是出现六天，对这六天沙暴的预测结果为：

                                                                                       表1预测表
        可得知沙暴天气的概率，再结合第三关的论证，给出最优路线决策。对第三关通过比较可能性推理的两种极端可能，得出不去矿山途中全是高温的剩余资金大于去矿山途中及挖矿时全是晴天的剩余资金，得出最优策略：选择不去矿山直接到达终点的这条路，不管出现什么天气只要走这条路便剩余资金最多。
        对于第四关在沙暴天气概率出现的情况下，在第 0 天就得确定方案，也就是说在第 0 天达到了纳什均衡，对于玩家来说们只要其他人不改变策略，他就无法完善自己的状况。由囚徒困境模型得知，三种状况，两者都挖矿，一个人挖矿一个人不挖矿，两个人都不挖矿，而由囚徒困境得到在两个人都不挖矿不走同一条路的情况下整体收益最大。这是最均衡的结果，要在整体收益最大的情况下如果一个人想做出改变去挖矿会导致整体收益下降，因而导向了一个较好的合作的结果，纳什均衡趋向于帕累托最优。
        在第五关中每个参与者都有限种策略选择并允许混合策略的前提下，纳什均衡定存在。由博弈论中囚徒困境模型得知，三种状况，两者都挖矿，一个人挖矿一个人不挖矿，两个人都不挖矿，而由囚徒困境得到在两个人都不挖矿不走同一条路的情况下整体收益最大。根据决策树算出每种方案的剩余资金，通过对比可得出第五关最优策略为：两人不能相遇，途中都不挖矿且不同路线到达终点，最后剩余收益最多为 8910 元。
        对于第六关在第五关的基础上结合第四关的灰色预测模型得出最优策略为：一人挖矿，两人不挖矿且其中一人与挖矿的人在第一天相遇，挖矿的人采取第四关的最优策略，结合囚徒困境和智猪模型可得该种策略为最优。
        参考文献：
        [1]张维迎.《博弈论与信息经济学》[M].上海:上海三联出版社,2004.
        [2]郭秀英.预测决策的理论与方法[M].北京:化学工业出版社,2010.