目錄
- 前言
- 原題
- 關鍵詞
- 目標
- 問題一分析
- 問題二分析
- 問題三分析
- 比賽后的一些些感想
前言
本人小白，求大佬們放過！本篇文章介紹我們小組撰寫B題的思路，如有不足歡迎批評指正！
原題
考慮如下的小游戲：玩家憑借一張地圖，利用初始資金購買一定數量的水和食物（包括食品和其他日常用品），從起點出發，在沙漠中行走，途中會遇到不同的天氣，也可在礦山、村莊補充資金或資源，目標是在規定時間內到達終點，并保留盡可能多的資金，
游戲的基本規則如下：
（1）以天為基本時間單位，游戲的開始時間為第0天，玩家位于起點，玩家必須在截止日期或之前到達終點，到達終點后該玩家的游戲結束，
（2）穿越沙漠需水和食物兩種資源，它們的最小計量單位均為箱，每天玩家擁有的水和食物質量之和不能超過負重上限，若未到達終點而水或食物已耗盡，視為游戲失敗，
（3）每天的天氣為“晴朗”、“高溫”、“沙暴”三種狀況之一，沙漠中所有區域的天氣相同，
（4）每天玩家可從地圖中的某個區域到達與之相鄰的另一個區域，也可在原地停留，沙暴日必須在原地停留，
（5）玩家在原地停留一天消耗的資源數量稱為基礎消耗量，行走一天消耗的資源數量為基礎消耗量的 倍，
（6）玩家第0天可在起點處用初始資金以基準價格購買水和食物，玩家可在起點停留或回到起點，但不能多次在起點購買資源，玩家到達終點后可退回剩余的水和食物，每箱退回價格為基準價格的一半，
（7）玩家在礦山停留時，可通過挖礦獲得資金，挖礦一天獲得的資金量稱為基礎收益，如果挖礦，消耗的資源數量為基礎消耗量的 倍；如果不挖礦，消耗的資源數量為基礎消耗量，到達礦山當天不能挖礦，沙暴日也可挖礦，
（8）玩家經過或在村莊停留時可用剩余的初始資金或挖礦獲得的資金隨時購買水和食物，每箱價格為基準價格的2倍，
請根據游戲的不同設定，建立數學模型，解決以下問題，
- 假設只有一名玩家，在整個游戲時段內每天天氣狀況事先全部已知，試給出一般情況下玩家的最優策略，求解附件中的“第一關”和“第二關”，并將相應結果分別填入Result.xlsx，
- 假設只有一名玩家，玩家僅知道當天的天氣狀況，可據此決定當天的行動方案，試給出一般情況下玩家的最佳策略，并對附件中的“第三關”和“第四關”進行具體討論，
- 現有 名玩家，他們有相同的初始資金，且同時從起點出發，若某天其中的任意 名玩家均從區域A行走到區域B( )，則他們中的任一位消耗的資源數量均為基礎消耗量的 倍；若某天其中的任意 名玩家在同一礦山挖礦，則他們中的任一位消耗的資源數量均為基礎消耗量的 倍，且每名玩家一天可通過挖礦獲得的資金是基礎收益的 ；若某天其中的任意 名玩家在同一村莊購買資源，每箱價格均為基準價格的 倍，其他情況下消耗資源數量與資源價格與單人游戲相同，
（1）假設在整個游戲時段內每天天氣狀況事先全部已知，每名玩家的行動方案需在第 天確定且此后不能更改，試給出一般情況下玩家應采取的策略，并對附件中的“第五關”進行具體討論，
（2）假設所有玩家僅知道當天的天氣狀況，從第 天起，每名玩家在當天行動結束后均知道其余玩家當天的行動方案和剩余的資源數量，隨后確定各自第二天的行動方案，試給出一般情況下玩家應采取的策略，并對附件中的“第六關”進行具體討論，
注1：附件所給地圖中，有公共邊界的兩個區域稱為相鄰，僅有公共頂點而沒有公共邊界的兩個區域不視作相鄰，
注2：Result.xlsx中剩余資金數（剩余水量、剩余食物量）指當日所需資源全部消耗完畢后的資金數（水量、食物量），若當榷訓有購買行為，則指完成購買后的資金數（水量、食物量），
關鍵詞
動態規劃模型、博弈樹、蒙特卡洛仿真模型、最優化原理
目標
在規定時間內到達終點，并保留盡可能多的資金，注意是錢！不是盡快跑出沙漠！
問題一分析
題目給出了近30天的天氣情況，所以玩家走出沙漠后身上剩余的資金是個定值，而我們要求的就是這個定值的最大值，因為整個游戲程序中，有礦山和村莊這兩個特殊點，所以不能用平時學的最短路徑來求解了，但可以將整個游戲分為若干階段：第一階段是玩家從起點出發到村莊或礦山的路徑；第二階段是玩家在村莊和礦山來回的路徑；第三階段是玩家從村莊或礦山出發到終點的路徑，而第一階段和第三階段可以利用動態規劃求解，第二階段根據運籌學原理，計算出在村莊與礦山的時間分配以及受天氣影響在起點應該購買的物資，整個階段可以通過設定變數，求解出目標利益函式，分析函式曲線，找出最優解，
問題二分析
相較與問題一，問題二的天氣未知，所以最后求出的結果也不是個定值，可以分類討論，各種天氣的出現比例給出不同的解決方案，同問題一，將整個游戲分為若干階段，對最終結果影響最大的天氣是沙暴，所以我們在確定天氣出現比率時候，需要將沙暴出現的位置（第幾階段）進行分類討論，而不是對接下來一天可能是哪種天氣進行分類討論（這樣就算復雜了），之后根據當天的天氣以及玩家身上所剩下的資源數和游戲地圖來規劃后面的路線，對不同天氣應進行分類討論，采用分支界限法，并進行剪枝處理來降低計算量，
問題三分析
較大的變化是，游戲可以有多名玩家參與，而每個人的目標依然是使自己利益最大化，也就不存在犧牲小我，成就大我的那種情況，也不會干損人不利己的事，多玩家參與的游戲相對于一名玩家參與的游戲而言，原來設定的最佳路徑會因為該路徑上有其它玩家而選擇原地等待或改變路徑，每名玩家需要根據博弈論的原理，以其他玩家剩余水和食物資源的數量以及離礦山或村莊的位置為依據，來推測該名玩家下一步的行動方案，因為未來天氣依然未知，這里使用蒙特卡洛仿真模型實作對不同比例天氣的模擬，玩家在對應天氣下依據博弈論原理進行選擇，（蒙特卡洛仿真，博弈樹均可用編程語言實作，我們用的是JAVA語言，寫了三百行左右）
比賽后的一些些感想
往年也參加過一次國賽，那時沒有基礎，也沒怎么畫心思去學，比賽的時候連模型都記不全，到處找文獻，選取片段，改改資料，東拼西湊的拼了一篇論文，最后連自己寫的是什么都不知道，你可能會問這肯定查重就過不去，對，查重率是很高，那就改句型！換詞！所以比賽結果也是意料之中的，得了安慰獎，現在知道我這小白是有多白了吧！
這次比賽準備了一個月，選題的時候，三人咬定不選C題，主觀性太強，怕到時候自己又是把別人文獻照搬過來堆出一篇論文，干著和一年前一樣的事，那么這次比賽也沒有任何意義了，因為興趣我們選擇了B題，也沒管它難不難，個人認為興趣能激發一個人解決問題的潛力，選定B題之前，認為B題只是個圖論和最短路徑而已，以前也接觸過這類問題，解決起來應該不難，選定B題之后，光是這個礦山和村莊就把人搞得頭疼，第六關的多人游戲就更是復雜，反正就是難，在這次比賽前，我們想都沒想過會用計算機編程語言來求解建模問題，而我個人比較擅長的是JAVA，把整個問題改寫成演算法題，貌似就不是很難了，代碼大致思路是這樣的：三個人從起點出發，開起三個執行緒，控制天氣比例后用隨機函式給出每天的天氣，每個人都用博弈樹思想來規劃路徑，每種天氣比例重復試驗一萬次得出平均結果，最后提交論文的時候真的挺欣慰的，至少讓自己感覺到是真解決了問題的，結果怎樣不重要，享受程序就好，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/46095.html
標籤：其他
上一篇：【資料結構與演算法】-＞演算法-＞字串匹配基礎（中）-＞BM演算法-＞KMP 三倍性能的強大演算法
下一篇：冷冰冰的，是演算法，還是人心