“穿越沙漠”最優(yōu)策略研究

“穿越沙漠”最優(yōu)策略研究摘要；本文借助馬爾可夫決策模型、蒙特卡羅算法、迪杰斯特拉算法對2020年數(shù)學建模競B題“穿越沙漠”問題進行研究，在不同關(guān)卡設定下，通過動態(tài)規(guī)劃給出規(guī)定時間到達目的地并盡可能多獲得資金的最優(yōu)策略。關(guān)鍵詞：馬爾可夫決策迪杰斯特拉蒙特卡羅博弈論動態(tài)規(guī)劃一、問題重述玩家用初始資金購買一定的必需資源，在天氣多變（晴朗、高溫、沙暴）的沙漠從起點出發(fā)，途中可以在礦山或村莊補充資金和資源。游戲目標是在規(guī)定時間到達終點的同時保留盡可能多的資金。游戲規(guī)則如下：(1)基本時間單位為天，玩家位于起點時為第0天且必須在規(guī)定時間內(nèi)到達終點才能結(jié)束該玩家的比賽。(2)以箱作為必需資源的最小計量單位，玩家每天的資源質(zhì)量不能超過最高負重，一旦在到達終點前耗盡資源則游戲失敗。在起點以基準價格購買必需資源且只能購買一次，在游戲中玩家可以選擇返回起點或在起點停留一段時間。在到達終點時，玩家可以以基準價格的一半退回剩余資源。(3)每天玩家可以原地停留也可以行走到鄰近的區(qū)域內(nèi)，整頓一天消耗資源數(shù)為基礎消耗量；行走需消耗資源，消耗數(shù)量為基礎消耗量的兩倍。當遇到沙暴時必須在原地整頓。(4)如果玩家到達礦山時，可以選擇挖礦賺取資金，沙暴天氣也可挖礦，但到達的第一天不可挖礦。挖礦每天消耗的資源為基礎消耗量的三倍，每天的賺得的資金為基礎收益；不挖礦時資源消耗量為基礎消耗量。玩家在村莊可以用現(xiàn)有資金補充資源，資源價格為基準價格的兩倍。需解決的問題：問題一：已知每天天氣狀況，假設只有一名玩家參與游戲，給出該玩家的最優(yōu)游戲策略。并對第一關(guān)、第二關(guān)進行求解，將結(jié)果填入Result.xlsx。問題二：假設只有一名玩家參與，玩家僅當天天氣狀況，以此決定每天行動策略。給出該玩家應采取的最優(yōu)策略，針對第三關(guān)、第四關(guān)進行具體分析。問題三：現(xiàn)有擁有相同的初始資金的名玩家同時從起點出發(fā)，若某天有名玩家從同一區(qū)域進入另一相同區(qū)域，則這名玩家的資源消耗量均為基礎消耗量的倍；若某天有名玩家在同一礦山挖礦，則該名玩家的資源消耗量均為基礎消耗量的三倍且每天的收益均為基礎收益的；若某天有名玩家在同一村莊補充資源，則資源價格為基準價格的4倍。其他情況下資源的價格和消耗量不變。(1)假設每天天氣情況均已知，各玩家的方案在起點確定且不可更改，給出玩家應采取的行動策略，針對第五關(guān)進行具體分析。(2)假設僅知道當天的天氣情況，從第一天開始，在每天結(jié)束后玩家均可知道其他玩家當天的策略和剩余資源，并確定第二天的策略。給出玩家采取的行動策略，針對第六關(guān)進行具體分析。二、問題假設1、假設沙漠中除題目給定天氣情況外無其他突發(fā)自然災害。2、假設每名玩家的身體情況相同且無突發(fā)疾病。3、假設第四關(guān)中僅出現(xiàn)一次沙暴天氣。4、假設第六關(guān)中忽略沙暴天氣的影響。三、模型的建立與求解游戲目標是為了到達終點時使資金最大化，以此為出發(fā)點對玩家的資金來源進行。3.1已知每天天氣的最優(yōu)策略不管選擇哪種方式都是通過最短路徑到達目的地，可以通過將題目所給地圖轉(zhuǎn)化為鄰接矩陣后使用迪杰斯特拉算法[2]即可求出兩點之間的最短路徑3.1.1起點-終點路線該路線表示不選擇進入礦山挖礦賺取資金。在趕路時玩家可以選擇在某一點“等待”便于以“合理時機”進入系統(tǒng)。從而使選擇該路線的資金最大化。3.1.2起點-礦山-終點路線選擇該路線表示玩家想在趕路的同時通過挖礦來增加資金金額。該路線有兩種策略可選擇：1.在起點處購買恰好足夠玩家挖礦、趕路和最后到達終點需要的資源數(shù)。2.在起點處先購買恰好足夠玩家從起點到礦山、挖礦和從礦山到達村莊的資源，在村莊再補充恰好足夠玩家回礦山挖礦一段時間的資源（可能多次補充），最后一次補充恰好足夠玩家最后到達終點所需要的資源。3.1.3起點-村莊-礦山-村莊-終點路線此路線玩家有兩種策略供選擇：1.在保留恰好到達村莊所需資源的情況下，補充到終點的最短路徑下所需的資源。2.返回村莊補充能夠使玩家回礦山挖礦一段時間和最后到達終點所需的資源。3.1.4針對第一關(guān)、第二關(guān)的求解1、起點-終點省錢路線根據(jù)兩關(guān)分別的最短路徑本文采用線性規(guī)劃[2]的對不同關(guān)卡的最終資金進行求解：第一關(guān)的線性規(guī)劃方程：第二關(guān)的線性規(guī)劃方程：最終得到兩關(guān)最終資金2、礦山賺錢路線由于起點-礦山-終點路線的收益與起點-村莊-礦山-村莊-終點路線的收益可比性太低，所以這里僅對后者進行具體分析。第二關(guān)礦山與村莊相鄰，所以對挖礦結(jié)束去村莊補充資源后返回礦山繼續(xù)挖礦的兩種策略作不同分析。3.2僅知每天天氣的最優(yōu)策略穿越沙漠的策略一共有兩種：1.以省錢為目的直接在合理時機下以最短路徑從起點到終點來達到資金最大化。2.經(jīng)過合理時機進出礦山通過賺錢的方式來達到資金最大化。兩種方式在僅知當天天氣的情況下，要對未來天氣進行預測。為了簡化運算，本文只針對每種路線的最短路徑的天氣進行蒙特卡羅[2]模擬（選擇最短路徑是確保規(guī)定時間內(nèi)到達終點剩余更多資金）。用模擬出的天氣情況可以得出資金的期望值，將其均值化，再將每種路線進行比較，最終即可得到所有天氣中的最優(yōu)策略為，可作為比較的基本方程。3.2.1針對省錢方式的策略消耗資金數(shù)：最終資金期望：3.2.2針對挖礦方式的策略1、起點-礦山-終點在礦山中消耗資源數(shù)平均消耗量：所以挖礦天數(shù)的計算公式為：最終資金期望：2、起點-礦山-村莊-終點挖礦時長的求解公式：最終資金期望為：3.3名玩家的游戲策略3.3.1兩名玩家在起點確定的游戲策略該問題可以由博弈論中的囚徒困境來進行模擬，為得到最優(yōu)策略，兩者為達到全局最優(yōu)解必須做出讓步，找出起點-終點的所有路徑，在其中選出兩條除最短路徑之外的路徑中最優(yōu)的路徑。3.3.2三名玩家在行動前一天確定的游戲策略本題將狀態(tài)空間分為起點-礦山，礦山-終點兩種。針對起點-礦山、礦山-終點的路線，使用馬爾可夫決策模型[4]中的懲罰函數(shù)進行路線決策，同時利用蒙特卡羅對各路線天氣進行預測。馬爾可夫決策模型中：狀態(tài)空間

狀態(tài)空間包括玩家活動區(qū)域內(nèi)動態(tài)實體的所有可能描述信息，本文將狀態(tài)空間定義周圍其它玩家的空間存在狀態(tài)。2、完結(jié)條件

行為決策過程中，迭代過程的結(jié)束需要一個終止狀態(tài)來判斷，本文選取下述情況作為結(jié)束標志：當?shù)竭_終點時為結(jié)束，馬爾可夫過程不再進行迭代。3、懲罰函數(shù)

玩家相遇：造成資源浪費。故玩家路線重疊時，作為懲罰函數(shù)。

玩家避免相遇而選擇繞路：造成資源浪費。故作為懲罰函數(shù)4、運動動作

由題意可知，玩家進行下一步的運動時，目的是到達終點，在二維化的地圖中，起點與礦山、礦山與終點均在特定矩形的主對角線上，故運動動作只三種情況：

向下

不動

向右。5、動作值函數(shù)

動作值函數(shù)是一個遞歸函數(shù)，首先檢測當前狀態(tài)是否到達終止狀態(tài)，若未達到遞歸結(jié)束條件，則執(zhí)行狀態(tài)轉(zhuǎn)移方程，若達到則結(jié)束遞歸，然后判斷當前迭代次數(shù)是否達到

T，若達到則結(jié)束遞歸，否則對所有可能的動作進行循環(huán)計算。

經(jīng)過以上迭代之后，得到的路線即為在一般情況下玩家要選擇的一般策略。參考文獻[1]嵇冉,王健.生活中的“囚徒困境”[J].中國統(tǒng)計,20