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

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

单位：上海市智能信息处理实验室 上海200433 复旦大学计算机科学与工程系 上海200433