基于单目标线性规划的穿越沙漠策略研究

杨诚靖 沈炜宏 郭小敏

摘  要：单目标线性规划模型是在一组线性条件约束下，寻求某一单一目标的最优值，适用于极值问题的求解。弗洛伊德算法是一种通过动态规划的思想寻找给定的加权图中多源点间最短路径的算法。文章建立了基于背包问题的单目标线性规划模型，给出了在只有一名玩家，且事先已知游戏阶段天气状况下玩家的最优策略。通过弗洛伊德算法求解出了相应节点间的最短路径，得到了玩家的最终剩余资金。

关键词：单目标线性规划；弗洛伊德算法；最优策略

中图分类号：TP391    文献标识码：A  文章编号：2096-4706（2023）01-0127-05

Research on Desert Crossing Strategy Based on Single Objective Linear Programming

YANG Chengjing， SHEN Weihong， GUO Xiaomin

（Yancheng Institute of Technology， Yancheng  224051， China）

Abstract： The single objective linear programming model seeks the optimal value of a single objective under a set of linear condition constraints and is suitable for solving extreme value problems. Freudian algorithm is an algorithm to find the shortest path among multiple source nodes in a given weighted graph based on dynamic programming idea. In this paper， a single objective linear programming model based on the knapsack problem is established， and the optimal strategy is given under the condition of only one player and the weather in the game stage is known in advance. The shortest path among corresponding nodes is solved by Freudian algorithm， and the final remaining funds of players are obtained.

Keywords： single objective linear programming; Floyd algorithm; optimal strategy

0  引  言

地球上沙漠的總面积近3 370万平方千米，沙漠边缘地带以及沙漠中的山丘地区对人类、野生动物以及水循环具有重要意义。在广袤的沙漠中蕴藏了丰富的矿产资源、矿物质、石油，对资源进行开发可以缓解我国资源紧张的问题。穿越沙漠游戏中，在已知天气情况下要求玩家凭借一张地图，利用初始资金购买一定数量的水和食物，从起点出发，在沙漠中行走，玩家可在矿山、村庄补充资金或资源，目标是在规定时间内到达终点，并保留尽可能多的资金。

1  问题分析

穿越沙漠以在规定时间内到达终点，并保留尽可能多的资金为目标，制定玩家的最优策略，属于图论和优化问题[1]。在只有一名玩家的情况下，由于影响因素不同，所以为了统一衡量，将不同情况下的消耗转化为资金消耗。介于题目中所给的地图比较复杂，为优化地图，将地图中的区域转化为赋权图。……