摘要
以旅行者的旅行时间最短为优化目标,用竞争分析的方法考虑了自然灾害环境中的在线导航问题,提出了旅行者在受灾区行走的上界控制策略,通过竞争比和竞争性能分析,结果表明上界控制策略具有该问题最优竞争比2k+1,并且竞争性能得到了提高.
In this paper, by using a method of competitive analysis, the online navigating problem in the environment of natural disasters to realize the aim of a less-minimum-time for the online traveling is studied. We give the strategy of controlling upper bound and its algorithmic model. Through analyzing the competitive ratio and competitive performance of the strategy, the result clearly shows that the strategy of controlling upper bound matches well the optimal competitive ratio 2k ＋ 1 of the problem and its competitive performance is advanced.
出处
《宁夏师范学院学报》
2009年第6期5-10,共6页
Journal of Ningxia Normal University
基金
宁夏自然科学基金资助项目(NZ08172)
宁夏师范学院校级科研项目(YB08024)
关键词
在线导航问题
上界控制策略
竞争比
竞争性能
Online navigating problem
Strategy of controlling upper bound
Sompetitive ratio
Competitive performance
