穿越沙漠的小游戏策略

张 敏 张 力 王雪锋 孟慧慧 邵光祖

（ 1、黄河交通学院数学教研室，河南 焦作454002 2、黄河交通学院智能工程学院，河南 焦作454002）

玩家凭借一张地图，利用初始资金购买一定数量的水和食物（包括食品和其他日常用品），从起点出发，在沙漠中行走。途中会遇到不同的天气，也可在矿山、村庄补充资金或资源，在游戏设定的规则下，规定的时间内到达终点，并保留尽可能多的资金。

1 问题分析

根据地形使用广度优先遍历[1]找出任意两区域的最优路径。最优路径的选择从是否挖矿考虑：如果挖矿，则根据动态规划模型求解挖矿天数，从而规划在起点时所需储备的资源；如果不挖矿，根据求得的起点到终点的最短距离以及储备所需资源，并依据所选的最优路径求解剩余资金。比较两种情况下不同线路的剩余资金，选择剩余资金最大的线路填写“第一关”和“第二关”的结果表。

2 模型的建立与求解

2.1 游戏第一关的分析与求解

游戏中只有一名玩家，并且在整个游戏时段内每天的天气状况事先全部已知，寻找一般情况下玩家的最优策略，即寻找从起点到终点的最优路径。

使用广度优先搜索遍历方法，遍历的步骤如下：

（1）从起点1 出发，访问1 区域。

（2）依次访问1 的各个未曾访问过的相邻区域2，25。

（3）分别从这些相邻的区域出发依次访问该区域的相邻区域，并使“先被访问区域的相邻区域”先于“后被访问区域的相邻区域”被访问。

（4）重复步骤（3），直至地图中所有已被访问的区域的相邻区域都被访问到。……