Education, Science, Technology, Innovation and Life
Open Access
Sign In

Desert Route Planning Based on Dynamic Programming

Download as PDF

DOI: 10.23977/tmte.2021.040107 | Downloads: 2 | Views: 126


Lingnan Xu 1


1 North China Electric Power University, Baoding, Hebei 071000

Corresponding Author

Lingnan Xu


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.


optimal strategy, dynamic programming, backtracking


Lingnan Xu. Desert Route Planning Based on Dynamic Programming. Tourism Management and Technology Economy (2021) 4: 33-37. DOI:


[1] Xu Guogen, Zhao Housui, Huang Zhiyong. Optimization method and its MATLAB implementation: Xu Guogen, Zhao Housui, Huang Zhiyong, 2018-07
[2] Li Shengbing, Li Hangmin. Interpretation of management terminology: Enterprise Management Press, 2007

Downloads: 281
Visits: 22945

All published work is licensed under a Creative Commons Attribution 4.0 International License.

Copyright © 2016 - 2031 Clausius Scientific Press Inc. All Rights Reserved.