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

柳 堰 唐龍海 梁曉瑞

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

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

1 問題分析

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

2 模型的建立與求解

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

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

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

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

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

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

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

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

3 結(jié)論

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