Mazes: Search games on unknown networks

✍ Scribed by E. J. Anderson

• Publisher: John Wiley and Sons
• Year: 1981
• Tongue: English
• Weight: 250 KB
• Volume: 11
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230110409

✦ Synopsis

Abstract

This paper discusses a class of search problems on networks, where the searcher only has information about that part of the network which he has traversed. These problems correspond to that of finding the exit of a maze. In this context it is natural to consider the two person game between the solver and the setter, where the setter may choose the maze subject to a constraint on the total length of its arcs. A particular strategy for the solver is investigated and shown to be optimal for this game.