摘要:本文主要针对在游戏规定条件下穿越沙漠的最优策略进行了相关研究。利用Bellman-Ford算法得出从起点到达矿山的最近距离,通过建立目标函数和约束条件,得到每种情况的最优策略。首先我们通过对题目所给路线与实际情况的分析,根据Bellman-Ford算法得出从起点到达矿山的最近距离,以及得到从矿山出发到达终点的最短路线。其次通过建立目标函数和约束条件,得出线性规划问题模型,最终通过求解线性规划问题,得到每种情况的最优策略。最后在最短路线的基础上考虑天气状况和玩家路线是否重合,从而确定最佳收益路线,做出三十天的天气预测,并结合Bellman-Ford算法与不同方案进行迭代,得到最优路线策略。
玩家凭借一张地图,利用初始资金购买一定数量的水和食物(包括食品和其他日常用品),从起点出发,在沙漠中行走。途中会遇到不同的天气,也可在矿山、村庄补充资金或资源,目标是在规定时间内到达终点,并保留尽可能多的资金。游戏开始的时间为第0天,玩家位于起点。玩家必须在截止日期或之前到达终点,到达终点后该玩家的戏结束。穿越沙漠需水和食物两种资源,每天玩家拥有的水和食物质量之和不能超过负重上限。玩家在矿山停留时,可通过挖矿获得资金,挖矿一天获得的资金量称为基础收益。玩家经过或在村庄停留时可用剩余的初始资金或挖矿获得的资金随时购买水和食物,若未到达终点而水或食物已耗尽,视为游戏失败。
1、问题分析
假设只有一名玩家,在整个游戏时段内每天天气状况事先全部已知,第一关和第二关路线全部分设定为经过矿山和村庄以及不经过矿山和村庄这两种路线进行建模,两者结合更加科学合理的帮助玩家穿越沙漠以及得到最大资金,规划以最短流程经过矿山和村庄以及停留矿山最久时间,所达到资金最大化,同时又保证食物充足以及在30天内完成。我们分别从玩家路线一致且经过矿山的情况和不经过矿山的情况以及玩家路线不一致经过或不经过矿山的情况进行对比分析,最终确定两名玩家路线不一致时,且不经过矿山,该路线是最优策略。我们基于所计算的最短路线的基础上分别考虑了晴朗天气和高温天气的所有情况,最终得到在不经过矿山的最短路线为,且全是晴天的情况下,达到终点的最佳收益最高为9670元,该路线为最优策略。
2、模型的建立与求解
我们通过对路线实际情况的分析,把两种情况路线全部分为经过矿山和村庄以及不经过矿山和村庄两种路线进行建模,两者结合进行比较更加科学合理的确定玩家穿模沙漠的最佳策略。初始化:将除源点外的所有顶点的最优距离估计值:d[v]←+∞,d[s]←0。分布式迭代求解:反复对边集E中的每条边进行松弛操作,使得顶点集V中的每个顶点v的最优距离估计值逐步接近其最优距离(运行v-1次)。检验负权回路:判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点,则算法返回false,表明问题无解;否则算法返回true,并且从源点可达的顶点v的最优距离保存在d[v]中。[2]我们先假设不经过矿山和村庄,最短时间到达终点时在穿越沙漠中水和食物最小消耗量以及剩余的的资金总和,利用Matlab建立模型并绘图。
以经过矿山和村庄建立模型,规划以最短路径经过矿山和村庄以及停留矿山最久时间,所达到资金的最大化,同时又保证食物充足以及在截止日期30天内完成,根据Bellman-Ford算法得出从起点到达矿山的最近距离,以及得到从矿山出发到达终点的最短路线,找到最小损耗路线。
通过建立目标函数和约束条件,得出线性规划问题,最终通过求解线性规划问题,得到每种情况的最优策略。线性规划的目标函数可以是求最大值,也可以是求最小值,约束条件可以是不等式也可以是等式,变量可以有非负要求也可以没有非负要求。为了避免这种由于形式多样性而带来的不便,规定线性规划问题的标准型为[3]:
线性规划的标准形式要求目标函数最小化,约束条件取等式,变量非负。由于题目所给玩家数量确定,所以该问题间接转化成定量分析讨论,其规则是若某天其中的任意k(2燮k燮n)名玩家均从区域A行走到区域B(B≠A),则他们中的任一位消耗的资源数量均为基础消耗量的2k倍;n=2,则有2名玩家,由题意可知2人是一同行动的。所以他们每人平均基础消耗量为一人(单独行动)的2倍。在两种方案的条件下进行路线规划,分别分为:从起点出发到达矿山,然后从矿山到达终点的最短路径(此时不考虑在矿山的停留时间);从起点出发不经过矿山直达终点的最短路径。在最短路线的基础上考虑天气状况和玩家路线是否重合,从而确定最佳收益路线。对于天气状况已知,排除考虑,我们分别从玩家路线一致且经过矿山的情况和不经过矿山的情况以及玩家路线不一致经过或不经过矿山的情况进行对比分析,最终确定两名玩家路线不一致时,且不经过矿山,该路线是最优策略。由于每名玩家仅知道当天的天气状况,因此我们考虑建立时间序列模型,做出三十天的天气预测,并结合Bellman-Ford算法与不同方案进行迭代,得到最优路线策略。经典的时间序列模型包括移动平均模型、自回归模型、自回归移动平均模型。假设xt表示t时刻的时间序列的值,q表示时间窗的大小,εt表示t时刻的白噪声,
α1,…,αp和β1,…,βq表示权重系数。
MA(q)表示为:
AR(P)和ARMA(p,q)分别表示为:
注意到对于ARMA模型,当权重系数β1,…,βq全为0时,其可以被看作一个AR模型[4]。因为MA,AR和ARMA都具有弱平稳性,其均值和协方差都不取决于t,即:E(Xt)=μ,cov(Xt,Xt+k)=E(Xt-u)(Xt+k-u)=γk,k∈Z分别做出了四种情况下的最短路线:第一种情况是在不经过矿山情况下最短路径为路线11(此时视为两名玩家路线一致),第二种情况是经过矿山的最短路径是路线12(此时视为两名玩家路线一致),第三种情况是两名玩家路线均不一致经过矿山到达终点最短路径13,第四种情况是两名玩家路线均不一致不经过矿山到达终点最短路径是14。
根据建立的模型,分别假设经过矿山和村庄及不经过矿山和村庄这两种不同的假设确定两条最短路线(不考虑停留情况),在这两条的最短路线的基础上同时考虑天气情况和挖矿停留时间。因为玩家仅知道当天的天气状况,只能据此决定当天的行动方案。游戏条件不考虑沙暴,我们基于所计算的最短路线的基础上分别考虑了晴朗天气和高温天气的所有情况,最终得到在不经过矿山的最短路线为,且全是晴天的情况下,达到终点的最佳收益最高为9670元,该路线为最优策略。考虑到沙暴天气的取值介于0~9之间,通过建立目标函数和约束条件,得出线性规划问题模型,最终通过求解线性规划问题,得到每种情况的最优策略。在最短路线的基础上考虑天气状况和玩家路线是否重合,从而确定最佳收益路线。对于天气状况已知,故排除考虑,我们分别从玩家路线一致且经过矿山的情况和不经过矿山的情况以及玩家路线不一致经过或不经过矿山的情况进行对比分析,最终确定两名玩家路线不一致时,且不经过矿山,该路线是最优策略。
由于每名玩家仅知道当天的天气状况,因此我们考虑建立时间序列分析模型,做出三十天的天气预测,并结合Bellman-Ford算法与不同方案进行迭代,得到最优路线策略2人共同挖矿,另一个人以最短路线经过所得资金最多,为57760元。最后对模型的优缺点进行了讨论,主要分析了未考虑到折返情况及特殊情况下天气对整个路线规划的影响。
3、结论
首先两种方案的条件下进行路线规划,分别从起点出发到达矿山,然后从矿山到达终点的最短路径,从起点出发不经过矿山直达终点的最短路径,在最短路线的基础上考虑天气状况和玩家路线是否重合,从而确定最佳收益路线。当天气状况已知,排除考虑,我们分别从玩家路线一致且经过矿山的情况和不经过矿山的情况以及玩家路线不一致经过或不经过矿山的情况进行对比分析,最终确定两名玩家路线不一致时,且不经过矿山,该路线是最优策略。对于每名玩家仅知道当天的天气状况,因此我们考虑建立时间序列模型,做出三十天的天气预测,并结合Bellman-Ford算法与不同方案进行迭代,得到最优路线策略。
参考文献:
[1]石福周.沙漠地区长大纵坡沥青路面稳定性控制研究[D].长安大学,2014.
[2]宫恩超,李鲁群.基于Bellman-Ford算法的动态最优路径算法设计[J].测绘通报,2011(8):26-28+41.
[3]盛仲飙.基于Matlab的线性规划问题求解[J].计算机与数字工程,2012,40(10):26-27+80.
[4]贺艳婷.时间序列分析建模实例[J].中国新通信,2020,22(10):138-140.
[5]徐燕.以数学建模竞赛为例基于SPSS建立ARIMA模型[J].科技视界,2020(1):50-51.
臧洋,师艳,景港澳,陈萌琪,赵怡.基于Bellman-Ford算法的穿越沙漠策略研究[J].科学技术创新,2020(34):16-17.
分享:
玩家凭借一张地图,利用初始资金购买一定数量的水和食物(包括食品和其他日常用品),从起点出发,在沙漠中行走。途中会遇到不同的天气,也可在矿山、村庄补充资金或资源,目标是在规定时间内到达终点,并保留尽可能多的资金。游戏开始的时间为第0天,玩家位于起点。玩家必须在截止日期或之前到达终点,到达终点后该玩家的戏结束。
2020-11-27《数学建模》课程的教学内容知识面涵盖广且学科交叉广泛;同时《数学建模》的很多知识点以《高等代数》《数学分析》《概率论与数理统计》《数学实验》等学科知识为基础,因此很多知识点加大了高职高专学生透彻理解《数学建模》内容的难度与深度,继而严重影响了学生对于《数学建模》课程的学习兴趣。
2020-07-10博弈论已经成为经济学的标准分析工具之一,被认为是20世纪经济学最伟大的成果之一,其在生物学、国际关系、计算机科学、政治学、军事战略等很多学科都有广泛的应用。博弈论与社会、经济联系密切,同样也可以运用博弈论构建数学模型,解析社会发展,培养新型人才。本文用约翰•纳什非合作博弈理论的思想对人才培养策略进行探析。
2020-07-10数学建模在合理假设的基础上将实际问题简单化、抽象化,用数学知识解决问题并接受实践的检验。在这一过程中,问题的求解需要借助计算机计算才能完成。MATLAB作为应用最广泛的科学计算软件,具有强大的数据处理、数据分析及图像可视化等功能。在每年的全国大学生数学建模竞赛中,MATLAB是普遍应用的软件。
2020-07-10随着中国经济的发展,社会越来越需要应用技能型人才,而高职教育的重要目的就是培养应用技能型人才。数学建模竞赛就是检验学生应用数学能力的一项重要赛事。数模竞赛于20世纪80年代起源于美国,90年代我国开始举办,参与竞赛的院校越来越多,影响力也越来越大。
2020-07-10诚然,培养高职学生的创新能力不是一种新的教育理念,但确实是一个新的课题,更是对高职教育体制和高职数学建模微观教育一场前所未有的挑战。采用案例教学培养学生的创新能力,还有许多值得探讨的内容,笔者希望与同行一道,无怨无悔为之努力、为之奋斗。
2020-07-10笔者带领所在团队,通过10年的探索实践,在理论成果方面,出版了专著《高职数学建模案例教学研究》(天津科学技术出版社);出版了教材《应用数学》(上、下,广东省高等教育出版社,推荐为国家职业教育“十三五”规划教材);出版了教材《数学建模及典型的案例分析》(电子工业大学出版社,国家“十二五”规划教材)。
2020-07-10目前,关于以学生为中心的数学建模金课建设的研究尚少。笔者结合从事数学建模课程教学、竞赛指导十几年的经验,基于数学建模课程特色,从数学建模素养、探究式教学模式、成果为本的评价方式三方面,探讨以学生为中心的数学建模金课的课程设计原则,从分层级教学组织、线上教学混合教学模式、实践训练、多层次考核四方面探讨金课建设的实施方案。
2020-07-10老师通过数学建模竞赛和数学建模课程教学等途径培养学生的数学思想,使学生在分析问题和解决问题的过程中养成独立思考的能力。数学建模是一门理论性与实践性都很强的课程,老师在教学活动中要优化知识结构,注重引导学生思考,重视学生在学习过程中直觉思维与发散思维的形成,培养学生的创新能力与自我评价能力,从而提高数学建模教学的质量。
2020-07-10《数学模型》课程能够将背景分析、数学建模、求解方法、软件编程、回归检验和论文撰写等有机地结合起来,是大学生尝试独立进行知识应用、实验实践和团队合作的良好环境,是大学生形成主导地位的锻炼机会。在《数学模型》的教学过程中要引导大学生进行实验实践学习、大数据的应用和大学生创新创业项目申报等。
2020-07-10人气:2500
人气:1998
人气:1306
人气:1289
人气:1085
我要评论
期刊名称:数学建模及其应用
期刊人气:1311
主管单位:山东省教育厅
主办单位:山东科技大学
出版地方:山东
专业分类:科学
国际刊号:2095-3070
国内刊号:37-1485/O1
创刊时间:2012年
发行周期:季刊
期刊开本:16开
见刊时间:7-9个月
影响因子:0.322
影响因子:0.352
影响因子:0.000
影响因子:0.000
影响因子:0.000
400-069-1609
您的论文已提交,我们会尽快联系您,请耐心等待!
你的密码已发送到您的邮箱,请查看!