关键词: 目标可移动的直线搜索问题 迷失的奶牛问题 在线算法 竞争比 Minimax定理

Abstract:

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 compet  itive ratio are introduced in this paper for this generalized problem. The minimax theorem plays a key role in this solution.

Key words: moving target linear search problem, lost-cow problem, on-line algorithm, competit ive ratio, minimax theorem