基于最短路径的末世求生规划模型 An Eschatological Survival Programming Model Based on the Shortest Path

doi:10.12677/AAM.2022.117465

Advances in Applied Mathematics
Vol. 11 No. 07 ( 2022 ), Article ID: 53469 , 8 pages
10.12677/AAM.2022.117465

一种有约束最短路问题的线性整数规划模型

李沫，刘孝磊，孙玺菁

●How to Cite this Article

海军航空大学数学教研室，山东烟台

收稿日期：2022年6月6日；录用日期：2022年7月4日；发布日期：2022年7月11日

摘要

本文在求解路径长度最短的求生问题时建立了线性整数规划模型，解决了一类有约束最短路问题。通过引入折算距离矩阵，使得终点约束条件线性化，以路径总长度最短为目标，建立了线性整数规划模型，借助标识矩阵将隐枚举的过滤条件线性化，从而提高运算效率，最终对求得的全局最优解进行生存条件验证，验证通过。网络规模为588个节点，求出全局最优解用时60.5秒。

关键词

折算距离矩阵，过滤条件，线性整数规划

A Linear Integer Programming Model for Constrained Shortest Path Problem

Mo Li, Xiaolei Liu, Xijing Sun

Mathematics Teaching and Research Office of Naval Aviation University, Yantai Shandong

Received: Jun. 6^th, 2022; accepted: Jul. 4^th, 2022; published: Jul. 11^th, 2022

ABSTRACT

In this paper, a linear integer programming model is established to solve the survival problem with the shortest path length. By introducing the equivalent distance matrix, the end constraint condition is linearized. A linear integer programming model is established for shortest total path length of points. The filter conditions of implicit enumeration are designed by identification matrix, so that the operation efficiency is improved. The survival condition test of the global optimal solution is carried out, and the verification is passed. The model is simple and the algorithm efficiency is high. The network scale is 588 nodes, and it takes 60.5 seconds to find the global optimal solution.

Keywords:Conversion Distance Matrix, Filter Condition, Linear Integer Programming

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 背景和问题介绍

现有一款求生游戏，讲述这样一个游戏情节：病毒肆虐各国，人类文明险些毁灭，为了能够活下去，志同道合的伙伴集结起来，艰难求生。在游戏中，人物有两类重要的行为：一类是通过寻找各种食物来维持自身生存；另一类是通过各种御寒措施来降低自身寒冷程度从而提高生存能力。

将这两种行为对应为人物的两个特征：饥饿度——反映人物的饥饿状态，负值表示人物处于饥饿状态；温暖度——反映人物的寒冷程度，负值表示人类处于寒冷状态。两项指标值越低，生存难度越大。

以该游戏为背景，设计一个简化的场景。假设人物活动区域为一个空间区域，其在平面投影区域为矩形，空间区域中不同位置分布有补充点，可提供篝火或食物，人物从该区域某一个位置(起点)进入，从区域另一个位置(终点)出去，规定人物只能通过食物提升饥饿度，只能通过篝火提升温暖度，由于食物的数量不同，篝火的大小不同，提供的补充量不同。补充点类别、补充量和三维坐标数据已知。

人物行走将会消耗温暖度和饥饿度，且相同状态下两者消耗相同：平地上每走100米消耗5个单位；上坡每走100米消耗6个单位；下坡每走100米消耗4个单位。由于食物点或篝火点之间的间隔很近，可以近似的认为人物在两个补充点间行走的距离为两点间的直线距离。

人物从若要完成穿越之旅，在行进过程中要确保自身生存状态：

1) 抵达补充点时，饥饿度和温暖度均不得低于−5，否则人物死亡；

2) 人物在抵达目标点时，饥饿度和温暖度均不得小于−3，否则穿越任务失败。假设人物在起点准备出发时，温暖度和饥饿度均为10。应当如何规划穿越任务行进路线，使得人物能够存活，且行走总路程最短。

这个问题求解最优生存路径，优化目标为任务行走总路程最短，该问题可抽象为网络模型下的最短路问题，但该最短路问题有约束条件，可抽象为动态最短路问题，规模较大时求解存在一定困难。可采用A*算法 [1] [2]，双A*算法 [3] 和IDA*算法 [4]，这些算法对规模较大的问题，仅能求局部最优解。A*算法基于广度优先搜索，搜算效率高，但效率受问题规模影响较大。IDA*算法是A*算法的迭代延伸算法，该算法比A*算法更适用于较大规模问题，但算法关键在于确定节点扩展方式来减少搜索中的回溯计算，受节点顺序制约，且牺牲算法搜索速度。本文基于经典的最短路0~1整数规划的模型，通过引入标识矩阵，将生存条件约束线性化，从而构造了0~1线性整数规划问题，可求全局最优解。

2. 问题规模确定

根据问题的条件和假设，人物的饥饿度和温暖度是相互独立的，篝火点只能补充温暖度，食物点只能补充饥饿度，且在人物行走过程的不同状态下，对两者的消耗是相同的，可独立计算。为确保经过的路径长度最短，人物路线选择会沿着从起点到终点的直线方向走，考虑直线附近的补充点进行补充。

将补充点数据可视化，在xoy平面绘制补充点位置，其中红色圆圈表示篝火点，蓝色五角星表示食物点。红色三角形表示起点，黑色三角形表示终点。补充点在xoy面的投影分布如图1所示。从图像可以看出，在连接起点到终点的直线附近，篝火点和食物点数量充分，分布较均匀。根据上述补充策略，补充点应当在该直线附近选择。

Figure 1. Projection distribution of food points and bonfire points on xoy plane

图1. 食物点和篝火点在xoy面的投影分布

不妨设第i个节点坐标为 $(u_{i}, v_{i}, z_{i})$ ，其在xoy面上的投影坐标为 $(u_{i}, v_{i})$ ， $i = 1, \dots, N$ 。起点投影坐标 $(u_{0}, v_{0})$ ，终点投影坐标 $(u_{t}, v_{t})$ ，连接起点和终点的投影直线方程为

$v = \frac{v_{t} - v_{0}}{u_{t} - u_{0}} (u - u_{0}) + v_{0} .$

为了使总路线长度最短，会选择直线附近的补充点进行补充，为刻画第i个节点与投影直线的位置关系，计算

$l e n_{i} = | v_{i} - \frac{v_{t} - v_{0}}{u_{t} - u_{0}} (u_{i} - u_{0}) - v_{0} |,$

给定范围阈值l，选择满足 $l e n_{i} \leq l$ 的n个补充点为网络节点，会极大地减少问题的规模。若无解，说明节点删选过多，可提高l的取值进行调整。

3. 行走路径最短规划模型的建立

以删选出来的n个补充点为节点，构建网络模型，要解决的问题即在该网络中寻找从起点到终点，能够满足人物满足生存条件的总长度最短的路。

计算任意两个节点之间的距离矩阵 $D = {(d_{i j})}_{n \times n}$ ，其中

$d_{i j} = {\begin{array}{l} \sqrt{{(x_{i} - x_{j})}^{2} + {(y_{i} - y_{j})}^{2} + {(z_{i} - z_{j})}^{2}}, & i \neq j, \\ 0, & i = j . \end{array}$

由于人物爬坡行走、平地行走、小坡行走平地行走对温暖度和饥饿度的消耗不同，分别为 $a_{1}, a_{2}, a_{3}$ 每米，可以得到任意两个节点间的折算距离矩阵 $H = {(h_{i j})}_{n \times n}$ ，其中

$h_{i j} = {\begin{cases} \frac{a_{1} d_{i j}}{a_{2}}, z_{j} > z_{i}, \\ d_{i j}, z_{j} > z_{i}, \\ \frac{a_{3} d_{i j}}{a_{2}}, z_{j} < z_{i} . \end{cases}$

人物平地行走的消耗为 $a_{2}$ ，得到消耗矩阵 $W = {(w_{i j})}_{n \times n}$ ，有

$W = a_{2} H .$

构造任意两个节点间的补充矩阵 $E = {(e_{i j})}_{n \times n}$ ，其中

$e_{i j} = {\begin{cases} t_{i}, i \neq j, \\ 0, i = j . \end{cases}$

$e_{i j}$ 表示人物从节点i走到节点j，在节点i所补充的饥饿度和温暖度。

引入网络节点类别标识向量 $F = (f_{1}, f_{2}, \dots, f_{n})$ 及对应的补充量 $T = (t_{1}, t_{2}, \dots, t_{n})$ ，其中 $t_{i}$ 表示第i个节点的补充量，

$f_{i} = {\begin{cases} 0, 第 i 个补给点为篝火点, \\ 1, 第 i 个补给点为食物点 . \end{cases}$

人物在第i个节点获得补充后，继续行进到第j个节点，这个过程中如果人物温暖度或饥饿度消耗值大于补充值，人物生存困难程度加大，当人物的温暖度和饥饿度同时低于w时，人物死亡。为此，构造过滤矩阵 $Q = {(q_{i j})}_{n \times n}$ ，其中

$q_{i j} = {\begin{cases} 1, e_{i j} - w_{i j} > α, i \neq j, \\ 0, 其他 . \end{cases}$

为了提高人物生存可能性，确定路径时将不会选择 $q_{i j} = 0$ 的边。这实际上是模型求解隐枚举的过滤条件。在这个模型中，通过引入标识矩阵，将过滤条件线性化，在降低算法复杂度和提高算法效率方面成效显著。阈值 $α \geq w$ 取值越大，游戏人物生存的可能性越大，取值小，标识矩阵1元素数量越多，求解复杂度越高。

引入0~1决策变量

$x_{i j} = {\begin{cases} 1, 选择从第 i 个节点走到第 j 个节点, \\ 0, 否则 . \end{cases}$

其中 $i, j = 1, \dots, n$ 。

要求人物行走的总路线长度最短，故可以构建目标函数为

$\min \sum_{i = 1}^{n} \sum_{j = 1}^{n} x_{i j} d_{i j} .$

约束条件构造如下：

1) 根据过滤条件，只能在标识矩阵为1的元素对应的边中选择，于是有约束条件

$x_{i j} \leq q_{i j}, i, j = 1, \dots, n .$

该条件将不满足中间节点生存条件的情况过滤掉了。

2) 终点生存条件

人物在行进过程中，对温暖度和饥饿度的消耗是相同的，到达终点时，游戏人物的温暖度和饥饿度均不得低于 $σ$ ，由于在起点人物温暖度与饥饿度均为 $δ$ ，故在从起点到终点的过程中，温暖度和饥饿度的补充总量应满足约束

温暖度： $δ + \sum_{i = 1}^{n} \sum_{j = 1}^{n} (1 - f_{i}) e_{i j} x_{i j} - \sum_{i = 1}^{n} \sum_{j = 1}^{n} w_{i j} x_{i j} \geq σ,$

饥饿度： $δ + \sum_{i = 1}^{n} \sum_{j = 1}^{n} f_{i} e_{i j} x_{i j} - \sum_{i = 1}^{n} \sum_{j = 1}^{n} w_{i j} x_{i j} \geq σ .$

3) 路径约束条件 [5]

对于路的起点和终点，约束如下：

$\sum_{j = 1}^{n} x_{1 j} = 1, \sum_{j = 1}^{n} x_{j 1} = 0, \sum_{j = 1}^{n} x_{j n} = 1 .$

对于路径的中间节点，约束如下：

$\sum_{j = 1}^{n} u_{i j} = \sum_{j = 1}^{n} u_{j i}, i = 2, \dots, n - 1, i \neq j .$

上述4个约束即为经典最短路问题的约束条件。

由于本问题增加了过滤条件终点生存条件，与最短路的线性整数规划模型存在本质差别，故满足上述4个路径约束条件的未必一定能形成正确的路，很可能会出现图2所示的路线情况，即出现可往返的路段 $v_{4} \leftrightarrow v_{5}$ 的出现，因此需要增加约束条件

$x_{i j} + x_{j i} \leq 1, i, j = 1, \dots, n, i \neq j .$

于是构造如下的线性整数规划模型为：

$\begin{array}{l} \min \sum_{i = 1}^{n} \sum_{j = 1}^{n} x_{i j} d_{i j}, \\ s .t . {\begin{cases} x_{i j} \leq c_{i j}, i, j = 1, \dots, n, \\ δ + \sum_{i = 1}^{n} \sum_{j = 1}^{n} (1 - f_{i}) e_{i j} x_{i j} - \sum_{i = 1}^{n} \sum_{j = 1}^{n} w_{i j} x_{i j} \geq σ, \\ δ + \sum_{i = 1}^{n} \sum_{j = 1}^{n} f_{i} e_{i j} x_{i j} - \sum_{i = 1}^{n} \sum_{j = 1}^{n} w_{i j} x_{i j} \geq σ, \\ \sum_{j = 1}^{n} x_{1 j} = 1, \\ \sum_{j = 1}^{n} x_{j 1} = 0, \\ \sum_{j = 1}^{n} x_{j n} = 1, \\ \sum_{j = 1}^{n} x_{i j} = \sum_{j = 1}^{n} x_{j i}, i = 2, \dots, n - 1, i \neq j, \\ x_{i j} + x_{j i} \leq 1, i, j = 1, \dots, n, i \neq j, \overset{}{} \\ x_{i j} = 0 或 1. \overset{}{} \end{cases} \end{array}$

Figure 2. Error path sketch map

图2. 错误路径示意图

4. 模型求解、验证及结论

为解决有约束最短路问题，本文建立的模型为线性整数规划模型，该模型可求得全局最优解，当 $a_{1} = 6$ ， $a_{2} = 5$ ， $a_{3} = 4$ ， $δ = 10$ ， $σ = - 3$ 阈值 $α = w - 5$ 时，以 $l = 200$ 删选的270个补充点构建模型，求解计算用时6.2秒，采用全部 $N = 588$ 节点构建模型，求解计算用时60.5秒，两种规模下，求解的最优解相同。总长度最短的路径为

$\begin{array}{l} 起点 \to 34 \to 122 \to 192 \to 201 \to 231 \to 244 \to 255 \to 297 \\ \to 308 \to 327 \to 339 \to 346 \to 375 \to 403 \to 412 \to 435 \\ \to 453 \to 480 \to 502 \to 519 \to 538 \to 570 \to 终点 . \end{array}$

除了起点和终点，该路径共经过22个节点，其中11个篝火点，11个食物点，路径总长度为1058.2米。总路径长度最短的路线图见图3所示，线路图在xoy面投影见图4。

可以计算人物到达每个补充点时的温暖度和饥饿度，见表1，可见人物沿着该路径行走，抵达任何一个中间节点时，均满足生存条件，在抵达终点时温暖度和饥饿度均同时大于−3，满足生存条件。

当 $α \leq w$ 时，最优解不发生变化，但运算时间会随着 $α$ 取值减小而增加，当 $w < α \leq - 3$ 时，最优解不发生变化，但运算时间会随着 $α$ 取值增大而减少。当 $- 3 < α \leq - 2.8$ 时，生存条件增强，最优解发生变化，最优路径长度为1101米，途经11个食物点，12个篝火点，从求解可以看出，生存条件的增强以牺牲行走路线的长度为代价，任务去更多的节点进行了温暖度和饥饿度补充，从实际角度来看，绕行40多米，但温暖度和饥饿度提高值不多，性价比不高。参数 $α > - 2.8$ 时，已无法找到满足生存条件的路径。

Figure 3. The path with the shortest total travel length

图3. 行走总长度最短的路径

Figure 4. Path projection with the shortest total travel length

图4. 行走总长度最短的路径投影

Table 1. Comfort and satiety of game characters at each supply point

表1. 游戏人物到达每个补充点时的温暖度和饥饿度

5. 模型评价与扩展

本文通过构建了消耗矩阵，使得人物在中间节点和终点的生存条件得以线性化，引入的过滤矩阵使得过滤隐枚举条件得以线性化，最终建立线性整数规划问题解决了本问题中的有约束最短路问题，可计算全局最优解，且计算效率高，计算速度快。但在本问题中，温暖度和饱和度相互独立，且一个中间节点要么补充温暖度，要么补充饥饿度，若两者不是相互独立，且同一节点可对两者都进行补充时，模型不再适用。

文章引用

李沫,刘孝磊,孙玺菁. 基于最短路径的末世求生规划模型
An Eschatological Survival Programming Model Based on the Shortest Path[J]. 应用数学进展, 2022, 11(07): 4395-4402. https://doi.org/10.12677/AAM.2022.117465

参考文献

1. 彭彭. 基于A*算法的路径规划算法研究[D]: [硕士学位论文]. 马鞍山: 安徽工业大学, 2018.

2. 陈素琼. 基于A*算法的地图游戏寻径研究[D]: [硕士学位论文]. 重庆: 重庆师范大学, 2016.

3. 杨科选. 人工智能驯鹿算法及其在游戏中的应用研究[D]: [硕士学位论文]. 长沙: 中南大学, 2009.

4. 袁川涵. 一种基于网络地图的双A*算法的改进方法[J]. 科技视界, 2019(29): 148-149.

5. 柯健, 李帅, 郝沅君, 张倩倩. 虚拟场景中路径搜索技术的研究[J]. 苏州市职业大学学报, 2012, 23(2): 55-58.

6. 司守奎, 孙玺菁. 数学建模算法与应用[M]. 第三版. 北京: 国防工业出版社, 2021: 74-75.

期刊菜单