目录
-
- 前言
- 原题
- 关键词
- 目标
- 问题一分析
- 问题二分析
- 问题三分析
- 比赛后的一些些感想
前言
本人小白，求大佬们放过！本篇文章介绍我们小组编写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，把整个问题改写成算法题，貌似就不是很难了。代码大致思路是这样的：三个人从起点出发，开起三个线程，控制天气比例后用随机函数给出每天的天气，每个人都用博弈树思想来规划路径，每种天气比例重复试验一万次得出平均结果。最后提交论文的时候真的挺欣慰的，至少让自己感觉到是真解决了问题的，结果怎样不重要，享受过程就好。
