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

摘要：

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

关键词： 目标可移动 直线搜索 奶牛问题 在线算法 线性螺旋搜索

作者: 王明岳

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

会议类型: 国内会议

会议名称: 2008年全国理论计算机科学学术年会

会议地点: 西安

会议语种:中文

页码: 60-62,104

在线出版日期: 2008-09-19（万方平台首次上网日期，不代表论文的发表时间）