Practice of Greedy and Backtracking Algorithm in City Marathon Route Planning
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    Manual planning of city marathon routes has low efficiency. In view of this, this study adopts a greedy and backtracking algorithm to carry out intelligent planning of a city marathon route. The specific method is described as follows. A road network connected by the topological relationship of longitude and latitude coordinate points is built through the urban road network information, and a traversal search is performed by the greedy and backtracking algorithm on the coordinate points. In addition, according to the special requirements of the city marathon route, strategies are adopted, such as direct approximation, heuristic distance, heuristic approach, and direction estimation, so as to realize the intelligent planning of the route. On this basis, a marathon route evaluation method is proposed, which integrates five dimensions including POI heat value, road width suitability, route smoothness index, comfort for turning, and POI density. Finally, a comparative analysis of artificial and intelligent route planning for Beijing and Hefei marathons is carried out. The results show that the proposed method can realize fast and efficient marathon route planning.

    Reference
    Related
    Cited by
Get Citation

王友才,陈焱焱,徐玉兵,刘子含,潘瑞,何子军,杨先军,孙怡宁.贪心与回溯算法在城市马拉松路线规划中的实践.计算机系统应用,2023,32(3):275-281

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:July 23,2022
  • Revised:August 26,2022
  • Adopted:
  • Online: November 29,2022
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-3
Address:4# South Fourth Street, Zhongguancun,Haidian, Beijing,Postal Code:100190
Phone:010-62661041 Fax: Email:csa (a) iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063