加拿大旅行者问题

• 作者: 徐寅峰 朱志军
• 来源期刊: 系统工程理论方法应用
• 学科: 工学
• 关键词: 加拿大旅行者问题 确定型可恢复加拿大旅行者问题 竞争算法 竞争比
• 年，卷（期）: 2003,（2）
• 所属期刊栏目: 学术论文
• 页码范围: 177-181
• 页数: 5页
• 分类号: TB114.1
• 字数: 5577字
• 语种: 中文
• DOI: 10.3969/j.issn.1005-2542.2003.02.019

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐寅峰	西安交通大学管理学院	138	1984	23.0	37.0
2	朱志军	西安交通大学管理学院	14	337	9.0	14.0