University of Twente Student Theses


Searching with Imperfect Information

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

This is the latest version of this item.

[img] PDF
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:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page