m射线路径上移动目标搜索的在线算法研究

摘要

在线搜索目标问题在计算机科学,尤其是机器人学里面处于核心地位。目前已知直线上、m射线路径上搜索固定目标的最佳在线策略,M.Y.Kao提出了这个问题的最佳在线随机算法。
　　 本文深入研究了三个问题:直线上搜索目标,m射线路径上搜索目标,m射线路径上并行搜索目标。这些问题也被称为奶牛路径问题(cow-pathproblem),以上三个问题越来越一般化,除了回顾在这三个问题中已有的研究成果——搜索固定目标的最佳确定性在线算法、随机算法以外,本文进一步扩展了这些问题。本文对于前两个问题中,目标匀速移动、目标变速移动的情况,给出了最佳在线算法及其竞争比,对于第三个问题,尝试性地给出了一些分析结果。