Author(s)

Yuan Tang, Ding Luo, Banghan Xu

Corresponding Author

Yuan Tang

ABSTRACT

The background is a game of "crossing the desert", which requires players to solve the player's optimal strategy under the given game rules. The goal of the game is to arrive at the end of the game within a specified time, with as much money as possible .In order to reduce resource consumption, players should give priority to the shortest path from the starting point through mines and villages to the destination, and then discuss the optimal scheme in detail. When calculating the shortest path, the map is abstracted into a no right map and transformed into a matrix form, and then the breadth first search algorithm (BFS) is used to solve the problem. On this basis, the problem is considered: for a single player with known weather in a specified time, the game is played. Firstly, according to whether there are villages or mines, this paper discusses the optimal strategy of players under different map types. The first pass and the second pass belong to the type of villages with mines, and mining can bring net income. In this regard, firstly, BFS is used to find the shortest path through the mine, and combined with the specific weather to calculate the resource consumption on the path that players must pass through. In order to increase the income, allocate as much time as possible to the mining, and then determine the mining scheme and the best village supply scheme. Then, considering the overall situation, the total resource consumption and village supply situation in the whole process are calculated, and the optimal resource allocation strategy is obtained by using linear programming. To sum up, it is the optimal strategy. According to the above strategies, the optimal strategy of the first level is to go to the mine along the shortest path 1-25-26-23-22-9-15-13-12, then to the village for replenishment after 7 days of mining, then continue to dig for 3 days, and finally reach the terminal point along 12-14-16-17-21-27, with the remaining capital of 10440 yuan; the second pass is to mine for 5 days along 1-2-10-11-20-21-29-30, return to the mine for 9 days after mining, and finally arrive at the terminal point along 39-47-56-64The remaining capital is 12505 yuan. In this paper, programming, logical reasoning and numerical calculation are used to obtain the optimal strategy through BFS, linear programming and game theory. Because some problems are easier to understand with logic proof than with code, this paper uses the method of combining program and reasoning to find the "shortest path" to solve the problem.

KEYWORDS

Logic proof, Breadth First Search, Path planning