基于图论的路线规划研究蒋淼涛--中国期刊网

字体：大中小

首页> 原创作品> 正文

基于图论的路线规划研究蒋淼涛

发表时间：2020/10/9 来源：《论证与研究》2020年8期作者：蒋淼涛周政 Q

[导读] 摘要：本文主要针对优化沙漠模型游戏决策的研究。利用剩余资金最多的目标入手，考虑每天天气已知、玩家单一的情况，做了图论与动态规划相结合的数学方法，将地图抽象为邻接矩阵，以Floyd算法化简为仅包含起点、终点、村庄、矿山四个特殊点为节点、最短路径长度为权值的最简无向图。首先结合剩余资金最大化及其衍生出的在矿山工作时间最久、结束时剩余物资最少等条件，以线性规划模型对资源购买方案进行剪枝优化。其次该模型的

                                                    蒋淼涛周政吕思思
                                     （江南大学江苏省无锡市 214122）
        摘要：本文主要针对优化沙漠模型游戏决策的研究。利用剩余资金最多的目标入手，考虑每天天气已知、玩家单一的情况，做了图论与动态规划相结合的数学方法，将地图抽象为邻接矩阵，以Floyd算法化简为仅包含起点、终点、村庄、矿山四个特殊点为节点、最短路径长度为权值的最简无向图。首先结合剩余资金最大化及其衍生出的在矿山工作时间最久、结束时剩余物资最少等条件，以线性规划模型对资源购买方案进行剪枝优化。其次该模型的优点是模型的决策依照实际逻辑判断，且实现了地图化简，使模型和编程简洁明了、可读性强。最后，利用Matlab对决策方案进行检验，从而确定模型的合理性与实用性较好。
        关键词：图论与动态规划；邻接矩阵；线性规划模型
        1 引言
        本文设计了一个类似沙漠掘金的小游戏。玩家可在起点或村庄购买水和食物等资源，在矿山挖矿获得资金，不同的天气和玩家的行动会产生不同的单日资源耗费。游戏最终目标是希望玩家在游戏的基本规则内，对各种情况提出决策方案，使玩家在中途不耗尽任何资源的情况下，在规定时间内到达终点并尽可能获得更多的资金。根据以下不同的游戏规则建立不同的数学模型，提出相应的一般情况下能使玩家在规定时间内到达终点，并保留尽可能多的资金的行动策略。
        2、模型的建立与求解
        首先以图论[3]方法将地图抽象为包括起点、终点、村庄、矿山四个特殊点和连接特殊点的边的无向图，使问题简化，便于思考决策。第一关的地图抽象简化出的图论模型如下图1所示。

                                                        图1第一关抽象地图
       上图1是由点集和边集组成，边集中的任意一条边都能够在点集中找到与之对应的一对节点，且对于任意一对节点，由于同一时刻整个地图的天气状况相同，所以局部情况下玩家任意方向的一次短期行走的消耗是相同的。但因天气变化消耗也会变化，所以应选择把最短距离作为它们的对应边的权重。根据所给地图用邻接矩阵来记录区域之间的位置关系，用1表示两区域相邻，(inf)表示区域与区域不相邻。再利用图论中最短优先算法——Floyd算法进行求解，找到特殊点间最短路径，得到各特殊点间的最短距离，记为Disi,j，i为起始点编号，j为终止点编号。将地图上特殊点间最短路径距离作为最小权值赋给特殊边，得出最简无向图。因村庄不耗费额外资源，同距离情况下应优先选择经过村庄的路线，所以可以略去起点直达矿山和矿山直达终点两条边。由此可把图1简化成下图2。

图2第一关最简无向图
下面各关卡地图的简化过程与此相同，故不再赘述。整个过程中水和食物资源的消耗包括：（1）原地停留的消耗：在途中，玩家可选择停留在原地不动，此时资源有所消耗，且消耗量还与天气状况和玩家行为相关。剩余水的变化：

        先将从起点到终点的最短路径和经过矿山的最短路径两种情况进行比较可得：玩家经过矿山赚取资金，可使最后获得的资金数最多。然后需要保证在矿山赚取的资金要能够高于往返村庄消耗资源的总价格。为使所获得的资金数最多，要使玩家在矿山的停留时间最长，需要找到从矿山到村庄或终点的最迟出发期限。
        结论
        模型的决策逻辑依照实际，易于实现和理解，运用图论的Floyd动态规划算法将地图简化为四节点的无向图，使模型更简洁明了、易于编程求解。针为了提供决策依据，本模型联系图论模型抽象出邻接矩阵，用Floyd算法求各点间最短路径，算法还具有可行性。建立的模型收敛困难，奖励函数需要提前设置，且对结果的影响比较大。我们不难发现这是一类图论、动态规划、强化学习问题，我们通过建立一个多目标的模型寻找各条件下的最优解。这个模型不仅仅适用于具体条件参数下的最优决策问题，还具有足够的普适性，对于一般情况下的路径规划、运筹决策类问题的求解都可以起到指导作用，在生产生活中都发挥着重要的作用。
        参考文献：
        [1]封硕, 谢廷船, 康靖, & 李建良. (2020). 基于双粒子群算法的矿井搜救机器人路径规划. 工矿自动化, (1), 11.
        [2]谢识予. (2001). 有限理性条件下的进化博弈理论. 上海财经大学学报, 3(5), 3-9.