摘要
最小最大圈覆盖问题是旅行售货商问题的推广,该问题在无线传感器网络和无人机救灾等领域有着广泛的应用.目前关于最小最大圈覆盖问题的研究主要集中在近似算法方面,而缺少精确算法方面的结果.本文根据最小最大圈覆盖问题的组合特征,对该问题设计了基于动态规划策略的首个精确算法,时间复杂度为O^(*)(3^(n)).本文将对最小最大圈覆盖问题的求解分为两个阶段,第一个阶段是对问题的输入进行预处理,第二个阶段是在预处理的基础上求问题的最优解.有趣的是,两个阶段的方法都是基于动态规划策略设计的,这是本文处理最小最大圈覆盖问题的一个主要的特色.本文所证明的求到最优解的时间O^(*)(3^(n)),显著优于基于暴力搜索策略的枚举算法的时间.
The min-max cycle cover problem is a generalization of the traveling salesman problem.Wireless sensor networks,UAV disaster rescue,and other fields all leverage the challenge.While approximation solutions for the min-max cycle cover issue receive a lot of attention,research on exact algorithms is sparse.Based on the combinatoric characteristics of the problem,we design the first exact algorithm for the min-max cycle cover problem using the dynamic programming strategy.We prove that the time complexity of our algorithm is O^(*)(3^(n)).Our method for the min-max cycle cover problem consists of two stages.The first stage involves preprocessing the problem’s input,and the second stage involves finding the best solution to the problem based on the first stage’s results.Interestingly,the two stages are both based on the dynamic programming strategy.This is the main feature of our algorithm.The time complexity O^(*)(3^(n))of our algorithm is significantly better than that of the enumeration algorithm using brute-force search.
作者
袁森
陈开奇
李江坤
张鹏
Sen YUAN;Kaiqi CHEN;Jiangkun LI;Peng ZHANG(School of Software,Shandong University,Jinan 250101,China)
出处
《中国科学：信息科学》
CSCD
北大核心
2022年第6期960-970,共11页
Scientia Sinica(Informationis)
基金
国家自然科学基金(批准号:61972228,61672323)
山东省自然科学基金重大基础研究(批准号:ZR2021ZD15)
山东省自然科学基金(批准号:ZR2019MF072)资助项目。
