基于決策樹的最優(yōu)穿越沙漠策略研究

黎金銘，毛 睿，潘玉雯，陽尚儒

（桂林電子科技大學(xué) 數(shù)學(xué)與計算科學(xué)學(xué)院，廣西 桂林 541004）

基于特定規(guī)則研究穿越沙漠的最優(yōu)策略，求解在初始點購買資源出發(fā)至終點，如何補充資源并賺取更多資金，是研究重點。此課題涉及資源與時間、環(huán)境與風(fēng)險、目標(biāo)與計劃、競爭與合作四項組合優(yōu)化，通常可用動態(tài)規(guī)劃及啟發(fā)式算法求解，若將地圖簡化后建立決策樹模型求解，能更好地解決最優(yōu)策略問題。

1.問題描述

已知未來30 天內(nèi)的天氣或僅知當(dāng)天的天氣，時間最長為30 天或10 天，憑借已知地圖(見圖1 和圖3)，利用初始資金購買水和食物，從起點出發(fā)穿越沙漠。途中會遇到晴朗、高溫、沙暴三種天氣，可在礦山、村莊補充資金或資源，但在村莊資源的價格是起點價格的兩倍。目標(biāo)是在截止期限或之前到達(dá)終點，若未到達(dá)終點而水或食物已耗盡視為策略失敗，到達(dá)終點后該活動結(jié)束，到達(dá)終點時的剩余資金最大。[1]

2.分析問題

穿越沙漠過程中，趕路的資源消耗是停留的2 倍，挖礦是停留的3 倍，每箱水重3 千克，基準(zhǔn)價格5 元；每箱食物的質(zhì)量為2 千克，基準(zhǔn)價格為10 元。在圖1 地圖中每日挖礦收益為1000 元，在圖3 地圖中挖礦收益為200 元。問題一，已知未來的天氣情況，需根據(jù)每日天氣的變化權(quán)衡到底是走是停留還是挖礦，從而到終點時剩余資金最大。問題二，已知當(dāng)天的天氣，但未來天氣未知且不會出現(xiàn)沙暴天氣，需建立決策樹模型，再結(jié)合未來天氣變化概率進行決策，找出最優(yōu)趕路方案。

圖1 地圖1

3.天氣條件確定模型的分析與求解

3.1 資源消耗計算模型

根據(jù)規(guī)則，第i 天消耗資源Qi計算式如下

第i 天補充資源花費QSi=2c1xsi+2c2ysi

xi為第i 天消耗的水?dāng)?shù)量；yi為第i 天時消耗食物的數(shù)量（箱）；c1為水價格；c2為食品價格；xsi表示第i 天路過村莊補給水的箱數(shù)，不補充時為0；ysi表示第i天路過村莊補充食物的箱數(shù)當(dāng)不補充時為0；QSi為第i 天在村莊買東所花的資金。第i 天剩余水的數(shù)量

x0為初始購買水的數(shù)量，y0初始購買食物的數(shù)量。第i 天剩余食物的數(shù)量

結(jié)合公式2、公式3，定義初始時刻負(fù)重為M0(≤1200)，初始時刻購買金額為Q0=c1x0+c2y0，由此推導(dǎo)每天負(fù)重的公式如下：

第i 天挖礦收益iB當(dāng)?shù)趇 天挖礦收益1000，不挖礦時為0.那么，第i 天剩余資金為

3.2 基于最短路徑的決策樹模型

如圖1 所示，連通兩點之間間隔一天的路程。分析地圖可知“從起點去礦山不經(jīng)村莊”花費的時間與“從起點去礦山經(jīng)過村莊”花費的時間相等同時“從礦山去終點”花費的時間與“從礦山經(jīng)過村莊再去終點”花費的時間相等。故假設(shè)從起點出發(fā)經(jīng)過村莊到達(dá)礦山；而從礦山出發(fā)去終點經(jīng)過村莊。根據(jù)分析可得到如圖2 的決策。

圖2 問題一決策樹圖

3.3 模型的求解

要想到達(dá)終點時剩余資金最大需要滿足以下條件：一是在礦山挖礦天數(shù)盡可能多；二是盡量不在高溫天氣挖礦和趕路；三是購買的物資滿足挖礦和趕路即可；四是在起點購買更多的食物。每日在礦山挖礦的收益為1000 元。假設(shè)未來30 天的天氣狀況已知，基本參數(shù)見文獻(xiàn)[1]。基于決策樹模擬算法的步驟如下：Step 1 輸入一月內(nèi)天氣，購買150 箱水、150 箱食物以及決策樹路線進行模擬。Step 2 開始模擬路線趕路，碰到沙暴天氣停止不動，若是晴朗繼續(xù)趕路，若是高溫可選擇停留或者趕路，一天結(jié)束計算剩余資金。Step 3 若遇上村莊則去補充資源，補充路上消耗或根據(jù)未來天氣補充到滿足去終點的資源即可。Step 4 碰上礦山，則去挖礦。挖到剩余資源能滿足去終點或村莊補充資源停止，直奔終點或村莊。轉(zhuǎn)Step5。Step 5 若能到達(dá)終點，重新優(yōu)化起點背包攜帶量和村莊補給量，計算最大收益H，進入下一步；否則穿越失敗回到Step1，改變高溫天氣下的決策重現(xiàn)遍歷。Step 6 檢查決策樹圖路徑，若決策樹沒有搜索完，返回Step1 按照決策樹圖重新模擬，計算最大收益Hi與H 比較。若Hi更大則最大收益H=Hi；若路徑搜索完輸出最大收益H。

表1 問題一每天趕路決策表

由表3 可知，從起點出發(fā)，路線1-25-24-23-22-9-15-14-12-14-15-9-21-27，需要趕路24 天，起點購買178 箱水，333 箱食物，經(jīng)村莊補充163 箱水，只去礦山一次，挖礦7天，再去終點路過村莊補充36 箱水，24 箱食物，最高收益為10470 元。

表3 高溫停留和高溫趕路的資源花費

4.天氣條件未知的模型分析與求解

模型建立和求解：問題二穿越沙漠的范圍變小，穿越的時間限制為10 天，僅知當(dāng)天天氣，但不出現(xiàn)沙暴天氣，每日挖礦收益為200 元，建立決策樹模型分析最優(yōu)決策，簡化后地圖如圖3 所示，基本參數(shù)見文獻(xiàn)[1]。由圖3 可知，從起點出發(fā)去終點的趕路方案僅有兩種。

圖3 地圖2

方案1 在起點處購買資源后開始出發(fā)，直奔終點即1-5-6-13；方案2 在起點處購買資源后出發(fā)去礦山，在礦山挖礦后，再去終點即1-4-3-9-11-13。方案2 比方案2 多花兩天的時間去終點，判斷兩種方案的優(yōu)劣，只需計算方案2 礦山挖礦所得最大凈收益（挖礦收益減去挖礦時的資源花費）減去2 天趕路的花費是否為正數(shù)即可。已知挖礦花費是基礎(chǔ)消耗的3 倍，在礦山的最大挖礦時間為5 天。假設(shè)挖礦時，天氣全為晴朗，計算可知每天挖礦花費165 元，每天挖礦收益200，凈收益35 元，5 天的收益175 元，趕路花費220 元。方案(2)挖礦的收益小于趕路花費，說明直奔終點是最好選擇。

處于高溫天氣的趕路方案：假設(shè)在趕路過程中，天氣變化概率都是獨立同分布的，“晴朗天氣”每天出現(xiàn)概率為P，則“高溫天氣”出現(xiàn)概率為1-P，晴朗天氣出現(xiàn)次數(shù)服從二項分布。

完全不停留決策分析：當(dāng)天氣為晴朗時，資源的消耗最小，最優(yōu)決策為前往終點。當(dāng)天氣為高溫時，是停留還是行仍需討論。趕路到終點所需時間記為t；可推導(dǎo)t 天時（0≤t≤ 3），趕路的平均資金消耗公式如下：

其中，kt,i為到達(dá)終點只剩余t 天路程時，天氣晴朗出現(xiàn)i次的平均消耗資金；P 為晴朗出現(xiàn)概率，1-P 高溫出現(xiàn)的概率。

權(quán)衡原地停留與繼續(xù)趕路的決策分析：當(dāng)剩余天數(shù)為j 天時，假設(shè)當(dāng)天天氣為高溫，對應(yīng)該停留還是趕路進行分析計算。當(dāng)決定在高溫的天氣狀況中進行原地停留時，資源總花費COST1,j為高溫當(dāng)天的停留資源花費Qstay與剩余j 天預(yù)測的趕路資源花費Ej之和；當(dāng)決定在高溫天氣趕路時，資源總花費COST2,j為高溫趕路花費Qwalk與剩余(i-1)天預(yù)測的趕路平均資源花費Ej-1之和；經(jīng)分析可知當(dāng)COST1,j＞COST2,j時，應(yīng)選擇停留；當(dāng)COST1,j＜COST2,j時，最優(yōu)策略是選擇繼續(xù)趕路；當(dāng)COST1,j=COST2,j時，趕路或停留皆可。

模型的求解：計算高溫天氣下的趕路消耗和停留消耗后，再將晴朗概率從0.1 至0.9 進行遍歷，最終得到高溫停留和高溫趕路的資源花費如表5 所示。

由表5 可知當(dāng)晴朗天氣出現(xiàn)的概率在0.85 以下，最優(yōu)決策是不停留直奔終點；當(dāng)晴朗天氣出現(xiàn)的概率超過0.85，最優(yōu)策略是原地停留，等待晴朗天氣出現(xiàn)再繼續(xù)趕路。

5.結(jié)語

本文利用決策樹求解判斷穿越沙漠的最優(yōu)決策，并通過編程仿真模擬計算，通過全局搜索算法求解出初始時刻最優(yōu)的資源購買數(shù)量。問題二中本文利用天氣概率分析問題，得出趕路花費與概率之間的關(guān)系，當(dāng)高溫天氣出現(xiàn)頻率較大時不推薦趕路應(yīng)在原地等待晴天出現(xiàn)。本文的模型降低了求解范圍，方式較為創(chuàng)新，減少了計算量和代碼量。