A note on the maximum size of a rectilinear maze
noteonmaximumsiz00shin.pdf (634.6Kb)Abstract
In this paper, we study the problem of searching through an unknown maze by a robot and show that the size of the largest rectilinear maze the robot can explore in at most k steps is bounded by 2k squared + 2k + 1 for mazes with circuits, and is bounded by 4k squared/3 + 8k/3 + 1 for mazes without circuits, Furthermore, we show that the bounds are tight.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.NPS Report Number
NPS-52-89-057Related items
Showing items related by title, author, creator and subject.
-
A Class of Bounded and Partially Bounded Nonlinear Controllers for First and Second Order Dynamical Systems
(IEEE, 2021-06-30);This letter proposes structurally simple, bounded and partially bounded nonlinear controllers that offer satisfactory performance, demonstrated by their application to first and second-order dynamical systems. This is done ... -
Optimizing an unknown function by the method of bounded least squares
(Monterey, California. Naval Postgraduate School, 1965);The problem of estimating the position of an extreme point of an unknown function of several independent variables is examined for the case where the dependent variable is known to be bounded. The classical method of ... -
NETWORK DEVICE SOFTWARE GENERATION
(Monterey, CA; Naval Postgraduate School, 2019-09);Verification of data-plane software is limited to verifying point properties such as bounded packet processing time or not misinterpreting malformed packet headers, which usually are chosen to illustrate the merits of some ...
