2020数模国赛B题.pdf-资料库

cddddduck-12844517-4744300845380028792.pdf-第1页.png

第1页 / 共57页

cddddduck-12844517-4744300845380028792.pdf-第2页.png

第2页 / 共57页

cddddduck-12844517-4744300845380028792.pdf-第3页.png

第3页 / 共57页

cddddduck-12844517-4744300845380028792.pdf-第4页.png

第4页 / 共57页

cddddduck-12844517-4744300845380028792.pdf-第5页.png

第5页 / 共57页

cddddduck-12844517-4744300845380028792.pdf-第6页.png

第6页 / 共57页

cddddduck-12844517-4744300845380028792.pdf-第7页.png

第7页 / 共57页

cddddduck-12844517-4744300845380028792.pdf-第8页.png

第8页 / 共57页

穿越沙漠的决策建模分析摘要考虑一种穿越沙漠的游戏，玩家要在限定的时间内，遵循一定的规则从起点走到终点，并且希望到达终点时手头的资金尽可能得多。我们需要求解一种策略，来帮助玩家，面对一些常见的情况，能够尽可能做出更优的决策。问题一：要求在全部天气信息已知的情况下，找出能使玩家通关且最终保有资金最多的方法。我们经过提取地图信息，使用邻接矩阵来记录点的关系。通过改良的 Dijkstra 法，找出地图中任意两点的所有最短路径。最后通过动态规划找到了最优方案，其中第一关的最优解为 10430 元，第二关的最优解为 12470 元。问题二：在仅知道当天天气的前提下，给出一个最优策略。利用仿真的方法建模整个决策过程，调节模型的参数，得到一些良好的模型。当模型以高概率选择向靠近终点的方向移动时，第三关通关的概率有 92.7%，同样的模型用在第四关，通关率降到 80.4%，简单优化参数，通关率可提升至 90.2% 问题三：本题需要玩家权衡最优方案和与他人博弈的可能，从两方面考虑问题：a、扩大方案的选择域，将一部分次优方案也纳入考虑范围；b、在负重上限内，提高初始购买资源的数量，来降低不慎与其他玩家相遇后游戏失败的概率。经过实际测试，通过概率可达 90.8%，通过的金额均达到 9000，其中有 52%的几率金额在 9400 以上。第二问引入了新的策略。以第二题决策模型为基础，增添规则，重新调整模型的参数。直接套用第二问模型，结果三位玩家的通关率分别为 76.4%，78.3%，78.1%，进一步优化参数，通关率可提升至 89.0%，92.2%，88.8%。关键词：动态规划、仿真、Dijkstra 算法、python、matlab

一、问题重述考虑如下的小游戏：玩家凭借一张地图，利用初始资金购买一定数量的水和食物（包括食品和其他日常用品），从起点出发，在沙漠中行走。途中会遇到不同的天气，也可在矿山、村庄补充资金或资源，目标是在规定时间内到达终点，并保留尽可能多的资金。游戏的基本规则如下：以天为基本时间单位，游戏的开始时间为第 0 天，玩家位于起点。玩家必须在截止日期或之前到达终点，到达终点后该玩家的游戏结束。穿越沙漠需水和食物两种资源，它们的最小计量单位均为箱。每天玩家拥有的水和食物质量之和不能超过负重上限。若未到达终点而水或食物已耗尽，视为游戏失败。每天的天气为“晴朗”、“高温”、“沙暴”三种状况之一，沙漠中所有区域的天气相同。每天玩家可从地图中的某个区域到达与之相邻的另一个区域，也可在原地停留。沙暴日必须在原地停留。玩家在原地停留一天消耗的资源数量称为基础消耗量，行走一天消耗的资源数量为基础消耗量的倍。玩家第 0 天可在起点处用初始资金以基准价格购买水和食物。玩家可在起点停留或回到起点，但不能多次在起点购买资源。玩家到达终点后可退回剩余的水和食物，每箱退回价格为基准价格的一半。玩家在矿山停留时，可通过挖矿获得资金，挖矿一天获得的资金量称为基础收益。如果挖矿，消耗的资源数量为基础消耗量的倍；如果不挖矿，消耗的资源数量为基础消耗量。到达矿山当天不能挖矿。沙暴日也可挖矿。玩家经过或在村庄停留时可用剩余的初始资金或挖矿获得的资金随时购买水和食物，每箱价格为基准价格的 2 倍。在给定前提下，给出一般情况下玩家的最优策略。 23

二、问题分析 2.1 问题一问题一要求在仅有一名玩家，且全部天气信息已知的情况下，要求找出能使玩家通关且最终保有资金最多的方法。那么首先我们可以提取地图信息，将其抽象化为图（Graph），此时所有的区域会抽象为点，且代表相邻区域的点之间存在连线，使用邻接矩阵来储存点之间的关系。接着通过改良的 Dijkstra 法，找出地图中任意两点的所有最短路径。虽然此题中任意两点间的最短路径可能不止一条，但对于第一题而言，在两点间相同长度的不同路径上，玩家的决策产生的影响相同，所以可以将复杂的图退化为简单图，同时筛去赘余的连线。面对在简单图上寻找最优方案，我们选择使用动态规划（DP），来寻找出最优方案。 2.2 问题二问题二要求玩家在仅知道当天的天气状况下，据此决定当天的行动方案，给出一般情况下玩家的最佳策略，并对附件中的“第三关”和“第四关”进行具体讨论。问题二和问题一相比缺失了整个过程的天气数据，意味着无法求得一个在各种情况下，在各种指标下均最优的策略。并且我们缺少历史数据进一步挖掘信息，挖掘一些统计规律。因此，我们的思路是，利用仿真的方法来建模整个决策过程，通过调节模型的参数，得到一些表现良好的决策模型，人工生成一些天气情况来检验决策模型的优劣。分析各参数变化对最终结果的影响，挖掘背后代表的实际意义。 2.3 问题三

2.3.1 第一问问题三的第一问引入了新的游戏规则，提取主要信息可知，当玩家与其他玩家选择了类似或相同的“受欢迎”方案时，将会受到一定的“惩罚”效果，而玩家选择较为“偏僻”的方案时，则“糟糕”的方案本身又会给玩家带来较大的负面影响，因此需要权衡来选出恰当的方案。其中玩家可提前得知所有的天气情况，但必须在游戏开始前确定自己的方案及路线。我们可以从两方面来考虑问题： a、扩大方案的选择域，不仅限于几种最优方案，将一部分次优方案也纳入考虑范围；b、在负重上限内，提高初始购买资源的数量，来提高容错率，降低不慎与其他玩家相遇后游戏失败的概率。因此此题不适用将复杂图降为简单图，因为每一个平凡点都有组成次优方案的价值。 2.3.2 第二问问题三的第二问可以看作在问题二的基础上，引入了多个玩家，且多个玩家在某些情况下会相互影响，但玩家在当天决策时并不知道其他玩家的策略。因此可以以第二题的单人决策模型为基础，增添规则约束，重新调整模型的参数，得到一些表现良好的决策模型。分析各参数变化对最终结果的影响，挖掘背后代表的实际意义。三、模型假设 1. 由第一问给出的天气数据，在后面的问题决策中，假设晴天与高温天气出现的概率均为 50% 2. 为了加快动态规划运行速度，做出如下假设：玩家在沿某一路径上移动

时，默认在没有到达路径末端时不会返回 3. 为了加快动态规划运行速度，玩家一旦离开起点，就再也不会回到起点 4. 动态规划运行速度，当玩家到达终点时，默认游戏结束四、符号说明符号 i L w f wout fout win fin we t M 符号说明当前天数所处地点携带水量携带食品量消耗水量消耗食品量买入水量买入食品量天气总天数剩余资金单位天箱箱箱箱箱箱天元

五、模型的建立与求解 5.1 问题一的建模与求解 5.1.1 数据分析问题一要求在仅有一名玩家，且全部天气信息已知的情况下，要求找出能使玩家通关且最终保有资金最多的方法。那么首先我们可以提取地图信息，将其抽象化为图（Graph），此时所有的区域会抽象为点，且代表相邻区域的点之间存在连线，使用邻接矩阵来储存点之间的关系。接着通过改良的 Dijkstra 法，找出地图中任意两点的所有最短路径。虽然此题中任意两点间的最短路径可能不止一条，但对于第一题而言，在两点间相同长度的不同路径上，玩家的决策产生的影响相同，所以可以将复杂的图退化为简单图，同时筛去赘余的连线。面对在简单图上寻找最优方案，我们选择使用动态规划（DP），来寻找出最优方案。 5.1.2 模型建立首先我们将关卡一、二的地图转为图（Graph），并提取图中信息作出邻接矩阵，考虑到终点（点 27）的特殊性，我们将邻接矩阵中所有以 27 为起点的线段均置为 0。如下为关卡一的图及邻接矩阵：图 1 关卡一图 2 关卡一邻接矩阵

得到邻接矩阵后，我们可以较轻易地使用改良的 Dijkstra 法找出任意两关键点（起点、村庄、矿山、终点）间的所有最短路径。例如在关卡一中从起点到矿山的所有最短路径包含有：[1-25-24-23-22-9-15-13-12]和[1-25-24-23-21-17- 16-14-12]。观察容易发现第一条路径中节点 15 为村庄，而第二条路径中没有特殊点，由最短路径的子路径仍为最短路径可知，[1-25-24-23-22-9-15]为起点到村庄的最短路径之一，[15-13-12]为村庄到矿山的最短路径，由此我们可以将复杂图退化至简单图，下图分别为关卡一、二退化后的简单图。图 3 关卡一简单图图 4 关卡二简单图在获得简单图后，我们就可以做动态规划操作（DP），通过不断递归来查找最优解。设定玩家在某一时刻的状态为 X(day,water,food,money,aimplace,daytoplace)，参数说明，day 第几天，water 剩余水，food 剩余食物，money 当前金额，aimpalce 下一个目标地点，daytoplace，去往目标地点至少需要行走的天数。 During_game(X,record) Ifdie(X) return Ifgameover(X) save(record) return If daytoplace==0: for i in couldreach: X,aimplace=i X.daytoplace=needday Record.()

During_game(X,record) for do in cando: Return X.do() During_game(X,record) return if invillage: X.buy() Record() During_game(X,record) if sandstrom: if mountain For do in cando: X.do() During_game(X,record) 5.1.3 模型求解图 5 第一关结果图 6 第二关结果

资料库

2020数模国赛B题.pdf

相关推荐

人工智能

热门标签

最新资料