The canadian traveller problem and its competitive analysis
详细信息 查看全文
- 作者：Yinfeng Xu ; Maolin Hu ; Bing Su ; Binhai Zhu and Zhijun Zhu
- 关键词：Online algorithms ; Competitive analysis ; Greedy strategy ; Comparison strategy
- 刊名：Journal of Combinatorial Optimization
- 出版年：2009
- 出版时间：August, 2009
- 年：2009
- 卷：18
- 期：2
- 页码：195-205
- 全文大小：269.1 KB
文摘
From the online point of view, we study the Canadian Traveller Problem (CTP), in which the traveller knows in advance the structure of the graph and the costs of all edges. However, some edges may fail and the traveller only observes that upon reaching an adjacent vertex of the blocked edge. The goal is to find the least-cost route from the source O to the destination D, more precisely, to find an adaptive strategy minimizing the competitive ratio, which compares the performance of this strategy with that of a hypothetical offline algorithm that knows the entire topology in advance. In this paper, we present two adaptive strategies—a greedy or myopic strategy and a comparison strategy combining the greedy strategy and the reposition strategy in which the traveller backtracks to the source every time when he/she sees a failed edge. We prove tight competitive ratios of 2 k+1−1 and 2k+1 respectively for the two strategies, where k is the number of failed edges in the graph. Finally, we propose an explanation of why the greedy strategy and the comparison strategy are usually preferred by drivers in an urban traffic environment, based on an argument related to the length of the second-shortest path in a grid graph.