Optimization Study of Desert Traversing Routes Based on Floyd and Greedy Algorithms

Abstract

This paper is based on a desert traversal game to reach the endpoint within the specified time and keep as much money as possible, so it is necessary to give a reasonable choice of routes and optimize the routes. This paper defines the adjacency matrix of the graph and borrows the Floyd algorithm to get the two shortest routes: "to mine" and "not to mine"; secondly, based on the basic assumption that "players will give priority to routes containing villages", the shortest routes are optimized and the shortest routes are optimized to be "to mine" and "not to mine". Secondly, based on the basic assumption that "players will prefer the route containing villages", the shortest route is optimized to the shortest route passing through villages; Thirdly, based on the objective of "retaining as much money as possible", mining in mines is divided into "continuous mining" and "non-continuous mining". "Finally, the greedy method is used to obtain the funds of the three cases of the two routes are 9410-yuan, 10430 yuan, and 9800 yuan, and the remaining funds are compared to obtain the optimal route for the player to pass the game. Afterward, the weather probability of each day is estimated and the weather sequence is randomly generated; secondly, combining the map information and the weather condition of the day, the dynamic strategy should be adopted by the player given; again, Monte Carlo simulation is used to simulate the whole decision-making process, and the performance of the model is optimized by adjusting the parameters of the model.