基于动态规划的沙漠行走问题决策分析

姚铭波 黄品文 张婉春 陆 瑶

（浙江水利水电学院，浙江 杭州310018）

针对问题一的求解，第一关：首先将地图转换成无向图进行预处理，其次根据已知条件写出动态规划模型，决策变量为：路径、是否挖矿、是否沿途买水和食物、初始出发时的资金，目标函数为：玩家到达终点时留存的总资金最大，约束条件为：到达终点的截止日期不能超过30 天、负载量不能超过1200 千克、资金、水、食物负重以及当天金币的状态的建模约束。在已知全部天气状况的情况下，再根据无向图写出邻接矩阵，用Floyd 算法得到27 个点两两之间任意的最短路径，然后用C 语言进行求解，最佳结果在第23 天返回终点，总金额为10430 元；第二关：在第一关的基础上，只改变了最短路径，其余条件不变，最佳结果在第30 天返回终点，总金额为12710 元。

1 问题的背景与重述

游戏已经成为人们休闲娱乐的调味品，玩家可以在游戏世界中通过完成任务，领取更高的奖励。现如今有一款穿越沙漠的游戏，玩家凭借着地图在沙漠中行走，根据地图的难度不同，游戏的策略也呈现出不同的效果。如何根据地图难度的不同，在遵守游戏规则的情况下，解决资金资源问题，尽可能留有多的资金，成为游戏攻略的一大难题。

2 问题的分析

问题一要求在一个人出发时得知接下来所有天气状况后求出第一关和第二关的最优解，我们先通过题目和游戏规则整理出目标函数、决策变量和全面准确的相关约束条件，建立问题一的动态规划模型，最后建立模型用C 语言求出最优解，如果难以求解就先通过建立邻接矩阵然后用floyd 算法求出最短路径，再通过优化路径法化简模型，贪心算法求出不同方案的近似解。……