基于Floyd 算法的穿越沙漠游戏研究

柳 堰 唐龙海 梁晓瑞

（1、太原理工大学土木工程学院,山西 太原030024 2、太原理工大学电气与动力工程学院,山西 太原030024）

随着大数据时代的到来,针对本问题建立的模型,模型的优点在于通过假设使得问题大大简化。然而这也是该模型最大的弊病所在,并没有考虑多次进行挖矿以及连续多天挖矿包括多次在村庄进行补给的情况,不考虑特殊因素的情况下,由于只要有时间挖矿,收益就会大于亏损,故最优解应该存在于多次、多天连续挖矿并进行多次往返村庄购买补给的情况中。本文中所使用的Floyd 算法相较于旅行商模型、遗传算法等求解最优路径相比,可以得到精确解,而不仅仅是随机解,用图论模型形象直观的体现了路线之间的关系。

1 问题分析

首先利用基于Floyd 算法,得出目标函数,即到达终点所剩资金（包含退还食物和水的资金）的最大值的路径即为最优路径。第一关和第二关模型类似,只是第二关的地图稍复杂。第三关只有一名玩家,且只知道当天的天气情况,但已知十天之内不会出现沙暴天气。需要使用Floyed 算法遍历各元素求出最短路径。由于玩家只知道当天的天气情况,因此建立十天之内的概率天气矩阵,第四关仍然只有一名玩家,也只知道当天的天气情况,但已知30 天内较少出现沙暴天气,无非在调整概率天气矩阵时,添加较低比重的沙暴天气即可。第五关有两名玩家,且每天天气情况已知。在游戏途中,由于相同路程和相同行为（这里指挖矿和村庄购买）的开销成倍增加,遍历元素之间的最优路径之后,使两位玩家尽量避免相同行程和相同的行为,最后对每种组合方式进行分类讨论。

2 模型的建立与求解

首先建立地图上每个元素之间的距离矩阵,相邻元素用1来表示,地图上不相邻元素之间设为无穷大,在第一关中最终可以得到一个27×27 的距离矩阵。第二关元素较多,找出规律进行矩阵的建立。最终可以得到64×64 的距离矩阵。具体可以分为以下几种情况：若该元素位于奇数行,则可以分为中间列（左右均有相邻元素）、左列（左边无相邻元素而右边有相邻元素）、右列（右边无相邻元素而左边有相邻元素）。在这三种情况中,每种情况又可以分为最上行（以上无其他元素）和其他行（以上有其他元素）；若该元素位于偶数行,则依然可以分为中间列、左列和右列。在这三种情况中,每种情况也可以分为最下行（以下无其他元素）和其他行（以下有其他元素）。如图1 所示。

进行分类后,即可按照与之临近关系判断是否相邻,同时设置天气矩阵,设晴天为1,高温为2,沙暴为3。玩家可以在村庄和起点购买食物和水,由于村庄购买资源的价格为基础价格的2 倍,因此应该尽可能在起点购买所有的食物和水；又由于背包承载质量1200kg 的限制,玩家不得不在村庄购买物资,助力于矿山挖矿和到达终点。做出如下约束：在起点处玩家应尽可能多的购买并且保证能够到达村庄,但不能超过1200kg；所有的水和食物恰好能在到达终点时消耗完。可以通过约束条件得到购买食物和水的分配优化模型。具体算式如下：

图1 第二关元素分类

通过matlab 可以得到最优解z 以及对应最优解的决策变量x。第一种路径为不在村庄买食物和水以及不在矿山挖矿（可以经过村庄和矿山）,直接到达终点；第二种情况是先经过村庄购买水和食物。若所带补给足够到达终点,则一定不会去村庄进行购买,故这种情况与第一种情况互斥。第三种情况为到达矿山进行挖矿,再到终点；最后一种情况是既经过矿山进行挖矿,又经过村庄进行购买（由于假设所限,只能购买一次或者挖矿一次）。进入村庄进行购买的目的很单纯,即食物和水不足以支撑到游戏结束,而进入矿山挖矿,可能有多重目的和情况：第一种情况是补给足够,希望能够多赚钱,第二种情况是补给不够,需要进入矿山挖矿赚钱,其后必经过村庄购买补给。这里又可以细分为两种情况：第一种为原先补给是足够的,然而挖矿消耗量大,导致补给不足,第二种情况是原先补给即不足以支撑游戏结束。Floyd 算法,又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。在此使用Floyd 算法,遍历起点、终点、村庄、矿山等特殊元素之间的最短路径。在到达终点的前提下,列出目标函数：剩余资金=初始资金+挖矿收益+终点退回资金- 起点及村庄购买补给的花费,即m=q+h+r-s-c,对所有情况进行分类讨论,求解出目标函数（资金剩余量）的最大值,即为最优策略。

第二关仅有一名玩家,地图中没有村庄,不存在沙暴天气而且只知道当天的天气情况。首先依然需要建立距离矩阵和随机天气矩阵。由于地图边界不规则,在此也采取人工遍历的方式求出距离矩阵。概率天气矩阵设置晴天的概率分别为0.2、0.5、0.8。由于本题目不含有村庄,故选择元素时仅有两种情况,第一种情况就是直接到达终点,行走的天数是确定的（已知不存在沙暴天气）,而天气是未知的。通过设置概率天气函数,即可求出在设定概率下目标函数值。第二种情况是经过矿山,由于在晴朗天气,挖矿一天盈利35 元,高温天气,挖矿一天需要亏损205 元,故若持续为晴朗天气,则可连续挖矿,若有高温天气,则坚决不挖矿,当天立即离开。

第四关与第三关模型类似,仅仅是题目中给出了沙暴天气出现的概率较小,故在概率矩阵设定时,需要将沙暴天气概率设置为较小即可,最后在时间截止之前到达终点,而且在地图中出现了村庄,这样,本题可以抛开假设1 和2,多次往返于村庄进行补给和矿山进行挖矿。分别按照不同天气概率对直达终点和经过矿山（无论是否挖矿）进行目标函数值的求解,最终可以比对出在不同概率条件下的最优策略,由此可得,晴天的出现有助于玩家在矿山处通过挖矿获得较大收益。

第五关共有两位玩家进行游戏,最先注意要避免的问题是两位玩家在同一天有相同的行程或者进行相同的操作。所以在本关中,依旧使用Floyd 算法遍历元素之间的最短路径之后,两位玩家对几种不同的最短路径进行排列组合,求得此时的目标函数值。若组合之间有路程或操作的重合,则在某位玩家路线做细微扰动,比较前后的目标函数值,进行讨论。

第六关理论上有两种讨论方法,都是博弈论的相关内容,第一种情况是玩家是敌对的,这里需要求解纳什均衡的问题。纳什均衡,即非合作博弈均衡,也就是无论对方的策略选择如何,当事人一方都会选择某个确定的策略。这种情况保证自己利益的最大化,因此在这种均衡状态下各个人应该是余额一致的,选一种各自余额最高的均衡状态即可；第二种情况是玩家可以相互之间合作,那就是帕累托最优问题,帕累托最优,也即帕累托效率,是指资源分配的一种理想状态,最后选择一种各位玩家余额最接近的情况即可。本文贯穿始终的Floyd 算法是本文的一大特点,另外通过合理的假设,也使得各问题得以大大简化。全文各新旧模型的综合运用,令全文思路清晰,条理分明,充满了创新性。最后,纵观全文,客观的评价了模型的优劣并进行了模型的延伸。综合考虑到模型具有的优化功能,可以将其推广至物流、运输等重要领域。这对今后资源的节约以及社会经济效益的提高具有重要的参考价值。

3 结论

本文所涉及到的多种模型,针对规划穿越沙漠路径中最优路径的问题,提出一种基于最短路径规划算法,并通过增加天气情况、物资和矿山等不确定性情况,建立基于以上因素影响下最优路径,通过图论的比较,在不同方案中寻找效果最好的方案。结果表明,在天气已知的情况下,所建立的数学模型较为灵活,仿真结果表明,此数学模型算法有较强的实用性,可以推广至物流、运输等重要领域,这对今后的资源节约以及社会经济效益的提高具有重要的参考价值。