数学建模2020B题穿越沙漠
生活随笔
收集整理的這篇文章主要介紹了
数学建模2020B题穿越沙漠
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
1.題目
考慮如下的小游戲：玩家憑借一張地圖，利用初始資金購買一定數(shù)量的水和食物（包括食品和其他日常用品），從起點出發(fā)，在沙漠中行走。途中會遇到不同的天氣，也可在礦山、村莊補充資金或資源，目標是在規(guī)定時間內(nèi)到達終點，并保留盡可能多的資金。
游戲的基本規(guī)則如下：
（1）以天為基本時間單位，游戲的開始時間為第0天，玩家位于起點。玩家必須在截止日期或之前到達終點，到達終點后該玩家的游戲結(jié)束。
（2）穿越沙漠需水和食物兩種資源，它們的最小計量單位均為箱。每天玩家擁有的水和食物質(zhì)量之和不能超過負重上限。若未到達終點而水或食物已耗盡，視為游戲失敗。
（3）每天的天氣為“晴朗”、“高溫”、“沙暴”三種狀況之一，沙漠中所有區(qū)域的天氣相同。
（4）每天玩家可從地圖中的某個區(qū)域到達與之相鄰的另一個區(qū)域，也可在原地停留。沙暴日必須在原地停留。
（5）玩家在原地停留一天消耗的資源數(shù)量稱為基礎消耗量，行走一天消耗的資源數(shù)量為基礎消耗量的倍。
（6）玩家第0天可在起點處用初始資金以基準價格購買水和食物。玩家可在起點停留或回到起點，但不能多次在起點購買資源。玩家到達終點后可退回剩余的水和食物，每箱退回價格為基準價格的一半。
（7）玩家在礦山停留時，可通過挖礦獲得資金，挖礦一天獲得的資金量稱為基礎收益。如果挖礦，消耗的資源數(shù)量為基礎消耗量的倍；如果不挖礦，消耗的資源數(shù)量為基礎消耗量。到達礦山當天不能挖礦。沙暴日也可挖礦。
（8）玩家經(jīng)過或在村莊停留時可用剩余的初始資金或挖礦獲得的資金隨時購買水和食物，每箱價格為基準價格的2倍。
請根據(jù)游戲的不同設定，建立數(shù)學模型，解決以下問題。
2.解題思路與第一關(guān)與第二關(guān)
有三大種思路
1.動態(tài)規(guī)劃
2.簡略地圖后使用Dijkstra算法來解決
3.分析題干然后建立模型利用groubi,lingo求解最優(yōu)解
2.1 動態(tài)規(guī)劃情況
設狀態(tài)dp[k][j][w][f]代表第k天時在第j個點剩余水為w箱剩余食物為f箱的最大資金，則：
ans=MAXw,f,i dp[k][zd][w][f]
2.1.1 初始值設定
由于起始點可以在起點購買物資，則有初始狀態(tài)
dp[0][qd][w][f]=10000?cost_water?w?cost_food?fw∈[0,400]f∈[0,600]
其中cost_water??，cost_food???? 為購買水和食物消耗的錢。
這里假設起始為第0天，則第一天天氣影響的是從第0天到第1天。
2.1.2 狀態(tài)轉(zhuǎn)移方程
當?shù)趉天人在村莊j時：
當?shù)趉天人在礦山j時：
挖礦
第k天為沙暴天氣：
dp[k+1][j][w-xh_water[tq]][f-xh_food[tq]]=max(dp[k][j][w][f])第k天為非沙暴天氣：
dp[k+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]=max(dp[k][jj][w][f])當?shù)趉天人在其他地區(qū)時
第k天為沙暴天氣：
第k天為非沙暴天氣：
dp[k][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]=max(dp[k][j][w][f])2.1.3思考隱含條件約束模型
除了回村莊補充物資，不會走回頭路。
除了挖礦和沙塵暴不會在原地停留。
只會走關(guān)鍵點之間的最短路徑
2.1.4代碼
第一關(guān)
#include<bits/stdc++.h> #include<iostream> using namespace std;// 點數(shù) const int N=11,M=28,inf=0x3f3f3f,Day=30; int dp[32][N+1][405][605],zd,qd,FZ; int cost_water,cost_food,walk,dig,buy; int xh_water[3]={5,8,10},xh_food[3]={7,6,10}; bool cz[N+1],ks[N+1];struct node {short day; // i short from; // jj jint water,food;int money;bool operator!=(const node &x){return x.day!=day || x.from!=from || x.water!=water || x.food!=food ;}; }path[31][N+1][405][605],lastpath; vector <int> weather; vector <int> g[N]; map <int,int> mp; void push_back(int x,int y) {g[x].push_back(y);g[y].push_back(x); }void build_map() {push_back(1,2);push_back(2,3);push_back(2,5);push_back(5,6);push_back(3,4);push_back(4,7);push_back(6,7);push_back(7,8);push_back(8,9);push_back(9,10);push_back(10,11);mp[1]=1;mp[2]=25;mp[3]=26;mp[4]=27;mp[5]=24;mp[6]=23;mp[7]=21;mp[8]=9;mp[9]=15;mp[10]=14;mp[11]=12;for(int i=1;i<=N;i++){cz[i]=0;ks[i]=0;}cz[9]=1;ks[11]=1;zd=4;qd=1;return ; } void init() {memset(dp,-inf,sizeof(dp));FZ=1200;cost_water=5;cost_food=10;walk=2;buy=2;dig=3;for(int k=0;k<=405;k++){for(int l=0;l<=601;l++){if(k*3+l*2<=FZ){dp[0][qd][k][l]=10000-k*cost_water-l*cost_food;}}}printf("init %d\n",dp[0][1][178][333]);path[0][1][0][0]={0,0,0,0};return ; } int main() {weather={1,1,0,2,0,1,2,0,1,1,2,1,0,1,1,1,2,2,1,1,0,0,1,0,2,1,0,0,1,1,};build_map();init();for(int i=0;i<Day;i++){printf("第%d天\n",i);int tq=weather[i];for(int j=1;j<=N;j++){if(cz[j])// 村莊{for(int w=0;w<=405;w++){for(int f=0;w*3+f*2<=1200;f++){//購買或不夠買物資(ww=0,ff=0就是不購買) if(tq==2) //停留{int money=dp[i][j][w][f];for(int ww=0;ww<=money/cost_water;ww++){for(int ff=0;ff<=(FZ-(w+ww)*3)/2-f;ff++){if(w+ww-xh_water[tq]>=0&&f+ff-xh_food[tq]>=0&&dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food>=0){if(dp[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]<dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food){dp[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]=dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food;path[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]={i,j,w,f,dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food};}}}}}else //從j走到jj{for(auto jj:g[j]){int money=dp[i][j][w][f];for(int ww=0;ww<=money/cost_water;ww++){for(int ff=0;ff<=(FZ-(w+ww)*3)/2-f;ff++){if(w+ww-walk*xh_water[tq]>=0&&f+ff-walk*xh_food[tq]>=0&&dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food>=0){if(dp[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]<dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food){dp[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]=dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food;path[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]={i,j,w,f,dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food};}}}}}}}}}else if (ks[j])// 礦山{for(int w=0;w<=405;w++){for(int f=0;w*3+f*2<=1200;f++){// 已經(jīng)停留一天了，可以挖礦if(w-dig*xh_water[tq]>=0&&f-dig*xh_food[tq]>=0){if(dp[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]<dp[i][j][w][f]+1000&&dp[i][j][w][f]>=0){dp[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]=dp[i][j][w][f]+1000;path[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]={i,j,w,f,dp[i][j][w][f]+1000};}}// 在礦山不挖礦或 不允許挖礦if(tq==2) //停留但不挖礦{if(w-xh_water[tq]>=0&&f-xh_food[tq]>=0){if(dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]<dp[i][j][w][f]&&dp[i][j][w][f]>=0){dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]=dp[i][j][w][f];path[i+1][j][w-xh_water[tq]][f-xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};}}}else{if(w-walk*xh_water[tq]>=0&&f-walk*xh_food[tq]>=0){for(auto jj:g[j]){if(dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]<dp[i][j][w][f]&&dp[i][j][w][f]>=0){dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]=dp[i][j][w][f];path[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};}}}}}}}else //普通區(qū){for(int w=0;w<=405;w++){for(int f=0;w*3+f*2<=1200;f++){if(tq==2) //在j點停留{if(w-xh_water[tq]>=0&&f-xh_food[tq]>=0&&dp[i][j][w][f]>=0){if(dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]<dp[i][j][w][f]){dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]=dp[i][j][w][f];path[i+1][j][w-xh_water[tq]][f-xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};}}}else// 走到jj點{for(auto jj:g[j]){if(w-walk*xh_water[tq]>=0&&f-walk*xh_food[tq]>=0&&dp[i][j][w][f]>=0){if(dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]<dp[i][j][w][f]){dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]=dp[i][j][w][f];path[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};}}}}}}}}}int ans=-inf;node lastpath;int last_water=0,last_food=0,last_day=Day;for(int i=0;i<=Day;i++){for(int w=0;w<=405;w++)for(int f=0;w*3+2*f<=1200;f++){if(dp[i][zd][w][f]>ans){ans=dp[i][zd][w][f];lastpath=path[i][zd][w][f];last_water=w;last_food=f;last_day=i;}}}stack<node> s;stack<int> my;printf("??day:%d weather:%d %d water:%d food:%d money:%d\n",last_day,weather[Day],zd,last_water,last_food,ans);s.push((node){last_day,zd,last_water,last_food,ans});while(lastpath!=path[0][1][0][0]){s.push(lastpath);printf("??day:%d weather:%d %d water:%d food:%d money:%d\n",lastpath.day,weather[lastpath.day],mp[lastpath.from],lastpath.water,lastpath.food,lastpath.money);my.push(lastpath.money);lastpath=path[lastpath.day][lastpath.from][lastpath.water][lastpath.food];}freopen("output.txt","w",stdout);my.push(my.top());while (!s.empty()){node t=s.top();int money=my.top();printf("Day:%d weather:%d point:%d water:%d food:%d money:%d\n",t.day,weather[t.day],mp[t.from],t.water,t.food,money);s.pop();my.pop();}printf("%d\n",ans);return 0; }第二關(guān)
#include<bits/stdc++.h> #include<iostream> using namespace std;const short N=27,inf=20000,Day=30; short dp[31][N+1][401][601],zd,qd,FZ; short cost_water,cost_food,walk,dig,buy; short xh_water[3]={5,8,10},xh_food[3]={7,6,10}; bool cz[N+1],ks[N+1];struct node {char day; // i char from; // jj jshort water,food;bool operator!=(const node &x){return (x.day-'0')!=(day-'0') || (x.from-'0'!=from-'0') || (x.water-'0')!=(water-'0') || (x.food-'0'!=food-'0') ;}; }path[31][N+1][401][601],lastpath; vector <short> weather; vector <short> g[N+1]; map <short,short> mp; void push_back(short x,short y) {g[x].push_back(y);g[y].push_back(x); }void build_map(short flag) {if(flag==2){push_back(1,2);push_back(2,3);push_back(3,4);push_back(4,5);push_back(5,6);push_back(6,7);push_back(7,8);push_back(8,9);push_back(9,10);push_back(10,11);push_back(11,12);push_back(7,13);push_back(13,14);push_back(14,15);push_back(15,16);push_back(15,10);push_back(15,11);push_back(16,12);push_back(3,17);push_back(17,18);push_back(18,19);push_back(19,20);push_back(20,21);push_back(21,22);push_back(22,23);push_back(15,23);push_back(23,16);mp[1]=1;mp[2]=2;mp[3]=3;mp[4]=4;mp[5]=12;mp[6]=21;mp[7]=29;mp[8]=30;mp[9]=39;mp[10]=47;mp[11]=56;mp[12]=64;mp[13]=38;mp[14]=46;mp[15]=55;mp[16]=63;mp[17]=11;mp[18]=20;mp[19]=28;mp[20]=37;mp[21]=45;mp[22]=54;mp[23]=62;for(short i=1;i<=N;i++){cz[i]=0;ks[i]=0;}cz[9]=cz[23]=1;ks[8]=ks[15]=1;qd=1;zd=12;}return ; }void init() {FZ=1200;cost_water=5;cost_food=10;walk=2;buy=2;dig=3;for(short i=0;i<=Day;i++){for(short j=1;j<=N;j++){for(short w=0;w<=400;w++){for(short f=0;f<=600;f++){if(w*3+f*2<=FZ){dp[i][j][w][f]=-inf;}}}}}for(short k=10;k<=405;k++){for(short l=0;k*3+l*2<=FZ;l++){dp[0][qd][k][l]=10000-k*cost_water-l*cost_food;}}path[0][1][0][0]={0,0,0,0};return ; }int main() {weather={1,1,0,2,0,1,2,0,1,1,2,1,0,1,1,1,2,2,1,1,0,0,1,0,2,1,0,0,1,1,};build_map(2);init();// dp [i][j][w][f]// 第i天 在j個點 w 箱水 f 箱食物 時最大利潤，// max_k_l (dp[30][27][k][l])// 第i天的天氣決定 i+1天能否移動// 如：第0天天氣決定第1天能否移動// 先不考慮非礦山停留自愿停留情況// for(short i=1;i<N;i++)// {// printf("第%d個點",i);// for(auto j:mp[i]) // {// printf("%d ",j);// }// printf("\n");// }// printf("???%d %d %d %d\n",xh_food[0],xh_food[2],xh_water[0],xh_water[1]);for(short i=0;i<Day;i++){printf("第%d天\n",i);short tq=weather[i];for(short j=1;j<=N;j++){if(cz[j])// 村莊{for(short w=0;w<=405;w++){for(short f=0;w*3+f*2<=1200;f++){//購買或不夠買物資(ww=0,ff=0就是不購買) if(tq==2) //停留{short money=dp[i][j][w][f];for(short ww=0;ww<=money/cost_water;ww++){for(short ff=0;ff<=(FZ-(w+ww)*3)/2-f;ff++){if(w+ww-xh_water[tq]>=0&&f+ff-xh_food[tq]>=0&&dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food>=0){if(dp[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]<dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food){dp[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]=dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food;// path[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]={i,j,w,f,dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food};path[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]={i,j,w,f};}}}}}else //從j走到jj{for(auto jj:g[j]){short money=dp[i][j][w][f];for(short ww=0;ww<=money/cost_water;ww++){for(short ff=0;ff<=(FZ-(w+ww)*3)/2-f;ff++){if(w+ww-walk*xh_water[tq]>=0&&f+ff-walk*xh_food[tq]>=0&&dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food>=0){if(dp[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]<dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food){dp[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]=dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food;// path[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]={i,j,w,f,(short)dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food};path[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]={i,j,w,f};}}}}}}}}}else if (ks[j])// 礦山{for(short w=0;w<=405;w++){for(short f=0;w*3+f*2<=1200;f++){// 已經(jīng)停留一天了，可以挖礦if(w-dig*xh_water[tq]>=0&&f-dig*xh_food[tq]>=0){if(dp[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]<dp[i][j][w][f]+1000&&dp[i][j][w][f]>=0){dp[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]=dp[i][j][w][f]+1000; // path[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]={i,j,w,f,(short)dp[i][j][w][f]+1000};path[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]={i,j,w,f};}}// 在礦山不挖礦或 不允許挖礦if(tq==2) //停留但不挖礦{if(w-xh_water[tq]>=0&&f-xh_food[tq]>=0){if(dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]<dp[i][j][w][f]&&dp[i][j][w][f]>=0){dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]=dp[i][j][w][f];// path[i+1][j][w-xh_water[tq]][f-xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};path[i+1][j][w-xh_water[tq]][f-xh_food[tq]]={i,j,w,f};}}}else{if(w-walk*xh_water[tq]>=0&&f-walk*xh_food[tq]>=0){for(auto jj:g[j]){if(dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]<dp[i][j][w][f]&&dp[i][j][w][f]>=0){dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]=dp[i][j][w][f];// path[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};path[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]={i,j,w,f};}}}}}}}else //普通區(qū){for(short w=0;w<=405;w++){for(short f=0;w*3+f*2<=1200;f++){if(tq==2) //在j點停留{if(w-xh_water[tq]>=0&&f-xh_food[tq]>=0&&dp[i][j][w][f]>=0){if(dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]<dp[i][j][w][f]){dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]=dp[i][j][w][f];// path[i+1][j][w-xh_water[tq]][f-xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};path[i+1][j][w-xh_water[tq]][f-xh_food[tq]]={i,j,w,f};}}}else// 走到jj點{for(auto jj:g[j]){if(w-walk*xh_water[tq]>=0&&f-walk*xh_food[tq]>=0&&dp[i][j][w][f]>=0){if(dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]<dp[i][j][w][f]){dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]=dp[i][j][w][f];// path[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};path[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]={i,j,w,f};}}}}}}}}}short ans=-inf;node lastpath;short last_water=0,last_food=0,last_day=Day;for(short i=0;i<=Day;i++){for(short w=0;w<=405;w++)for(short f=0;w*3+2*f<=1200;f++){if(dp[i][zd][w][f]>ans){ans=dp[i][zd][w][f];lastpath=path[i][zd][w][f];last_water=w;last_food=f;last_day=char(i);}}}stack<node> s; // freopen("outputQ2.txt","w",stdout);printf("ans:%d\n",ans);printf("day:%d weather:%d point:%d water:%d food:%d\n",last_day,weather[Day],zd,last_water,last_food);node temppath=(node){last_day,zd,last_water,last_food};s.push(temppath);while(lastpath!=path[0][1][0][0]){s.push(lastpath);printf("day:%d weather:%d point %d water:%d food:%d\n",lastpath.day,(int)weather[lastpath.day],(int)mp[lastpath.from],lastpath.water,lastpath.food);temppath=lastpath;lastpath=path[lastpath.day][lastpath.from][lastpath.water][lastpath.food];} }2.2簡化地圖+Dijkstra
2.2.1模型簡化與分析
游戲原地圖較為復雜，但事實上有意義的結(jié)點只有起點、終點、村莊和礦山，因此求解時考慮使用Dijkstra，求出這四類結(jié)點的最短路徑，將原地圖壓縮到僅包含著四類結(jié)點。
下面對各個問題進行討論與分析
對于只有一名玩家并且每天天氣全部已知的情況：第一關(guān)和第二關(guān)必然有確定的最優(yōu)解，而地圖結(jié)構(gòu)并不復雜，因此可以直接通過窮舉、蒙特卡羅等搜索策略求解。
2.2.2模型假設
1.每天的天氣情況相互獨立。
2.玩家每天早上確定策略，晚上完成狀態(tài)轉(zhuǎn)移及資源、資金結(jié)算。
3.多人游戲中，各個玩家絕對自私、完全理性。
2.2.3 符號說明
2.2.4 模型建立與求解
maxQ30+12pwW30+12pfF30其中Qt,Wt,Ft分別表示第t天時玩家所剩下的資金、水和食物量。如果玩家在第30天前到達終點，則其各個屬性將會在未來幾天視作不變，所以我們以第三十天為統(tǒng)一結(jié)束時間。該目標函數(shù)有如下約束：Qt=Qt?1+QMineMinet?Shopt[2pfShopFt+2pwShopWt]
食物方面
每天結(jié)束時的資金等于前一天的資金加上當天挖礦獲得的1000元（如果挖礦的話），再減去在村莊購買食物和水花費的錢（如果購買的話）。其中ShopFt和ShopWt分別表示玩家在第t天購買的食物量和水量（如果購買的話）。
Ft=F(t?1)?2Movet △Ft? 3Mine tMovet △Ft?(1?Movet?Minet)△Ft+Shopt ShopFt
水方面
Wt=Wt?1?2Movet△Wt?3Minet△Wt?(1?Movet?Minet)△Wt+ShoptShopWt
2.2.5 地圖簡化
我們首先引入Dijkstra算法，這是一種在有向賦權(quán)圖中求兩點之間最短路徑的高效算法。選取圖中起點、終點、村莊和礦山作為特殊點，利用Dijkstra算法計算出每兩個特殊點之間的最短路徑（即不考慮沙暴天氣的影響下，所需最少的天數(shù)） 。然后根據(jù)簡化后的情況來完成一幅新的地圖。
3.第三關(guān)與第四關(guān)
第三關(guān)與第四關(guān)相比較于前兩關(guān)，僅僅知道當天的天氣，據(jù)此決定當天的行動方案，給出最佳策略。
3.1 前兩關(guān)總結(jié)
分析第一關(guān)和第二關(guān)：可得出以下的基本的策略設計原則
(1)到達終點處的資源恰好耗盡。為了使到達終點的時候資金盡可能的多，萬向節(jié)沒有理由買多余生存需要的水和食物，玩家在七點和村莊購買資源的價格高于終點返還的資金，因此在天氣情況已知的情況下，玩家知道維持自己生存所需要的最少資源，所以有能力在到達終點的時候控制資源恰好耗盡。此策略僅僅適用于全局天氣已知的情況。第三四關(guān)不可以了。
(2)起點處保證生存的情況下多買食物
因為村莊的資源貴，所以盡可能的起點買食物，并且因為背包有上限，所以玩家傾向于在起點購買價格較貴且質(zhì)量較小的資源。會盡可能的多買食物。
3.2 三關(guān)
第三關(guān)和第四關(guān)由于存在隨機性，不能夠給出一個確定性的最優(yōu)策略，所以在設計方案之后需要對方案的結(jié)果進行評價
沿用動態(tài)規(guī)劃的思想的情況下處理第三關(guān)
第三關(guān)天氣是隨機的。但是地圖比較小且只有10天，所有天氣一供1024中情況，可以利用動態(tài)規(guī)劃給出每一種情況的最優(yōu)解，用統(tǒng)計的方法來觀察規(guī)律。
通過觀察最優(yōu)解策略，發(fā)現(xiàn)即使在全部晴天狀態(tài)下也沒有全部去挖礦，可以猜想這一關(guān)不能挖礦。
事實上，由于第三關(guān)沒有村莊，又因為高溫天氣消耗更大，且挖礦收益更小，即使在晴朗的天氣挖礦，收益僅為200-165=35，挖礦五天的收益175還不能彌補繞路造成的資源損耗。所以直接去終點是比較正確的選擇。
3.3四關(guān)
分析第四關(guān)之于以前的關(guān)卡引入一個新的概念決策點。這個決策點13距離起點只有4天的路程，而且是玩家在沙漠中的必經(jīng)點，這和第三關(guān)的情況非常相似。同時決策點距離村莊和礦山都只有一天的行程，在決策點的裝屯點直接影響了玩家的決策，因此是玩家做決策的關(guān)鍵點。
分析一般情況下最有策略
地圖中沒有礦山和村莊的情況
當玩家距離下一個目的地較近的時候，玩家不應該等待，應該盡可能的到達目的地，因為更長時間的停留會大大的增加資源的消耗，甚至會失敗的風險，即使等待最終能夠到達終點，最后的資金和快速通過的方案也相差無幾，通過避開高溫行走而節(jié)省的金錢并不多。
地圖中有村莊和礦山的情況
出發(fā)點的策略是攜帶效率高的資源，在村莊大量補充攜帶資源效率低的資源
行動策略為在接近村莊和礦山的點進行決策，若資源較少則先去補充資源，若資源較多就去挖礦，當挖礦挖到資源剩余按最壞的打算僅夠前往下一個功能點的時候。
3.4 如何處理天氣
處理天氣的思路一種情況是上面提到到按照一定分布隨機生成，然后統(tǒng)計每一種情況分析出最有的策略。
還有一種是利用馬爾可夫鏈，建立了天氣預測而模型。根據(jù)第一關(guān)天氣轉(zhuǎn)換情況預測其余關(guān)卡的天氣情況，在根據(jù)問題一的模型得出在不同天氣情況下玩家的最佳策略，利用對應的天氣情況概率和最佳策略下的最大資金，可以得出最終收益的數(shù)學期望，選擇數(shù)學期望最大的一種策略
4.使用軟件與編程語言
按照解決問題的不同思路使用不同的工具；
如果是使用動態(tài)規(guī)劃作為主要求解的方法，那么C++,MATLAB都可以作為求解的辦法。
如果側(cè)重于仿真與模擬，通過蒙特卡洛這種方法來求解。可以使用Python來完成。
如果是使用groubi等求解器，可以配合MATLAB和編程語言一起使用。
本文第二部分動態(tài)規(guī)劃解決第一二關(guān)的代碼來源于
https://www.cnblogs.com/cherrypill/p/15158527.html
總結(jié)
以上是生活随笔為你收集整理的数学建模2020B题穿越沙漠的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： mybatis判断集合为空或者元素个数为
- 下一篇： Linux 内核定时器实验————复习到