摘 要：针对特定游戏背景下穿越沙漠问题进行研究，从地图起点出发，以穿越沙漠为游戏背景在约定时间到达终点。在满足相关正负约束条件下合理利用初始资金使得到达终点时资金最多，游戏相关变量可分类为生存变量与收益变量。玩家需要在规定的负重范围内携带物资，若剩余物资不足以满足能耗要求则游戏结束。在路径最优方面，建立利用 Dijskra 算法实现剪枝的动态规划模型，并用 C++ 编程求解，最后利用 Lingo 对结果进行检验，对促进多因素条件下路径的合理规划设计有重要意义。
关键词：动态规划；单源最短路算法；Dijskra 算法；线性规划
DOI:10.19850/j.cnki.2096-4706.2022.02.028
基金项目：江苏省高等学校大学生创新创业训练计划项目（202111998044Y）
中图分类号：TP311 文献标识码：A 文章编号：2096-4706（2022）02-0111-03
Research on the Problem of Crossing Desert Based on Depth DP Search
DONG Zhenghua, JIANG Yingzi, YAN Shanjun
(Xuzhou University of Technology, Xuzhou 221018, China)
Abstract: 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.
Keywords: dynamic programming; single source shortest path algorithm; Dijskra algorithm; linear programming
参考文献：
[1] 谢胜利，唐敏，董金祥 . 求解 TSP 问题的一种改进的遗传算法 [J]. 计算机工程与应用，2002（8）：58-60+245.
[2] 蔡之华，彭锦国，高伟，等 . 一种改进的求解 TSP 问题的演化算法 [J]. 计算机学报，2005（5）：823-828.
[3] 高海昌，冯博琴，朱利 . 智能优化算法求解 TSP 问题 [J].控制与决策，2006（3）：241-247+252.
[4] 周永权，黄正新等 . 求解 TSP 问题的离散型萤火虫群优化算法 [J]. 电子学报，2012，40（6）：1164-1170.
[5] 谢聪 . 求解 TSP 问题的改进离散蝴蝶优化算法 [J]. 数学的实践与认识，2020，50（1）：173-182.
[6] 贺亦甲，符强，朱俊杰，等 . 一种求解 TSP 问题的改进鸟群算法 [J]. 计算机时代，2019（5）：56-60.
作者简介：董正华（2001—），女，汉族，江苏盐城人，本科在读，研究方向：应用统计学；姜英姿（1970—），男，汉族，山东文登人，高级实验师，硕士，研究方向：数学与统计；通讯作者：燕善俊（1978—），男，汉族，江苏沛县人，副教授，硕士，研究方向：数学和信息科学。