B题穿越沙漠

考虑如下的小游戏：玩家凭借一张地图，利用初始资金购买一定数量的水和食物（包括食品和其他日常用品），从起点出发，在沙漠中行走。途中会遇到不同的天气，也可在矿山、村庄补充资金或资源，（赚钱）目标是在规定时间内到达终点，并保留尽可能多的资金。（资金max）

游戏的基本规则如下：

（1）以天为基本时间单位，游戏的开始时间为第0天，玩家位于起点。玩家必须在截止日期或之前到达终点，到达终点后该玩家的游戏结束。

（2）穿越沙漠需水和食物两种资源，它们的最小计量单位均为箱。每天玩家拥有的水和食物质量之和不能超过负重上限。若未到达终点而水或食物已耗尽，视为游戏失败。

（3）每天的天气为“晴朗”、“高温”、“沙暴”三种状况之一，沙漠中所有区域的天气相同。

（4）每天玩家可从地图中的某个区域到达与之相邻的另一个区域，也可在原地停留。沙暴日必须在原地停留。

（5）玩家在原地停留一天消耗的资源数量称为基础消耗量，行走一天消耗的资源数量为基础消耗量的倍。

（6）玩家第0天可在起点处用初始资金以基准价格购买水和食物。玩家可在起点停留或回到起点，但不能多次在起点购买资源。玩家到达终点后可退回剩余的水和食物，每箱退回价格为基准价格的一半。

（7）玩家在矿山停留时，可通过挖矿获得资金，挖矿一天获得的资金量称为基础收益。如果挖矿，消耗的资源数量为基础消耗量的倍；如果不挖矿，消耗的资源数量为基础消耗量。到达矿山当天不能挖矿。沙暴日也可挖矿。

（8）玩家经过或在村庄停留时可用剩余的初始资金或挖矿获得的资金随时购买水和食物，每箱价格为基准价格的2倍。

请根据游戏的不同设定，建立数学模型，解决以下问题。

\1. 假设只有一名玩家，在整个游戏时段内每天天气状况事先全部已知，试给出一般情况下玩家的最优策略。求解附件中的“第一关”和“第二关”，并将相应结果分别填入Result.xlsx。

\2. 假设只有一名玩家，玩家仅知道当天的天气状况，可据此决定当天的行动方案，试给出一般情况下玩家的最佳策略，并对附件中的“第三关”和“第四关”进行具体讨论。

\3. 现有名玩家，他们有相同的初始资金，且同时从起点出发。若某天其中的任意名玩家均从区域A行走到区域B( )，则他们中的任一位消耗的资源数量均为基础消耗量的倍；若某天其中的任意名玩家在同一矿山挖矿，则他们中的任一位消耗的资源数量均为基础消耗量的倍，且每名玩家一天可通过挖矿获得的资金是基础收益的；若某天其中的任意名玩家在同一村庄购买资源，每箱价格均为基准价格的倍。其他情况下消耗资源数量与资源价格与单人游戏相同。

（1）假设在整个游戏时段内每天天气状况事先全部已知，每名玩家的行动方案需在第天确定且此后不能更改。试给出一般情况下玩家应采取的策略，并对附件中的“第五关”进行具体讨论。

（2）假设所有玩家仅知道当天的天气状况，从第天起，每名玩家在当天行动结束后均知道其余玩家当天的行动方案和剩余的资源数量，随后确定各自第二天的行动方案。试给出一般情况下玩家应采取的策略，并对附件中的“第六关”进行具体讨论。

注1：附件所给地图中，有公共边界的两个区域称为相邻，仅有公共顶点而没有公共边界的两个区域不视作相邻。

注2：Result.xlsx中剩余资金数（剩余水量、剩余食物量）指当日所需资源全部消耗完毕后的资金数（水量、食物量）。若当日还有购买行为，则指完成购买后的资金数（水量、食物量）。

全国大学生数学建模竞赛2020赛题 (mcm.edu.cn)

沙漠捞钱笔记

穿越沙漠

挖矿赚钱

买吃喝的花钱

结束的资源可以退款

数据总和

时间单位：天
资源单位：水食物（箱）
天气情况：
- 晴朗：
- 高温：
- 沙暴：原地停留
消耗情况：走 = 2 * 停留

每道题都是一种特殊的情况

想到的模型：

单目标，钱！

约束条件：

资源（水和食物）
载重
天数
地图？

特殊因素：

天气：沙尘暴可以挖矿

地图规划：

第一题

可能的情况：

1、直接跑终点（资源够不够，打工是否有收益）（论文：这个工作一定要做）

2、去矿山村庄来回打工赚money。（2大于1才能打工）

三阶段
- 起点到矿山/村庄。（一条最适合的路）
- 村庄矿山来回刷money。
- 回终点。（一条最适合的路）

李龙：天气卡住节奏，天气是否过来，组合不一样。动态规划。卡天气可以原地呆着！

鑫成：最短路，贪心算法。发证最近的路程可以找。

刷钱模型？

考虑因素：

矿山与村庄的距离因素。
矿山与村庄位移的天数。
到矿山当天不能干活。
天气情况。

三步算，一步算代码冗杂，容易局部最优解。体现的思考，与简化问题。

代码去实现！

st：

李龙：先写个赚钱循环！

jh：Question：如果天气差停下来可以不呜呜呜？

鑫成：一步步来。（卑鄙的资本家）

先起点买爆！

默认行走更赚。虽然天气很差，但是只要收益大，就累点吧。

你这个年纪怎么睡得着。

最后把这么情况，算入优化模型中。列数学公式。

优化模型：

第一阶段：

李龙：一阶段固定，省事~

第二阶段：

根据一阶段后的数据,以及各个因素，构建单目标多约束优化模型。

第三阶段：

由于比较麻烦，不关键，单独计算，减回去！反正不是重点。已经考虑很多东西了。

第二关，两种情况，也是图形规划。

可以沿着第一关的思路继续做

第二题

动态规划。注意收益？

加强对天气的关注。工作收益。

直接走到终点？
是否打工？单向地图！
博弈问题。

是否补满装备？

第三关

各个天气的概率确定。

动态规划。注意收益？

加强对天气的关注。工作收益。

直接走到终点？
是否打工？单向地图！
博弈问题。

是否补满装备？

第四关（基于状态机）

较少的定义：概率定下来。各个温度的概率。

（天气来回不影响，每天单独）

鑫成：天数固定。还是用优化模型。否定！

状态机！！！

期望值（）风险系数：指标。

第三题

第五关

鑫成：遗传算法

可能得使用暴力算法了。代码问题。

供求关系。

劲铧：加博弈论的第一第二题

CJ：暴力模型：计算机遍历，蒙特罗塔。验证。

沙漠致富之路总结

包含算法

动态规划
单目标优化模型
博弈论，静态博弈
启发式算法（基于经验和直觉）
模拟仿真，暴力解法
马尔科夫链（近似状态机）
图论算法（最小图路径迪杰斯特，Floyd）

论文应有内容

影响因素的分布图
排序好的捕捉条件约束
优化后的简化图结构
适当补充流程图
最短路径的floyd或迪杰斯特的伪代码
排序好的决策表格
博弈论具体博弈数值
具体玩家收益表格，期望值表格