苏禧媛

（陕西科技大学文理学院，陕西 西安 710021）

穿越沙漠是一种典型的生存游戏，此游戏需遵守一些游戏规则，例如：负重不能超过上限，购买物资时需考虑资金是否足够，在规定时间内到达终点。本文要解决的问题是考在遵守游戏规则的情况下，考虑一定的风险性帮玩家找到最优策略，实现剩余资金量最多这一目标。

1 问题分析

针对“玩家必须在截止日期或之前到达终点”这一游戏规则，本文采用图论Dijkstra 的方法求得起点到村庄、起点到矿山、村庄到矿山、村庄到终点、矿山到终点的最短距离，同时利用Kruskal 算法（避圈法）对模型进行优化。

针对这是多位玩家参与寻求最优策略的问题。在游戏规则改变后，需要分多种情况来讨论。最终的目的都是需要走最少的路获得最大的利，尽量不同时走相同路线。针对于此，本文涉及利用极端情况进行讨论，并同时设置风险界限a，将多目标规划变成一个目标的线性规划[1-3]。最后分别按情况进行讨论，并利用博弈论分析玩家心理，求出最优行走路径。

2 模型建立与求解

2.1 Dijkstra 与Kruskal 算法运用

起点→矿山→终点最短路径如图1 所示，可以看出，此地图是一个不规则的多边形图，为了将它进行简化，我们利用Dijkstra 算法分别求得起点到村庄，起点到矿山，村庄到矿山，村庄到终点，矿山到终点的最短距离，分别记为：T1，T2，T3，T4，T5，通过求解得出：T1=6，T2=8，T3=2，T4=3，T5=5，于是可以建立最短路径图，同时利用Kruskal 算法（避圈法）对图进行优化。

图1 起点→矿山→终点最短路径

在确定了起点和终点的最短路径后，只需对村庄和矿山之间的往返情况进行分析，争取在起点购买充足的物资，减少往返路程和时间，保证收取资源的时间尽可能多，以期获得较多的收益，剩余资金数最大。……