Searching with Imperfect Information

Heukers, F. (2017) Searching with Imperfect Information.

[img]
Preview
PDF
144kB
Abstract:When a non-optimal seeker is introduced into the cow path problem, the competitive ratio of the optimal deterministic algorithm increases. In this paper, we discuss the impact of the non-optimal seeker on the cow path problem using this optimal deterministic algorithm. Also, a method is proposed to improve this algorithm for the non-optimal seeker. The distance factor in the algorithm is made dependent on the probability of the seeker finding the object when he is upon it. Some examples are given were the competitive ratio of this adjusted algorithm is determined for the expected case and for 95% of the cases. Also, the impact of a non-optimal seeker on an extend version of the cow path problem, known as a star search, is discussed briefly.
Item Type:Essay (Bachelor)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics
Programme:Applied Mathematics BSc (56965)
Link to this item:http://purl.utwente.nl/essays/72868
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page