M On The Ray Path Of A Moving Target Search Algorithm

On-line searching problem is central to computer science,especially in the robotics.The optimal on-line algorithms of the linear search, m-rays target search problems have been proposed until now,and M.Y.Kao presented the best randomized algorithm to these problems.Three problems are deeply discussed in this thesis:linear search problem,m-ray search problem,m-rays parallel search problem.These problems are also called cow-path problems,and the three problems are more and more generalized,this thesis reviews the results achieved until now to the three problems:the best deterministic on-line algorithm and randomized algorithm when searching for the static target,moreover,this thesis studies the variation of these problems.The best on-line algorithms for problem 1 and problem 2 while the target moves at fixed velocity or changing velocity are presented,also including the competitive ratio of them.The author attempts to solve the problem that parallel searching for the moving target on m-rays and give some results.