О сложности автоматного обхода лабиринтов

В работе [8] рассматривается класс всех конечных лабиринтов с конечными дырами диаметра не больше данного натурального числа $n$. Показано, что для этого класса существует универсальный обходчик, у которого не больше $Cn^2$ состояний. В настоящей статье дается более эффективный алгоритм обхода, чем в [8]. Строится универсальный обходчик для этого класса, у которого $Cn$ состояний.