唐杰烽

(五邑大學(xué) 智能制造學(xué)部,廣東 江門 529020)

1 問(wèn)題重述

玩家憑借一張地圖,利用初始資金購(gòu)買一定數(shù)量的水和食物(包括食品和其他日常用品),從起點(diǎn)出發(fā),在沙漠中行走。途中會(huì)遇到不同的天氣,也可在礦山、村莊補(bǔ)充資金或資源,目標(biāo)是在規(guī)定時(shí)間內(nèi)到達(dá)終點(diǎn),并保留盡可能多的資金。

2 模型假設(shè)

(1)假設(shè)題目所給的數(shù)據(jù)真實(shí)可靠；(2)假設(shè)晴朗,高溫,沙暴出現(xiàn)的概率分別為P(Sunny),P(Hot)、P(Sand)；(3)假設(shè)第四關(guān)的沙暴天氣不會(huì)出現(xiàn)在玩家最后前往終點(diǎn)的路上,導(dǎo)致玩家中途游戲失??；(4)假設(shè)兩個(gè)玩家都以游戲勝利為目標(biāo),即最多剩余資金為目標(biāo)進(jìn)行活動(dòng)且不會(huì)出現(xiàn)回退的情況。

3 定義與符號(hào)說(shuō)明

表1

4 模型的建立與求解

4.1 問(wèn)題1 的模型建立與求解

4.1.1 模型的建立

Step1.將附件中的地圖進(jìn)行簡(jiǎn)化,構(gòu)建一個(gè)只存在起點(diǎn)、終點(diǎn)、礦山、村莊的無(wú)向圖。

Step2. 使用Dijkstra 算法在簡(jiǎn)化后的地圖中選取物理最近的路徑,結(jié)合天氣情況和負(fù)重計(jì)算購(gòu)買的物資數(shù)量從而得出剩余資金。

根據(jù)天氣情況將每天所要花費(fèi)的食物和水的箱數(shù)存入二維矩陣needEat 中,其中第一行為水的數(shù)量(單位:箱),第二行為食物的數(shù)量(單位:箱)。remainMoney用以表示剩余資金,principal 表示初始資金,cost 表示用于購(gòu)買水和食物所花費(fèi)的資金。

計(jì)算公式為:

remainMoney=principal-cost

其中cost 是每天所購(gòu)買的水和食物所花費(fèi)的資金的總和。waterprice 和foodprice 分別表示水的基準(zhǔn)價(jià)格(單位:元/箱)和食物的基準(zhǔn)價(jià)格(單位:元/箱)。needEat[1][i]表示根據(jù)當(dāng)天天氣情況所確定的水的消耗量(單位:箱),needEat[2][i]表示根據(jù)當(dāng)天天氣情況所確定的食物的消耗量(單位:箱)。LoadMax=1200kg.

Step3.將是否前往礦山采礦或到村莊進(jìn)行物資補(bǔ)給納入考慮。basicEarning為基礎(chǔ)收益(單位:元/天),earnings 表示玩家采礦所得的總收益,則剩余資金remainMoney 的計(jì)算公式如下:

remainMoney=principal- cost+earnings

由于加入了在村莊購(gòu)買物資的費(fèi)用和在礦山采礦時(shí)提升的費(fèi)用成本,故將總花費(fèi)cost 分解成村莊花費(fèi)(costVillage)、起點(diǎn)購(gòu)買物資的花費(fèi)(costStart)。

此時(shí),總花費(fèi)cost 的計(jì)算公式如下:

cost=costVillage+costStart

其中:

因?yàn)榇迩f購(gòu)買物資的成本為基準(zhǔn)價(jià)格的2 倍,因此村莊花費(fèi)如下:

村莊花費(fèi)costVillage =2(costMining+costWalking)

利用時(shí)間節(jié)點(diǎn)來(lái)區(qū)分起點(diǎn)花費(fèi)和村莊花費(fèi),即利用在村莊采購(gòu)的日期flag 來(lái)標(biāo)記,可知日期1 至flag 日期為起點(diǎn)花費(fèi)；flag日期至結(jié)束日期為村莊花費(fèi)。

earnings 是玩家采礦所得的總收益,用date[earning]來(lái)記錄開始采礦的時(shí)間,則earnings 的計(jì)算公式如下:

Step4.比較上述兩種模式(物理遠(yuǎn)近和前往礦山采礦)的剩余資金remainMoney,取所剩余資金較多的方案為目標(biāo)方案。

4.1.2 問(wèn)題1 模型的求解

對(duì)于第一關(guān),

Step1.將不規(guī)則的路徑進(jìn)行數(shù)字化處理,即利用矩陣存儲(chǔ),并通過(guò)Dijkstra 算法對(duì)路徑進(jìn)行簡(jiǎn)化,得出一幅只有起點(diǎn)、終點(diǎn)、礦山和村莊為頂點(diǎn)的無(wú)向圖,如圖1 所示。

圖1 經(jīng)過(guò)簡(jiǎn)化后的第一關(guān)地圖

由costStart 的第二個(gè)計(jì)算公式可得根據(jù)物理遠(yuǎn)近從起點(diǎn)到終點(diǎn)所耗費(fèi)的資金為cost=590(元)。剩余資金remainMoney=principal-cost=10000-590=9410(元)。

由costStart 和cost 的計(jì)算公式可解得cost=7805(元),挖礦天數(shù)為 MineDay1+MineDay2=8+3 (天)=11 (天),故earnings=11000(元)。

則前往礦山采礦的方案剩余資金為remainMoney=1 2195(元 )

對(duì)于第二關(guān),將不規(guī)則的路徑進(jìn)行數(shù)字化處理,即利用矩陣存儲(chǔ),并通過(guò)Dijkstra 算法對(duì)路徑進(jìn)行簡(jiǎn)化,由第二關(guān)的地圖可知,礦山30 到村莊62 的距離相較于村莊39 遠(yuǎn),而礦山55 到村莊39 比到村莊62 的路程更遠(yuǎn),且與通向終點(diǎn)的路徑相背。則由最短路徑優(yōu)化思想將上述兩條較遠(yuǎn)的路線剔除。

Step2.根據(jù)Step1 所得出的最短路徑,再次利用Dijkstra 算法,求解出從起點(diǎn)到終點(diǎn)的物理上的5 條帶相同權(quán)的路徑,將其中兩條路徑結(jié)合可得出第6 條路徑分別為:

由cost 的計(jì)算公式可得可得根據(jù)物理遠(yuǎn)近從起點(diǎn)到終點(diǎn)所耗費(fèi)的資金為 cost=2810 (元)。 剩余資金為remainMoney=principal-cost=10000-2810=7190(元)。

圖2 第二關(guān)路線圖

Step3. 將是否前往礦山采礦或到村莊進(jìn)行物資補(bǔ)給納入考慮。從起點(diǎn)出發(fā)前往礦山30 采礦5 天,隨后前往離其最近的村莊39,補(bǔ)給后前往礦山55,再次采礦9 天,隨后2 天前往終點(diǎn)。

利用Dijkstra 算法求解出按照路線從起點(diǎn)到終點(diǎn)的最短路徑為

由cost 和costStart 的計(jì)算公式可解得cost=7080(元),挖礦天數(shù)為 MineDay1+MineDay2=5+8 (天)=13 (天),故earnings=13000(元)。

則前往礦山采礦的方案剩余資金為remainMoney=1 5920(元 )

Step4. 將上述兩個(gè)方案的剩余資金remainMoney 做比較,取大者,則前往礦山采礦的方案作為玩家的最優(yōu)策略。

4.2 問(wèn)題2 模型的建立與求解

4.2.1 問(wèn)題2 模型的建立

Step1. 對(duì)附件中的第三關(guān)、第四關(guān)地圖進(jìn)行簡(jiǎn)化,利用Dijkstra 算法構(gòu)建幾個(gè)特殊端點(diǎn)之間的最短路徑。特殊端點(diǎn)指的是起點(diǎn)、終點(diǎn)、礦山和村莊。從而得到一個(gè)只含有特殊端點(diǎn)的無(wú)向圖。

以第三關(guān)為例,經(jīng)簡(jiǎn)化后的地圖如圖3 所示。

圖3 簡(jiǎn)化后的第三關(guān)地圖

Step2.由于天氣未知且玩家可根據(jù)當(dāng)天天氣來(lái)做出當(dāng)天的行動(dòng)決策,題目條件中沙暴天氣出現(xiàn)的幾率較低,因此在考慮玩家行動(dòng)策略時(shí),不考慮沙暴天氣對(duì)行動(dòng)策略的主要影響,而將晴朗行走與高溫行走的物資消耗納入主要決策范圍。

Step3. 使用Dijkstra 算法在簡(jiǎn)化后的地圖中選取物理最近的路徑,結(jié)合天氣情況和負(fù)重計(jì)算購(gòu)買的物資數(shù)量從而得出剩余資金。

根據(jù)天氣情況將每天所要花費(fèi)的食物和水的箱數(shù)存入二維矩陣needEat 中,其中第一行為水的數(shù)量,第二行為食物的數(shù)量。remainMoney 用以表示剩余資金,principal 表示初始資金,cost 表示用于購(gòu)買水和食物所花費(fèi)的資金。

Step4.將是否前往礦山采礦或到村莊進(jìn)行物資補(bǔ)給納入考慮。由于本題的天氣未知,玩家只能知道當(dāng)天的天氣情況作出抉擇。所以注意到不同天氣情況下基礎(chǔ)收益和采礦消耗之間的關(guān)系,以下為涉及到采礦時(shí)的基礎(chǔ)模型。basicEarning為基礎(chǔ)收益(單位:元/天),earnings 表示玩家采礦所得的總收益,則剩余資金remainMoney的計(jì)算公式如下:

remainMoney=principal- cost+earnings

由于加入了在村莊購(gòu)買物資的費(fèi)用和在礦山采礦時(shí)提升的費(fèi)用成本,故將總花費(fèi)cost 分解成村莊花費(fèi)(costVillage)、起點(diǎn)購(gòu)買物資的花費(fèi)(costStart)。

因?yàn)榇迩f購(gòu)買物資的成本為基準(zhǔn)價(jià)格的2 倍,因此村莊花費(fèi)如下:

村莊花費(fèi)

costVillage =2(Day*P(Sunny)*C_Walking in Sunny Day+Day*P(Hot)*C_Resting in Hot Day+Day*P(Sand)*C_Resting in Sand Day)

利用時(shí)間節(jié)點(diǎn)來(lái)區(qū)分起點(diǎn)花費(fèi)和村莊花費(fèi),即利用在村莊采購(gòu)的日期flag 來(lái)標(biāo)記,可知日期1 至flag 日期為起點(diǎn)花費(fèi)；flag日期至結(jié)束日期為村莊花費(fèi)。

earnings 是玩家采礦所得的總收益,用date[earning]來(lái)記錄開始采礦的時(shí)間。

Step4.比較上述兩種模式(物理遠(yuǎn)近和前往礦山采礦)的剩余資金remainMoney,取所剩余資金較多的方案為目標(biāo)方案。

4.2.2 問(wèn)題2 模型的求解

對(duì)于第三關(guān),

Step1. 將不規(guī)則的路徑進(jìn)行數(shù)字化處理,即利用矩陣存儲(chǔ),并通過(guò)Dijkstra 算法對(duì)特殊端點(diǎn)之間的路徑進(jìn)行簡(jiǎn)化,得出一幅只有特殊端點(diǎn)的無(wú)向圖,如圖4 所示。

圖4 簡(jiǎn)化后的第三關(guān)地圖

因天氣未知,所以玩家需要通過(guò)當(dāng)天的天氣做出當(dāng)天的行動(dòng)策略。題目能唯一確定的是10 天內(nèi)不可能出現(xiàn)沙暴天氣。玩家行走策略的主要評(píng)估對(duì)象為晴朗天氣下的行走與高溫天氣下的行走和休息之間的消耗關(guān)系。

Step2. 通過(guò)附件中所附帶的基礎(chǔ)消耗量(箱)可算得

晴朗天氣行走一天的總花費(fèi)C_WalkinginSunnyDay=1 10(元 )

高溫天氣行走一天的總花費(fèi)C_WalkinginHotDay= 270( 元)

高溫天氣休息一天的總花費(fèi)C_restinginHotDay= 135( 元)

玩家從一個(gè)區(qū)域移動(dòng)到與其相鄰的另一區(qū)域,以玩家的耗費(fèi)的角度來(lái)做計(jì)算,高溫行走所耗費(fèi)的資金要大于高溫休息一天后晴天行走所耗費(fèi)的資金。根據(jù)Step1 所得的簡(jiǎn)化地圖可知,在時(shí)間為10 天的情況下,完成物理遠(yuǎn)近的路線的路徑最短所需時(shí)間為4 天,即不考慮用3 天時(shí)間完成從一個(gè)區(qū)域到另一區(qū)域的移動(dòng)。由此可得,玩家的基本行走策略為:如果當(dāng)天為高溫,則不行走,晴朗則行走,且附加約束條件為8 天內(nèi)走完全部路程。

Step3. 使用Dijkstra 算法在簡(jiǎn)化后的地圖中選取物理最近

的路徑,解得路徑為:。由于整個(gè)游戲時(shí)間段中,玩家僅知道當(dāng)天的天氣情況,故作以下幾種特殊情況的假設(shè),并與不考慮天氣直接完成該路徑的決策作比較。

假設(shè)1:前四天都是晴朗,利用

cost=Day*(P(Sunny)*C_Walking in Sunny Day)+P(Hot)*C_Resting in Hot Day)

可得兩種方案的cost 相同。

剩余資金為:

remainMoney=principal-cost=10000-cost

假設(shè)2:前四天中有兩天是高溫天氣,且前六天中只有兩天高溫,利用如假設(shè)1 相同的公式可算得不考慮天氣的行走決策方案的cost 大于考慮天氣的行走方案決策的cost。

經(jīng)計(jì)算,可知考慮天氣的行走決策方案的優(yōu)點(diǎn)為在前8 天中高溫天氣時(shí)間少于4 天,且前4 天中出現(xiàn)高溫天氣所產(chǎn)生的cost 要比不考慮天氣時(shí)所產(chǎn)生的cost 低。

Step4.將是否前往礦山采礦納入考慮。由于游戲規(guī)則指出玩家的基礎(chǔ)收益僅為200 元/天,而晴朗采礦產(chǎn)生的消耗為135 元/天,高溫天氣消耗為405 元/天,在有基礎(chǔ)收益少于采礦消耗的可能性下,途徑礦山再到終點(diǎn)的最短路徑要比物理最短路徑多出一天的路程?？伤愕弥辽僖谇缋什傻V3 天才可減小與物理最短路徑之間的差距。但該條件出現(xiàn)的要求較為苛刻,即大概率情況下,前往礦山都將造成過(guò)多的支出,難以達(dá)到前往礦山采礦獲得收益的目的。故在第三關(guān)中,不考慮玩家前往礦山進(jìn)行采礦。

對(duì)于第四關(guān),

Step1. 將不規(guī)則的路徑進(jìn)行數(shù)字化處理,即利用矩陣存儲(chǔ),并通過(guò)Dijkstra 算法對(duì)特殊端點(diǎn)之間的路徑進(jìn)行簡(jiǎn)化,得出一幅只有特殊端點(diǎn)的無(wú)向圖,如圖5 所示。

圖5 簡(jiǎn)化后的第四關(guān)地圖

Step2. 使用Dijkstra 算法在簡(jiǎn)化后的地圖中選取物理最近的路徑,由于題目表述“30 天內(nèi)極少出現(xiàn)沙暴”,故本文不考慮玩家在最后一段前往終點(diǎn)的路途中遭遇沙暴天氣導(dǎo)致到達(dá)不了終點(diǎn)的情況。

解得路徑為:

Step3.考慮礦山采礦或村莊補(bǔ)給物資的情況。(圖6)

圖6 第四關(guān)路線圖

問(wèn)題3 的解答:

根據(jù)問(wèn)題2 第三關(guān)得出唯一最短路徑為

5 結(jié)論

本文所提出的模型較為簡(jiǎn)潔、簡(jiǎn)單易懂,故可在日常生活中方便應(yīng)用；模型的求解較為簡(jiǎn)單、方便；模型的普適性較強(qiáng),推廣度更大。不足之處在于文章解答的環(huán)境均處于較為理想的狀態(tài),故需考慮的因素還有待發(fā)掘；模型的求解需要較高的編程基礎(chǔ),涉及到強(qiáng)化學(xué)習(xí)。模型可以進(jìn)一步推廣作為一些生存游戲的觀察設(shè)計(jì)的基準(zhǔn),因涉及到許多的生存參數(shù),例如:食物與水的重量分配、在游戲設(shè)計(jì)中,可以在此處添加更多的相關(guān)參數(shù),例如:攻擊、防御等；可以作為功能型機(jī)器人的路徑選擇指標(biāo)。相關(guān)的生存參數(shù)可推廣為機(jī)器人的各項(xiàng)功能指標(biāo)；3.模型上涉及到大量的概率統(tǒng)計(jì)知識(shí),可用于機(jī)器學(xué)習(xí)。