黎金铭，毛 睿，潘玉雯，阳尚儒
（桂林电子科技大学 数学与计算科学学院，广西 桂林 541004）
基于特定规则研究穿越沙漠的最优策略，求解在初始点购买资源出发至终点，如何补充资源并赚取更多资金，是研究重点。此课题涉及资源与时间、环境与风险、目标与计划、竞争与合作四项组合优化，通常可用动态规划及启发式算法求解，若将地图简化后建立决策树模型求解，能更好地解决最优策略问题。
已知未来30 天内的天气或仅知当天的天气，时间最长为30 天或10 天，凭借已知地图(见图1 和图3)，利用初始资金购买水和食物，从起点出发穿越沙漠。途中会遇到晴朗、高温、沙暴三种天气，可在矿山、村庄补充资金或资源，但在村庄资源的价格是起点价格的两倍。目标是在截止期限或之前到达终点，若未到达终点而水或食物已耗尽视为策略失败，到达终点后该活动结束，到达终点时的剩余资金最大。[1]
穿越沙漠过程中，赶路的资源消耗是停留的2 倍，挖矿是停留的3 倍，每箱水重3 千克，基准价格5 元；
每箱食物的质量为2 千克，基准价格为10 元。在图1 地图中每日挖矿收益为1000 元，在图3 地图中挖矿收益为200 元。问题一，已知未来的天气情况，需根据每日天气的变化权衡到底是走是停留还是挖矿，从而到终点时剩余资金最大。问题二，已知当天的天气，但未来天气未知且不会出现沙暴天气，需建立决策树模型，再结合未来天气变化概率进行决策，找出最优赶路方案。
图1 地图1
3.1 资源消耗计算模型
根据规则，第i 天消耗资源Qi计算式如下
第i 天补充资源花费QSi=2c1xsi+2c2ysi
xi为第i 天消耗的水数量；
yi为第i 天时消耗食物的数量（箱）；
c1为水价格；
c2为食品价格；
xsi表示第i 天路过村庄补给水的箱数，不补充时为0；
ysi表示第i天路过村庄补充食物的箱数当不补充时为0；
QSi为第i 天在村庄买东所花的资金。第i 天剩余水的数量
x0为初始购买水的数量，y0初始购买食物的数量。第i 天剩余食物的数量
结合公式2、公式3，定义初始时刻负重为M0(≤1200)，初始时刻购买金额为Q0=c1x0+c2y0，由此推导每天负重的公式如下：
第i 天挖矿收益iB当第i 天挖矿收益1000，不挖矿时为0.那么，第i 天剩余资金为
3.2 基于最短路径的决策树模型
如图1 所示，连通两点之间间隔一天的路程。分析地图可知“从起点去矿山不经村庄”花费的时间与“从起点去矿山经过村庄”花费的时间相等同时“从矿山去终点”花费的时间与“从矿山经过村庄再去终点”花费的时间相等。故假设从起点出发经过村庄到达矿山；
而从矿山出发去终点经过村庄。根据分析可得到如图2 的决策。
图2 问题一决策树图
3.3 模型的求解
要想到达终点时剩余资金最大需要满足以下条件：一是在矿山挖矿天数尽可能多；
二是尽量不在高温天气挖矿和赶路；
三是购买的物资满足挖矿和赶路即可；
四是在起点购买更多的食物。每日在矿山挖矿的收益为1000 元。假设未来30 天的天气状况已知，基本参数见文献[1]。基于决策树模拟算法的步骤如下：Step 1 输入一月内天气，购买150 箱水、150 箱食物以及决策树路线进行模拟。Step 2 开始模拟路线赶路，碰到沙暴天气停止不动，若是晴朗继续赶路，若是高温可选择停留或者赶路，一天结束计算剩余资金。Step 3 若遇上村庄则去补充资源，补充路上消耗或根据未来天气补充到满足去终点的资源即可。Step 4 碰上矿山，则去挖矿。挖到剩余资源能满足去终点或村庄补充资源停止，直奔终点或村庄。转Step5。Step 5 若能到达终点，重新优化起点背包携带量和村庄补给量，计算最大收益H，进入下一步；
否则穿越失败回到Step1，改变高温天气下的决策重现遍历。Step 6 检查决策树图路径，若决策树没有搜索完，返回Step1 按照决策树图重新模拟，计算最大收益Hi与H 比较。若Hi更大则最大收益H=Hi；
若路径搜索完输出最大收益H。
表1 问题一每天赶路决策表
由表3 可知，从起点出发，路线1-25-24-23-22-9-15-14-12-14-15-9-21-27，需要赶路24 天，起点购买178 箱水，333 箱食物，经村庄补充163 箱水，只去矿山一次，挖矿7天，再去终点路过村庄补充36 箱水，24 箱食物，最高收益为10470 元。
表3 高温停留和高温赶路的资源花费
模型建立和求解：问题二穿越沙漠的范围变小，穿越的时间限制为10 天，仅知当天天气，但不出现沙暴天气，每日挖矿收益为200 元，建立决策树模型分析最优决策，简化后地图如图3 所示，基本参数见文献[1]。由图3 可知，从起点出发去终点的赶路方案仅有两种。
图3 地图2
方案1 在起点处购买资源后开始出发，直奔终点即1-5-6-13；
方案2 在起点处购买资源后出发去矿山，在矿山挖矿后，再去终点即1-4-3-9-11-13。方案2 比方案2 多花两天的时间去终点，判断两种方案的优劣，只需计算方案2 矿山挖矿所得最大净收益（挖矿收益减去挖矿时的资源花费）减去2 天赶路的花费是否为正数即可。已知挖矿花费是基础消耗的3 倍，在矿山的最大挖矿时间为5 天。假设挖矿时，天气全为晴朗，计算可知每天挖矿花费165 元，每天挖矿收益200，净收益35 元，5 天的收益175 元，赶路花费220 元。方案(2)挖矿的收益小于赶路花费，说明直奔终点是最好选择。
处于高温天气的赶路方案：假设在赶路过程中，天气变化概率都是独立同分布的，“晴朗天气”每天出现概率为P，则“高温天气”出现概率为1-P，晴朗天气出现次数服从二项分布。
完全不停留决策分析：当天气为晴朗时，资源的消耗最小，最优决策为前往终点。当天气为高温时，是停留还是行仍需讨论。赶路到终点所需时间记为t；
可推导t 天时（0≤t≤ 3），赶路的平均资金消耗公式如下：
其中，kt,i为到达终点只剩余t 天路程时，天气晴朗出现i次的平均消耗资金；
P 为晴朗出现概率，1-P 高温出现的概率。
权衡原地停留与继续赶路的决策分析：当剩余天数为j 天时，假设当天天气为高温，对应该停留还是赶路进行分析计算。当决定在高温的天气状况中进行原地停留时，资源总花费COST1,j为高温当天的停留资源花费Qstay与剩余j 天预测的赶路资源花费Ej之和；
当决定在高温天气赶路时，资源总花费COST2,j为高温赶路花费Qwalk与剩余(i-1)天预测的赶路平均资源花费Ej-1之和；
经分析可知当COST1,j＞COST2,j时，应选择停留；
当COST1,j＜COST2,j时，最优策略是选择继续赶路；
当COST1,j=COST2,j时，赶路或停留皆可。
模型的求解：计算高温天气下的赶路消耗和停留消耗后，再将晴朗概率从0.1 至0.9 进行遍历，最终得到高温停留和高温赶路的资源花费如表5 所示。
由表5 可知当晴朗天气出现的概率在0.85 以下，最优决策是不停留直奔终点；
当晴朗天气出现的概率超过0.85，最优策略是原地停留，等待晴朗天气出现再继续赶路。
本文利用决策树求解判断穿越沙漠的最优决策，并通过编程仿真模拟计算，通过全局搜索算法求解出初始时刻最优的资源购买数量。问题二中本文利用天气概率分析问题，得出赶路花费与概率之间的关系，当高温天气出现频率较大时不推荐赶路应在原地等待晴天出现。本文的模型降低了求解范围，方式较为创新，减少了计算量和代码量。
猜你喜欢挖矿决策树花费疯狂的“挖矿”作文大王·低年级(2022年8期)2022-07-10矿工“杀红眼”！一切皆可挖矿电脑报(2021年16期)2021-07-07供电紧张，伊朗禁挖比特币4个月环球时报(2021-05-28)2021-05-28新春开拍小礼物影像视觉(2021年3期)2021-03-24情况不同，“花费”不一样小学生学习指导(中年级)(2020年12期)2020-12-04信息时代基于决策树对大学生情绪的分类数码世界(2020年4期)2020-06-18简述一种基于C4.5的随机决策树集成分类算法设计科学与信息化(2019年28期)2019-10-21决策树学习的剪枝方法科学与财富(2016年32期)2017-03-042014年世界杯会花费多少？足球周刊(2014年20期)2014-07-03决策树在施工项目管理中的应用决策与信息·下旬刊(2013年1期)2013-03-11