摘要
针对加拿大旅行者问题 ,分析其主要变形——确定型可恢复的加拿大旅行者问题。考虑堵塞边动态产生 ,一个遇到且堵塞边在时间 l( x,x)后可以自动恢复情况下的道路选择。通常对于在线算法可以从两个方面进行评价 :最坏情形分析和竞争比分析。本文先设计了求解最坏情形下旅行时间最短的标号算法并分析了其计算复杂性。而后在竞争比分析中 ,设计了基于贪婪原则的选路策略 ,并对其进行了竞争比分析 ,证明了该贪婪策略对于确定型可恢复加拿大旅行者问题的竞争比为 ( k+ 2 )
The Canadian Traveler Problem and its variations are considered. Devising a travel strategy under the condition that each site is associated with a recovery time l(x,x) to reopen any blocked road that is adjacent to it is the main problem of this paper. The quality of online algorithm is usually measured based on two alternate criteria: competitive ratio and worst case performance. In the worst case performance analysis, the paper devised an algorithm to get the optimal worst case travel time and the algorithm complexity is considered. Greedy Strategy is put forward in the competitive analysis and k+22 is proved to be the competitive ratio.
出处
《系统工程理论方法应用》
2003年第2期177-181,共5页
Systems Engineering Theory·Methodology·Applications
基金
国家自然科学基金资助项目 ( 7980 0 0 4)
关键词
加拿大旅行者问题
道路选择
旅行时间
竞争比
标号算法
贪婪策略
堵塞边
the Canadian traveler problem
the deterministic recoverable Canadian traveler problem
competitive algorithm
competitive Ratio
