目标可移动的直线搜索问题的在线算法研究

An On-line Algorithm Analysis of the Moving Target Linear Search Problem

直线搜索问题也被叫做迷失的奶牛问题,解决这个问题的算法叫做线性螺旋搜索。该算法被证明是解决这个问题的最佳在线算法,它的竞争比是9。如果这个问题中的目标可以移动,那么这个问题就被强化了。本文将提出被强化后的问题的最佳在线算法及其竞争比。Minimax定理在这个算法中扮演着重要角色。

The linear search problem （LSP） is also called the lost-cow problem, which can be solved by linear spiral search. Linear spiral search is proved to be the optimal on-line algorithm and has the competitive ratio 9. This problem is generalized when the target moves. The optimal strategy and its competitive ratio are introduced in this paper for this generalized problem. The minimax theorem plays a key role in this solution.