基于Floyd 算法的穿越沙漠游戲研究

柳 堰 唐龍海 梁曉瑞

（1、太原理工大學(xué)土木工程學(xué)院,山西 太原030024 2、太原理工大學(xué)電氣與動(dòng)力工程學(xué)院,山西 太原030024）

隨著大數(shù)據(jù)時(shí)代的到來(lái),針對(duì)本問(wèn)題建立的模型,模型的優(yōu)點(diǎn)在于通過(guò)假設(shè)使得問(wèn)題大大簡(jiǎn)化。然而這也是該模型最大的弊病所在,并沒(méi)有考慮多次進(jìn)行挖礦以及連續(xù)多天挖礦包括多次在村莊進(jìn)行補(bǔ)給的情況,不考慮特殊因素的情況下,由于只要有時(shí)間挖礦,收益就會(huì)大于虧損,故最優(yōu)解應(yīng)該存在于多次、多天連續(xù)挖礦并進(jìn)行多次往返村莊購(gòu)買(mǎi)補(bǔ)給的情況中。本文中所使用的Floyd 算法相較于旅行商模型、遺傳算法等求解最優(yōu)路徑相比,可以得到精確解,而不僅僅是隨機(jī)解,用圖論模型形象直觀的體現(xiàn)了路線(xiàn)之間的關(guān)系。

1 問(wèn)題分析

首先利用基于Floyd 算法,得出目標(biāo)函數(shù),即到達(dá)終點(diǎn)所剩資金（包含退還食物和水的資金）的最大值的路徑即為最優(yōu)路徑。第一關(guān)和第二關(guān)模型類(lèi)似,只是第二關(guān)的地圖稍復(fù)雜。第三關(guān)只有一名玩家,且只知道當(dāng)天的天氣情況,但已知十天之內(nèi)不會(huì)出現(xiàn)沙暴天氣。需要使用Floyed 算法遍歷各元素求出最短路徑。由于玩家只知道當(dāng)天的天氣情況,因此建立十天之內(nèi)的概率天氣矩陣,第四關(guān)仍然只有一名玩家,也只知道當(dāng)天的天氣情況,但已知30 天內(nèi)較少出現(xiàn)沙暴天氣,無(wú)非在調(diào)整概率天氣矩陣時(shí),添加較低比重的沙暴天氣即可。第五關(guān)有兩名玩家,且每天天氣情況已知。在游戲途中,由于相同路程和相同行為（這里指挖礦和村莊購(gòu)買(mǎi)）的開(kāi)銷(xiāo)成倍增加,遍歷元素之間的最優(yōu)路徑之后,使兩位玩家盡量避免相同行程和相同的行為,最后對(duì)每種組合方式進(jìn)行分類(lèi)討論。

2 模型的建立與求解

首先建立地圖上每個(gè)元素之間的距離矩陣,相鄰元素用1來(lái)表示,地圖上不相鄰元素之間設(shè)為無(wú)窮大,在第一關(guān)中最終可以得到一個(gè)27×27 的距離矩陣。第二關(guān)元素較多,找出規(guī)律進(jìn)行矩陣的建立。最終可以得到64×64 的距離矩陣。具體可以分為以下幾種情況：若該元素位于奇數(shù)行,則可以分為中間列（左右均有相鄰元素）、左列（左邊無(wú)相鄰元素而右邊有相鄰元素）、右列（右邊無(wú)相鄰元素而左邊有相鄰元素）。在這三種情況中,每種情況又可以分為最上行（以上無(wú)其他元素）和其他行（以上有其他元素）；若該元素位于偶數(shù)行,則依然可以分為中間列、左列和右列。在這三種情況中,每種情況也可以分為最下行（以下無(wú)其他元素）和其他行（以下有其他元素）。如圖1 所示。

進(jìn)行分類(lèi)后,即可按照與之臨近關(guān)系判斷是否相鄰,同時(shí)設(shè)置天氣矩陣,設(shè)晴天為1,高溫為2,沙暴為3。玩家可以在村莊和起點(diǎn)購(gòu)買(mǎi)食物和水,由于村莊購(gòu)買(mǎi)資源的價(jià)格為基礎(chǔ)價(jià)格的2 倍,因此應(yīng)該盡可能在起點(diǎn)購(gòu)買(mǎi)所有的食物和水；又由于背包承載質(zhì)量1200kg 的限制,玩家不得不在村莊購(gòu)買(mǎi)物資,助力于礦山挖礦和到達(dá)終點(diǎn)。做出如下約束：在起點(diǎn)處玩家應(yīng)盡可能多的購(gòu)買(mǎi)并且保證能夠到達(dá)村莊,但不能超過(guò)1200kg；所有的水和食物恰好能在到達(dá)終點(diǎn)時(shí)消耗完。可以通過(guò)約束條件得到購(gòu)買(mǎi)食物和水的分配優(yōu)化模型。具體算式如下：

圖1 第二關(guān)元素分類(lèi)

通過(guò)matlab 可以得到最優(yōu)解z 以及對(duì)應(yīng)最優(yōu)解的決策變量x。第一種路徑為不在村莊買(mǎi)食物和水以及不在礦山挖礦（可以經(jīng)過(guò)村莊和礦山）,直接到達(dá)終點(diǎn)；第二種情況是先經(jīng)過(guò)村莊購(gòu)買(mǎi)水和食物。若所帶補(bǔ)給足夠到達(dá)終點(diǎn),則一定不會(huì)去村莊進(jìn)行購(gòu)買(mǎi),故這種情況與第一種情況互斥。第三種情況為到達(dá)礦山進(jìn)行挖礦,再到終點(diǎn)；最后一種情況是既經(jīng)過(guò)礦山進(jìn)行挖礦,又經(jīng)過(guò)村莊進(jìn)行購(gòu)買(mǎi)（由于假設(shè)所限,只能購(gòu)買(mǎi)一次或者挖礦一次）。進(jìn)入村莊進(jìn)行購(gòu)買(mǎi)的目的很單純,即食物和水不足以支撐到游戲結(jié)束,而進(jìn)入礦山挖礦,可能有多重目的和情況：第一種情況是補(bǔ)給足夠,希望能夠多賺錢(qián),第二種情況是補(bǔ)給不夠,需要進(jìn)入礦山挖礦賺錢(qián),其后必經(jīng)過(guò)村莊購(gòu)買(mǎi)補(bǔ)給。這里又可以細(xì)分為兩種情況：第一種為原先補(bǔ)給是足夠的,然而挖礦消耗量大,導(dǎo)致補(bǔ)給不足,第二種情況是原先補(bǔ)給即不足以支撐游戲結(jié)束。Floyd 算法,又稱(chēng)為插點(diǎn)法,是一種利用動(dòng)態(tài)規(guī)劃的思想尋找給定的加權(quán)圖中多源點(diǎn)之間最短路徑的算法,與Dijkstra算法類(lèi)似。在此使用Floyd 算法,遍歷起點(diǎn)、終點(diǎn)、村莊、礦山等特殊元素之間的最短路徑。在到達(dá)終點(diǎn)的前提下,列出目標(biāo)函數(shù)：剩余資金=初始資金+挖礦收益+終點(diǎn)退回資金- 起點(diǎn)及村莊購(gòu)買(mǎi)補(bǔ)給的花費(fèi),即m=q+h+r-s-c,對(duì)所有情況進(jìn)行分類(lèi)討論,求解出目標(biāo)函數(shù)（資金剩余量）的最大值,即為最優(yōu)策略。

第二關(guān)僅有一名玩家,地圖中沒(méi)有村莊,不存在沙暴天氣而且只知道當(dāng)天的天氣情況。首先依然需要建立距離矩陣和隨機(jī)天氣矩陣。由于地圖邊界不規(guī)則,在此也采取人工遍歷的方式求出距離矩陣。概率天氣矩陣設(shè)置晴天的概率分別為0.2、0.5、0.8。由于本題目不含有村莊,故選擇元素時(shí)僅有兩種情況,第一種情況就是直接到達(dá)終點(diǎn),行走的天數(shù)是確定的（已知不存在沙暴天氣）,而天氣是未知的。通過(guò)設(shè)置概率天氣函數(shù),即可求出在設(shè)定概率下目標(biāo)函數(shù)值。第二種情況是經(jīng)過(guò)礦山,由于在晴朗天氣,挖礦一天盈利35 元,高溫天氣,挖礦一天需要虧損205 元,故若持續(xù)為晴朗天氣,則可連續(xù)挖礦,若有高溫天氣,則堅(jiān)決不挖礦,當(dāng)天立即離開(kāi)。

第四關(guān)與第三關(guān)模型類(lèi)似,僅僅是題目中給出了沙暴天氣出現(xiàn)的概率較小,故在概率矩陣設(shè)定時(shí),需要將沙暴天氣概率設(shè)置為較小即可,最后在時(shí)間截止之前到達(dá)終點(diǎn),而且在地圖中出現(xiàn)了村莊,這樣,本題可以?huà)侀_(kāi)假設(shè)1 和2,多次往返于村莊進(jìn)行補(bǔ)給和礦山進(jìn)行挖礦。分別按照不同天氣概率對(duì)直達(dá)終點(diǎn)和經(jīng)過(guò)礦山（無(wú)論是否挖礦）進(jìn)行目標(biāo)函數(shù)值的求解,最終可以比對(duì)出在不同概率條件下的最優(yōu)策略,由此可得,晴天的出現(xiàn)有助于玩家在礦山處通過(guò)挖礦獲得較大收益。

第五關(guān)共有兩位玩家進(jìn)行游戲,最先注意要避免的問(wèn)題是兩位玩家在同一天有相同的行程或者進(jìn)行相同的操作。所以在本關(guān)中,依舊使用Floyd 算法遍歷元素之間的最短路徑之后,兩位玩家對(duì)幾種不同的最短路徑進(jìn)行排列組合,求得此時(shí)的目標(biāo)函數(shù)值。若組合之間有路程或操作的重合,則在某位玩家路線(xiàn)做細(xì)微擾動(dòng),比較前后的目標(biāo)函數(shù)值,進(jìn)行討論。

第六關(guān)理論上有兩種討論方法,都是博弈論的相關(guān)內(nèi)容,第一種情況是玩家是敵對(duì)的,這里需要求解納什均衡的問(wèn)題。納什均衡,即非合作博弈均衡,也就是無(wú)論對(duì)方的策略選擇如何,當(dāng)事人一方都會(huì)選擇某個(gè)確定的策略。這種情況保證自己利益的最大化,因此在這種均衡狀態(tài)下各個(gè)人應(yīng)該是余額一致的,選一種各自余額最高的均衡狀態(tài)即可；第二種情況是玩家可以相互之間合作,那就是帕累托最優(yōu)問(wèn)題,帕累托最優(yōu),也即帕累托效率,是指資源分配的一種理想狀態(tài),最后選擇一種各位玩家余額最接近的情況即可。本文貫穿始終的Floyd 算法是本文的一大特點(diǎn),另外通過(guò)合理的假設(shè),也使得各問(wèn)題得以大大簡(jiǎn)化。全文各新舊模型的綜合運(yùn)用,令全文思路清晰,條理分明,充滿(mǎn)了創(chuàng)新性。最后,縱觀全文,客觀的評(píng)價(jià)了模型的優(yōu)劣并進(jìn)行了模型的延伸。綜合考慮到模型具有的優(yōu)化功能,可以將其推廣至物流、運(yùn)輸?shù)戎匾I(lǐng)域。這對(duì)今后資源的節(jié)約以及社會(huì)經(jīng)濟(jì)效益的提高具有重要的參考價(jià)值。

3 結(jié)論

本文所涉及到的多種模型,針對(duì)規(guī)劃穿越沙漠路徑中最優(yōu)路徑的問(wèn)題,提出一種基于最短路徑規(guī)劃算法,并通過(guò)增加天氣情況、物資和礦山等不確定性情況,建立基于以上因素影響下最優(yōu)路徑,通過(guò)圖論的比較,在不同方案中尋找效果最好的方案。結(jié)果表明,在天氣已知的情況下,所建立的數(shù)學(xué)模型較為靈活,仿真結(jié)果表明,此數(shù)學(xué)模型算法有較強(qiáng)的實(shí)用性,可以推廣至物流、運(yùn)輸?shù)戎匾I(lǐng)域,這對(duì)今后的資源節(jié)約以及社會(huì)經(jīng)濟(jì)效益的提高具有重要的參考價(jià)值。