图论在策略图版游戏“穿越沙漠”中的应用

The Application of Graph Theory in the Strategy Board Game “Crossing the Desert”

摘要: 针对“穿越沙漠”游戏的策略求解问题，本文从玩家角度出发，利用数学语言对“穿越沙漠”游戏规则进行详细刻画，以玩家最终抵达终点所剩的资金最多为目标，建立优化模型，并结合Floyd算法对游戏地图进行简化，最终通过随机化贪心算法求解既定条件下的最优游戏策略。

Abstract: In order to find out the strategy of “Crossing Desert” game, from the point of view of the players, we described the rules of the game “crossing the desert” in detail by using mathematical language. Then, we took the maximum amount of funds left at the final destination as the goal, established an optimization model, and simplified the game map with Floyd algorithm, and finally we used randomized greedy algorithm (RGA) to solve the optimal game strategy under the given conditions.