限制图上的局内出租车调度与竞争算法

Scheduling for on-line taxi problem and competitive algorithm on constrained graphs

经典的优化理论大多是在已知条件不变的基础上给出最优方案（即最优解），其最优性在条件发生变化时就会失去．局内问题与竞争算法则是针对特定的优化问题来研究这样的方法，它在变化因素的每一个特例中都能给出一个方案，使得这一方案所得到的解离最优方案给出的解总在一定的比例之内．本文应用复位策略给出限制图上局内ｋ 出租车调度问题竞争比为１＋ （ｎ－ ｋ）λ的竞争算法．

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. A competitive algorithm is given for on line scheduling of k taxi problem on constrained graphs using the position maintaining occupied strategy, which has 1+( n-k) λ competitive ratio.