贪心与回溯算法在城市马拉松路线规划中的实践  

Practice of Greedy and Backtracking Algorithm in City Marathon Route Planning

作　　者：王友才 陈焱焱[1] 徐玉兵[1] 刘子含 潘瑞 何子军[1] 杨先军[1] 孙怡宁[1] WANG You-Cai;CHEN Yan-Yan;XU Yu-Bing;LIU Zi-Han;PAN Rui;HE Zi-Jun;YANG Xian-Jun;SUN Yi-Ning(Hefei Institutes of Physical Science,Chinese Academy of Sciences,Hefei 230031,China;University of Science and Technology of China,Hefei 230026,China)

机构地区：[1]中国科学院合肥物质科学研究院,合肥230031 [2]中国科学技术大学,合肥230026

出　　处：《计算机系统应用》2023年第3期275-281,共7页Computer Systems & Applications

基　　金：国家重点研发计划(2021YFF0306402);安徽省科技重大专项(202103a07020004)。

摘　　要：针对目前城市马拉松路线人工规划效率低下的问题,本文采用贪心和回溯算法进行城市马拉松路线智能规划,具体方法是:通过城市路网信息构建由经纬度坐标点拓扑关系连接而成的路网,采用贪心和回溯算法对坐标点进行遍历搜索,结合城市马拉松路线特殊要求,运用直接逼近、启发式远离、启发式靠近和方向预估等策略实现路线的智能规划.在此基础上,提出一种综合POI热度值、道路宽度适宜度、路线畅通指数、过弯舒适度以及POI密集度5个维度的马拉松路线评估方法.最后,开展了北京、合肥马拉松人工和智能规划路线对比分析,结果表明所采用的方法可快速高效实现马拉松路线规划.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.

关 键 词：城市马拉松 路线规划 评估体系 启发式策略 贪心算法 回溯 

分 类 号：G822.8[文化科学—体育训练] TP18[文化科学—体育学]