基于最短路径的末世求生规划模型

An Eschatological Survival Programming Model Based on the Shortest Path

摘要: 本文研究了虚拟游戏背景下，穿越路线最短的末世求生问题。通过引入等效距离矩阵，使得终点约束条件线性化，以途经补给点数量最少为目标，建立了线性整数规划模型，通过删选原则降低补给点个数，借助标识矩阵设计隐枚举的过滤条件，从而提高运算效率，最终对求得的全局最优解进行生存条件验证，验证通过。本模型准确、简单、算法效率高，问题中共计给出补给点588个，求出全局最优解用时6.2秒。

Abstract: This paper studies the problem of survival with the shortest crossing route in the eschatology of virtual games. By introducing the equivalent distance matrix, the end constraint condition is line-arized. A linear integer programming model is established to minimize the number of supply points. The number of supply points is reduced through the deletion principle. The filter conditions of im-plicit enumeration are designed by identification matrix, so that the operation efficiency is im-proved. 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. A total of 588 supply points are given, and it takes 6.2 seconds to find the global optimal solution.