柳 堰 唐龍海 梁曉瑞

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

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

1 問題分析

首先利用基于Floyd 算法,得出目標(biāo)函數(shù),即到達(dá)終點所剩資金（包含退還食物和水的資金）的最大值的路徑即為最優(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)路徑之后,使兩位玩家盡量避免相同行程和相同的行為,最后對每種組合方式進(jìn)行分類討論。

2 模型的建立與求解

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

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

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

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

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

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

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

第六關(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)劣并進(jìn)行了模型的延伸。綜合考慮到模型具有的優(yōu)化功能,可以將其推廣至物流、運輸?shù)戎匾I(lǐng)域。這對今后資源的節(jié)約以及社會經(jīng)濟(jì)效益的提高具有重要的參考價值。

3 結(jié)論

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