基于深度DP搜索的穿越沙漠问题的研究

Research on the Problem of Crossing Desert Based on Depth DP Search

针对特定游戏背景下穿越沙漠问题进行研究,从地图起点出发,以穿越沙漠为游戏背景在约定时间到达终点。在满足相关正负约束条件下合理利用初始资金使得到达终点时资金最多,游戏相关变量可分类为生存变量与收益变量。玩家需要在规定的负重范围内携带物资,若剩余物资不足以满足能耗要求则游戏结束。在路径最优方面,建立利用Dijskra算法实现剪枝的动态规划模型,并用C++编程求解,最后利用Lingo对结果进行检验,对促进多因素条件下路径的合理规划设计有重要意义。

This paper studies the problem of crossing desert under the specific game background,starting from the starting point of the map,taking crossing desert as the game background and reaching the destination at the agreed time.Under the condition of satisfying the relevant positive and negative constraints,make rational use of the initial funds to maximize the funds at the end.The game related variables can be divided into survival variables and income variables.Players need to carry materials within the specified load range.If the remaining materials are not enough to meet the energy consumption requirements,the game ends.In terms of path optimization,a dynamic programming model of pruning using Dijskra algorithm is established and solved by C++programming.Finally,lingo is used to test the results,which is of great significance to promote the rational planning and design of paths under the condition of multiple factors.