Desert Route Planning Based on Dynamic Programming
Lingnan Xu · Tourism Management and Technology Economy · 2021
For the problem of crossing desert, the choice of path is very important. In this paper, the regions and adjacent parts of a map are regarded as nodes and edges respectively, so that a connected undirected graph is established. Under this circumstance, we develop two strategies to determine the optimal strategy to be adopted by players. The first strategy is to solve the Dijkstra algorithm of the shortest path between specified nodes. While the second strategy is to get out of the desert after replenishing resources and obtaining funds through key nodes within a specified period of time. A simplified road map represented by weights is obtained through equivalence, and by using the idea of dynamic programming, the problem is abstracted into solving the optimal solution of each stage. Meanwhile the resource allocation of initial knapsack is considered through 0-1 programming, and the idea of backtracking is used. Under the constraint of the upper limit of load, all feasible schemes are considered to obtain the maximum profit.