《明日之后》模拟生存游戏线路规划

《明日之后》是网易开发的一款生存类游戏，讲述这样一个游戏情节：病毒肆虐各国，人类文明险些毁灭，为了能够在末世中“活下去”，志同道合的伙伴集结起来，一起在病毒蔓延、感染者遍地、资源有限、天气严酷的世界中求生。在游戏中，人物有两类重要的行为，一类是要通过寻找各种食物来维持自身生存，另一类是通过各种御寒措施来降低自身的寒冷程度从而提高生存能力，我们把这两类行为对应到人物的两个特征，前者称为饱食度，刻画人物饥饿的状态，饱食度为负表示处于饥饿状态，饱食度越小，人物生存越难；后者称为舒适度，刻画人物寒冷的状态，舒适度为负表示处于寒冷状态，舒适度越小，游戏人物生存越难。

以该游戏为背景，我们设计这样一个简化的场景。假设游戏人物活动区域为一个空间区域，空间区域中不同位置分布有一些食物和篝火，人物从该区域某一个位置进入，从区域另一个位置出去，如下图所示：

游戏人物在该区域行走的规则如下：

（1） 人物到达食物点吃到食物，其饱食度将提高，提高程度依赖于食物数量。

（2） 人物到达篝火位置，其舒适度将提高，提高程度依赖于篝火的大小。

（3） 人物在平路（即 Z 坐标相同）行走 100 米，饱食度和舒适度均降低 5 个单位，

若走上坡路（Z 坐标增加），饱食度和舒适度每走 100 米均降低 6 个单位，若

走下坡路（Z 坐标减少），饱食度和舒适度每走 100 米均降低 4 个单位。假设

上、下坡已经等效为两点之间直线行走。

（4） 当人物到达食物点或篝火点，若饱食度和舒适度中任意一个小于-5，人物将死

亡，无法通过食物或篝火提高饱食度或舒适度。

（5） 假设人物在开始位置时的饱食度和舒适度均为 10。

（6） 要求人物到达终点时，饱食度和舒适度均不小于-3。

附件中给出了食物点和篝火点的信息，第一列为点的编号，第 2-4 列为食物点或篝火

点的位置坐标，第一行为起点信息，最后一行为终点信息；第 5 列为点的类型，1 表示该

点为食物点，0 表示该点为篝火点，第 6 列为人物位于该点时可通过补充食物或利用篝火

提高其饱食度或舒适度的大小，间接代表了该处食物的数量或篝火的大小。 请你们建立

数学模型和算法解决以下问题：

**问题 1：**规划该人物从起点到终点的路线（用序号表示），使其经过的食物点和篝火点

的次数最少。

**问题 2：**在第一问的基础上，进一步考虑人物行走的路径尽可能短，规划其从起点到

达终点的路线（用序号表示）。

**问题 3：**在篝火点，游戏人物可以制作火把携带，制作火把将使得饱食度降低 0.5 个

单位，但携带的火把能支持人物行走 20 米而不降低舒适度。请在第一问和第二问的规

划路线基础上，进一步考虑人物可制作火把携带的方案，使得人物到达终点后的饱食

度和舒适度尽可能高。

图片来源：http://www.laoshoucun.com/ 页游