“穿越沙漠”游戏最优策略分析

杨利霞

“穿越沙漠”游戏最优策略分析

! M/ s; w3 a; i0 ~; K
摘要：“沙漠穿越”游戏要求解决玩家在沙漠掘金中能到达终点时获得最大利益的最佳方案问题，第一关中，
只有一名玩家，在整个游戏时段内每天天气状况事先全部已知，运用 Dijkstra 算法求解最短路径的方式，首先
8 e. \# r! Q. |求出行走消耗天数最短的路径，其次在线路固定后并将玩家的策略汇总分为 6 种情况，使用 Lingo 进行线性规
划分别求解，并给出玩家的最优策略和较为简便的计算公式，并通过编译程序以方便后续调用。第二关模型增
加一个村庄和矿场， 需要在第一关的基础上扩充模型，考虑更多可能情况并不断比较得到最佳方案。在最佳
方案下，第一关最终资金量为 10 450 元，第二关最终资金量为 12 365 元。
# m2 ?( l) f. S/ G; g  a  I  E! W. z* v关键词：最短路径问题；线性规划；Dijkstra 算法；0-1 规划
% ?2 I8 m3 O) U3 D

2 `0 k& _. ^9 C. o& U