基于邻接矩阵法的穿越沙漠路线研究

来源 :科学导报·学术 | 被引量 : 0次 | 上传用户:whitewolfwv7
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
  【摘 要】本文主要针对穿越沙漠问题进行了相关研究,利用邻接矩阵法制定了不同地图不同天气变化条件下游戲玩家的最优策略。首先利用邻接矩阵先对第一关和第二关分别情况讨论,通过分析得出最优路径。其次第三关的天气变化情况不同通过分析得出最优路径。最后对第五关和第六关进行求解第五关中每天的天气已知,但两名玩家的路线只能当天确定,为使得他们获得的总资金最大,他们的路线应尽可能的不同,第六关天气与第四关一样未知,且地图与第四关相同,因此三名玩家的路线尽可能不重复,且最终所获得的总资金最高。
  引言
  本文介绍了穿越沙漠小游戏,玩家用地图购买一定数量的水和食物(包括日常必需品),然后从沙漠步行,行走时会有不同的天气(晴天、高温、沙尘暴),当经过矿山和村庄时可以补充资金和资源。游戏开始时间为第0天,游戏者再出发前必须在最后期限之前达到终点线,如果没有达到终点,水或食物耗尽,这被认为游戏失败,如果到达终点线后,玩家可以归还剩下的水和食物。
  1、问题分析
  在游戏规定的条件下,建立数学模型,在整个游戏时段内每天天气状况事先全部已知,试给出一般情况下玩家的最优策略。首先先求解“第一关”和“第二关”,并将相应结果分别填入Result.xlsx中,其次玩家仅知道当天的天气状况,可据此决定当天的行动方案,并对“第三关”和“第四关”进行具体讨论。
  最后对第六关求解,假设有n名玩家,求当n=2时,两位玩家的最优化路线,当n=3时,三位玩家的最优化路线。
  2、模型的建立与求
  首先采用邻接矩阵 [5]表示沙漠中任意两点之间可行走路线,邻接矩阵平方是表示顶bai点之间相邻关系的矩阵的平方。先对第一关和第二关分别情况讨论,在只有一名玩家,且知道每天的天气变化情况下,要求在30天之内从起点到达终点。需要对玩家行走的路线进行分类,通过最短路径分析出最优的几条路线[2]。在不违背游戏规则情况下,分别对第一关和第二关进行求解。
  针对第一关分三种情况:
  (1)从1(起点)-27(终点);
  (2)1(起点)-12(矿山)-27(终点);
  (3)1(起点)-15(村庄)-12(矿山)-27(终点)。
  在起始点购买物资消耗的钱小于初始资金:ω1<=η,从起始点到终点天数的约束:
  其中,β=nd,η=10000,ω=ω1 +ω2,d= 1000,a=190,b=104,c=150,最后得到起点a1-村庄a15(经过且停留一天)-矿山a12(挖矿)-终点a27的最短路径为1-25-24-23-22-9-15-13-12-14-15-9-21。得出即从起点出发经过村庄并停留一天购买物资,然后到达矿山,挖八天的矿物,赚取资金,最后返回终点的过程获得的资金为 13130 元。
  针对第二关同样也分三种情况:
  (1)1(起点)-64(终点);
  (2)1(起点)-30(矿山)-39(村庄)-64(终点);
  (3)1(起点)-30—(矿山)-64(终点)。
  对比三种情况,选出所剩资金最多的一种情况。由于第二关的与第一关的条件相同,仅地图不同。由1(起点)-64(终点);由起点-上矿场-村庄购买物资-下矿场-村庄(/无)-终点。
  最后得到路线从起点直接出发到终点,仅消耗资金,没有任何收益,到达55(矿山)后挖矿7天,去62(村庄)购买所需物资后回到终点,累计资金最大,为9635元。
  第三关:(1)1(起点)-13(终点);
  (2)1(起点)-9(矿山)-13(终点)。
  对比两种情况,选出所剩资金最多的一种情况,从起点到矿山挖矿挣取资金,最后回到终点。其次途中一直行走不停留,由于起点到矿山,矿山到终点的最短路径已经确定,且不存在沙暴天气,因此可以得到在路上行走消耗的天数是固定的五天,由于挖矿天数越多,获得的收益也越多,在起点购买的物资,最大只能支持行走五天和五天的挖矿时间消耗,若高温条件下不停留,在起点购买的物资,最多可以支持五天挖矿的消耗。
  针对第四关:(1)1(起点)-25(终点);
  (2)1(起点)-18(矿山)-14(村庄)-25(终点);
  (3)1(起点)-18(矿山)-25(终点)。
  对比三种情况,选出所剩资金最多的一种情况。得出玩家仅知道当天的天气状况,最短路得到从起点直接到终点的最短途径为1-6-11-16-21-22-23-24-25路线。在该路线下,八天晴朗的天气情况下,获得最大收益为9120元。
  将游戏规则复杂化,随着玩家数目的变化,挖矿收益和资源消耗也随着发生变化。在不违背游戏规则情况下,针对不同的天气变化情况分别对第五关和第六关进行分情况讨论。针对第五关:
  (1)玩家一和玩家二都从1(起点)直接到13(终点);
  (2)玩家一从:1(起点)-13(终点),玩家二从:1(起点)-9(矿山)-13(终点);
  (3)两个玩家:1(起点)-9(矿山)-13(终点)。
  选出所剩资金最多的一种情况:由两个玩家同时从起点走向终点,两个玩家一同行走,消耗的物资是一般情况下的二倍,因此为了减少不必要的消耗,尽可能的使得两个人分开走,一个玩家走矿山,一个玩家且不走矿山,最终得出起点直接到终点的最短路径为:1-5-6-13(经过三个区域). 其次为1-4-7-12(或11)-13(经过四个区域)。因此,两人最终剩余金钱总和为18965元,重量总和为333kg,远远小于重量限制。
  针对第六关由第四关可知,直接从起点直接到矿山最后回到终点,是一个玩家获得资金最大的时刻,24150元。且从起点到达矿山,以及从矿山回到终点的最短路线有多条,从起点到矿山,任选三条路线,至少有2个区域是相重合的。(原因:从起点出发只有两条路,3 个人必有两个人一起出发;从最后一个区域到达矿山,同起点出发)。从矿山到终点,无论三个人如何选择,必有一个人,至少与其他两个人的路线有重合。
  玩家一的行走路线为1(起点)-2-3-8-13-18(矿山)-19-20-25(终点);
  玩家二的行走路线为1(起点)-6-11-16-17-18(矿山)-23-24-25(矿山);玩家三的行走路线为1(起点)-2-7-12-17-18(矿山)-19-20-25(终点)。最后收益为求得三人的总收益为11370元。
  结论
  关卡1和关卡2都已知天气条件,因此考虑行走路线及是否在村庄买物资和挖矿时间的变化,对于不同行走路线分别考虑挖矿时间,得到最终结果。第四关忽略了较少出现的沙暴天气,只讨论了在晴朗和高温两种天气变化情况。第六关只讨论以最大的挖矿时间十六天获得的收益,没有详细讨论两人其它挖矿时间变化。
  参考文献:
  [1]任洛漪. 基于协同过滤推荐系统优化地图软件路线推荐[J].计算机产品与流通,2020,(09):133.
  [2]徐波,张玉敏.计及恶劣气象条件的系统状态检修决策模型[J].广东电力,2019,32(06):61-69.
  (作者单位:河北工程大学材料科学与工程学院)
其他文献
【摘 要】自从高校扩招以来,每年的应届毕业生出现井喷式的增长。但由于经济增速放缓、就业总量有限,高校毕业生的就业形势严峻。国务院总理李克强提出的“大众创业、万众创新”的号召在这样的背景下应运而生。在大学生创业过程中融资是最大的困难之一,出台和调整大学生创业融资政策,帮助大学生创业者解决融资难题,提高创业成功率是政府和相关部门的一项重要工作,形成社会各界的共同努力为大学生创业融资构建良好的氛围。  
期刊
【摘 要】随着如人工智能、大数据等的科学技术和经济的快速发展,物流业及其管理环境亦随之出现变革,提高企业的竞争优势变相即不断提高其物流管理水平。本文在总结传统物流管理弊端的基础上,分析了供应链环境下物流管理的特点、供应链管理和物流管理的关系、基于供应链环境的物流管理策略,最后提出了优化供应链环境下物流管理的方法。  【关键词】供应链;物流管理;完善策略  一、引言  供应链是在生产及流通过程中,围
期刊
【摘 要】近年来,职业院校越来越受到人们的重视,职业院校的教育工作者不仅要担负着指导学生知识与技能的责任,而且还肩负着培养学生思想素质的重要义务,尤其是在新时代的今天,我们越来越意识到培养专业能力强,综合素质高的复合型青年的必要性和迫切性,为此,本人理论联系实际,综合文献资料、经验总结、理论研究等研究方法就如何在新时代背景下高质量的展开职业院校的思想教育工作进行了具体的分析,给出了相应的参考建议。
期刊
【摘 要】随着全媒体时代的到来,大学英语教学的模式以及方法也发生了深刻的变化,同时全媒体时代为大学英语教学提供了更多的可能性,在全媒体技术的支撑下,大学英语智慧教学的实施得到了有效的推进。这一步提升了大学英语教学的有效性,同时也促进大学英语教学手段的创新发展,对于推动高等教育改革具有重要的意义。因此本文主要探讨全媒体时代下大学英语智慧教学模式的构建,希望能够为全媒体时代下大学英语教学提供一定的方法
期刊
【摘 要】随着我国现阶段市场经济的不断发展和壮大,跨文化现象对于商业活动的影响开始变得越来越重要了。英语已经成为全世界通用的语言,因此,商务英语的学习已经成为现在人们所重视的学习内容之一。商务英语作为国际贸易中的主要交流语言,其重要性也在无形中逐渐凸显出来。但是,由于各国家文化背景和历史地位的差异,商务英语在实际运用的过程中,很难会避免出现一些这样或者那样的问题。本文主要剖析了引发商务英语中跨文化
期刊
【摘 要】在新时代中,随着媒体和网络技术的发展,新兴文化的传播以及通讯条件的不断便利,高等教育学生的思想观念和价值观正在发生根本变化。鉴于学生家庭环境,教育环境和社会环境的多重作用所塑造的多样性特征,以及新时代社会发展对高职院校人才培养的需求,如何做好学生管理工作并鼓励其发展找到新的途径,包括思想教育,文化建设,技能创新和实践。这不仅是思想政治教育的关键,还是社会工匠需要解决的紧迫问题。  【关键
期刊
【摘 要】任务导向的教学模型强调任务的识别和执行是教学的主要方向,在这一教学过程中,学生的自教师指导学习能力和自教师参与能力得到了有效提高,引导学生从被动入学到主动研究。将任务型教学模式整合到高职院校的信息技术教学中,不仅符合高职院校学生的学习特点,而且可以帮助学生通过参与获得经验,从而改善和发展信息技术机会。在为发展综合技术型人才而发展专业高等教育的道路上。  【关键词】任务型教学法;信息技术;
期刊
【摘 要】就业是民生之本,创业是就业之根。倡导高校毕业生自主创业,能够在很大程度上缓解严峻的就业形势。但是,对于刚刚毕业的大学生而言,他们面临的最大问题是融资难。本文通过对辽宁省高校毕业生的创业融资情况进行调查,了解他们的创业融资现状,为下一阶段的解决融资难的问题提供决策参考。  【关键词】辽宁省;高校毕业生;创业融资  从2016年起,全国每年的应届高校毕业生都高达700万,2019年的应届高校
期刊
【摘 要】随着我国信息技术的不断发展,信息技术给人们的学习和工作带来了巨大的影响,尤其在教育领域,各个学校都积极得将微课引入课堂的教学中,力求构建出高效的智慧课堂。对于初中数学来说,由于上课方式存在一些问题,对学生的学习带来了不利的影响。因此,为了帮助学生更好的掌握数学知识,教师在教学的过程中应积极改变自身的教学思路,使用微课这一新颖的教学形式来展开教学,以此来提高学生的课堂学习质量。  【关键词
期刊
【摘 要】从现阶段的情况来看,虽然很多初中语文教师都加大了对于阅读教学的重视程度,但是却普遍存在教学效果堪忧的问题。阅读教学中,教师往往过多地重视阅读技巧的传授,忽视了学生在阅读过程中的感悟,进而导致阅读教学效果不佳,学生阅读能力提升困难。文章就从初中语文阅读教学的现状入手,探讨了一些针对初中语文阅读教学的策略,下文进行具体阐述。  【关键词】初中语文;阅读教学;现状;对策  前言  语文是初中阶
期刊