论文部分内容阅读
针对加拿大旅行者问题,分析其主要变形--确定型可恢复的加拿大旅行者问题.考虑堵塞边动态产生,一个遇到且堵塞边在时间l(x,x)后可以自动恢复情况下的道路选择.通常对于在线算法可以从两个方面进行评价:最坏情形分析和竞争比分析.本文先设计了求解最坏情形下旅行时间最短的标号算法并分析了其计算复杂性.而后在竞争比分析中,设计了基于贪婪原则的选路策略,并对其进行了竞争比分析,证明了该贪婪策略对于确定型可恢复加拿大旅行者问题的竞争比为(k+2)/2.