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

An Eschatological Survival Programming Model Based on the Shortest Path

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

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.