摘要
经典的优化理论大多是在已知条件不变的基础上给出最优方案 (即最优解 ) ,其最优性在条件发生变化时就会失去。局内问题与竞争算法则是针对特定的优化问题来研究这样的方法 ,它在变化因素的每一个特例中都能给出一个方案 ,使得这一方案所得到的解离最优方案给出的解总在一定的比例之内。本文首先提出了局内电梯调度问题 ,设计了解决该问题的两个不同的竞争算法 ,并证明了这两个竞争算法的竞争比分别为k+2 和n-k +1,其中k为电梯的个数 ,n为楼层数。
Most traditional optimization theories produce the optimal solutions for problems at hand on the basis that the known conditions are unchanged, which may lost their optimality in most cases with conditions vary. The researches on on-line problem and competitive algorithm try to explore strategies which can produce solutions that is in a certain range proportional to the optimal solution for a given problem even in worst cases. This paper gives two competitive algorithms for on-line scheduling of k elevator problem using the position maintaining occupied strategy, which have k+2 and n-k+1 competitive ratios respectively, where k is the number of elevators and n is the number of floors of a construction.
出处
《航空计算技术》
2001年第2期47-50,共4页
Aeronautical Computing Technique
关键词
局内问题
优化竞争算法
竞争比
电梯调度问题
on-line problem
competitive algorithm
competitive ratio
constrained graph
