Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-28T17:19:52.041Z Has data issue: false hasContentIssue false
  • English
  • Français

Search in a Maze

Published online by Cambridge University Press:  27 July 2009

S. Gal  and
E. J. Anderson
S. Gal
Affiliation:
IBM Israel Scientific Center Technion City, Haifa, Israel 32000
E. J. Anderson
Affiliation:
Institute of Management Studies University of Cambridge, Cambridge, England CB2 1RX
Get access Rights & Permissions [Opens in a new window]

Abstract

Suppose that you find yourself trapped in a maze about which you know nothing except that it has an exit point. We present an optimal strategy that will lead you to the exit point in minimum expected time. This strategy ensures that the expected total length of the arcs you traverse will not exceed the sum of the lengths of the arcs in the maze.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 4 , Issue 3 , July 1990 , pp. 311 - 318
Copyright
Copyright © Cambridge University Press 1990

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Anderson, E.J. (1981). Mazes: search games on unknown networks. Networks 11: 393–397.CrossRefGoogle Scholar
Even, S. (1979). Graph algorithms. Rockville, MD: Computer Science Press.Google Scholar
Fraenkel, A.S. (1970). Economic traversal of labyrinths. Mathematics Magazine 43: 125–130.CrossRefGoogle Scholar
Fraenkel, A.S. (1971). Economic traversal of labyrinths (correction). Mathematics Magazine 44: 12.CrossRefGoogle Scholar
Gal, S. (1980). Search games. New York: Academic Press.Google Scholar
Gal, S. (1989). Continuous search games. In Chudnovsky, D.V. & Chudnousky, G.V. (eds.), Search theory: Some recent developments. New York: Marcel Dekker, pp. 33–53.Google Scholar
Golumbic, M.C. (1987). A general mehod for avoiding cycling in a network. Information Processing Letters 24: 251–253.CrossRefGoogle Scholar
Lucas, E. (1882). Recreations mathematiques: Paris.Google Scholar
Tarry, G. (1895). Le problem des labyrinths. Nouvelles Annales de Mathématiques 14: 187.Google Scholar