黎金铭，毛 睿，潘玉雯，阳尚儒

（桂林电子科技大学 数学与计算科学学院，广西 桂林 541004）

基于特定规则研究穿越沙漠的最优策略，求解在初始点购买资源出发至终点，如何补充资源并赚取更多资金，是研究重点。此课题涉及资源与时间、环境与风险、目标与计划、竞争与合作四项组合优化，通常可用动态规划及启发式算法求解，若将地图简化后建立决策树模型求解，能更好地解决最优策略问题。

1.问题描述

已知未来30 天内的天气或仅知当天的天气，时间最长为30 天或10 天，凭借已知地图(见图1 和图3)，利用初始资金购买水和食物，从起点出发穿越沙漠。途中会遇到晴朗、高温、沙暴三种天气，可在矿山、村庄补充资金或资源，但在村庄资源的价格是起点价格的两倍。目标是在截止期限或之前到达终点，若未到达终点而水或食物已耗尽视为策略失败，到达终点后该活动结束，到达终点时的剩余资金最大。[1]

2.分析问题

穿越沙漠过程中，赶路的资源消耗是停留的2 倍，挖矿是停留的3 倍，每箱水重3 千克，基准价格5 元；每箱食物的质量为2 千克，基准价格为10 元。在图1 地图中每日挖矿收益为1000 元，在图3 地图中挖矿收益为200 元。问题一，已知未来的天气情况，需根据每日天气的变化权衡到底是走是停留还是挖矿，从而到终点时剩余资金最大。问题二，已知当天的天气，但未来天气未知且不会出现沙暴天气，需建立决策树模型，再结合未来天气变化概率进行决策，找出最优赶路方案。……