О поведении автоматов, оставляющих отметки в вершинах лабиринтов

• Автор: Насыров, Азат Зуфарович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Москва
• Количество страниц: 77 с. : ил

Введение
1. Исторический обзор
С задачей нахождения выхода из лабиринта люди сталкивались уже на ранних этапах развития цивилизации. Свидетельством этого может служить древнегреческий миф о том, как Тезей, убив Минотавра, сумел найти выход из лабиринта.
Математической моделью лабиринта является граф, ребра которого соответствуют коридорам, а вершины-— перекресткам лабиринта. Таким образом, в терминах графов задача о лабиринте заключается в построении метода, позволяющего найти маршрут в графе, который начинается в заданной вершине до (вход) и наверняка приводит в другую заданную вершину (выход). В такой постановке задача о лабиринте близка к задачам обхода графов, то есть к задачам, в которых требуется построить замкнутый маршрут, содержащий все вершины или все ребра графа. Действительно, следуя такому маршруту, мы обойдем все вершины графа, а, значит, обязательно достигнем выхода.
Опубликованная в 1736 году статья Л. Эйлера о кенигсбергских мостах, в которой им был сформулирован и доказан критерий существования в графе замкнутого маршрута, содержащего все ребра ровно по одному разу, положила начало теории графов как математической дисциплине и, в частности, явилась первой работой по проблеме обхода графов. Разнообразные задачи, связанные с обходами графов, актуальны и по сей день. Так, например, остается открытой проблема о существовании полиномиального алгоритма для задачи коммивояжера и задачи о существовании гамильтонова цикла.

Первый систематический процесс (алгоритм) для решения собственно задачи о лабиринте, по-видимому, был предложен Винером (С. Wiener) в 1833 году. Другие, более экономичные, способы решения этой же задачи были предложены Тэрри (G. Tarry) и Тремо (Tremaux). Алгоритмы, предложенные этими авторами, по своей сути были схожими с широко известным ныне алгоритмом поиска в глубину в графе.
Первым, кто начал изучать возможности автоматов по обходу лабиринтов, был К. Шеннон. В его работе 1951 года [20] рассматривалась задача поиска автоматом-мышью определенной цели в лабиринте. Модель Шеннона была формализована К. Деппом. В работе [7, 8] в качестве лабиринтов им рассматривались связные конфигурации клеток на плоскости или кубиков в пространстве (так называемые шахматные лабиринты), а в качестве автомата - конечный автомат, который, обозревая некоторую окрестность клетки, в которой находится, может затем перемещаться в соседнюю клетку в одном из координатных направлений. В этой работе было доказано существование для любого конечного автомата трехмерного шахматного лабиринта-ловушки и высказано предположение о существовании такой ловушки на плоскости.
Плоская ловушка для произвольного конечного автомата была построена X. Мюллером [18], но эта ловушка имела вид 3-графа (графа, у которого степени вершин не превышают 3). JI. Вудах [5] доказал, что не существует конечного автомата, который обходил бы все плоские шахматные лабиринты. Этот результат был несколько усилен X. Мюллером [19], который заметил, что в качестве ловушки для доказательства теоремы Будаха может быть выбран не более чем 3-связный лабиринт. Оценка сложности такой ловушки была получена X. Антельманом [2], который показал, что количество клеток в ней имеет порядок 2°т ln т), где то - количество состояний автомата. A.C. Подколзин [30, 31] существенно упростил доказательство Будаха, а Г. Килибарда [26] привел другое доказательство, логически более простое, однако приводящее к более сложной ловушке.
Если же дополнительно потребовать, чтобы автоматы фиксировали факт обхода, то ловушка может быть найдена в значительно более узких клас-

сах лабиринтов. Так, например, М. Булл и А. Хеммерлинг [6] доказали, что не существует автомата, который обходит и останавливается после обхода каждого лабиринта из класса всех конечных плоских мозаичных лабиринтов, являющихся деревьями, или из класса всех односвязных конечных плоских шахматных лабиринтов.
Поиски положительного решения задачи обхода велись в двух направлениях. Первое направление связано с рассмотрением классов лабиринтов, для которых можно построить автомат, обходящий любой лабиринт из данного класса. Отметим несколько интересных результатов, полученных в этом направлении.
К. Депп [7, 8] построил автомат, который обходит произвольный конечный плоский односвязный шахматный лабиринт, а Г. Килибарда [25] установил, что минимальное число состояний для такого автомата равно четырем. В той же работе Г. Килибарда описывает еще два класса лабиринтов, для которых удается не только построить универсальные обходящие автоматы, но и получить точные нижние оценки для числа состояний таких автоматов.
В ряде работ были рассмотрены классы лабиринтов с ограничениями на размеры и расположение дыр. А.Н. Зыричев [24] доказал, что класс конечных шахматных лабиринтов, диаметры дыр которых не превосходят заданной константы d, обходится некоторым автоматом, имеющим не более, чем Cd2 состояний. Г. Килибарда [27] понизил эту оценку до Cd, указав при этом, что этот результат останется верным, если вместо шахматных рассматривать мозаичные лабиринты. A.A. Золотых показал, что можно ослабить ограничения, наложенные на размеры дыр. Более точно, в работе [23] он рассматривал класс лабиринтов, внутренние дыры которых ограничены в некотором рациональном направлении константой d (длина проекции любой дыры на некоторую прямую с рациональным угловым коэффициентом не превосходит d), и доказал, что для этого класса существует универсальный автомат, число состояний которого линейно зависит от d. Кроме того, в той же работе рассматривался случай, когда каждая внутренняя дыра ограничена числом d хотя бы в одном из некоторого конечного множества

§5. Мозаичная и шахматная ловушки для автомата с /с-следом
В этом параграфе будут построены мозаичная и шахматная бесконечные трехмерные ловушки для автомата с -следом.
Для построения таких ловушек мы покажем, что для любого конечного набора автоматов без печати существует шахматный возвращающий лабиринт, Это факт будет доказан сведением к построению возвращающего лабиринта для некоторого другого набора автоматов без печати. Подобные сведения, в той или иной форме, встречались в [5, 26, 30] и опирались, по существу, на утверждение о том, что для любого конечного прямоугольного лабиринта можно построить шахматный лабиринт такой, что поведение автомата без печати в этом шахматном лабиринте ” моделируется” другим автоматом в исходном прямоугольном лабиринте. Мы воспользуемся этим утверждением в той форме, в которой оно приведено в работе [26] (лемма 3). Прежде, чем сформулировать это утверждение, введем несколько обозначений.
Пусть дано натуральное число 5 > 2 и пусть а — {<Д
где 1 й 4. Обозначим через Ь&(а) лабиринт, получающийся из Ь{а) заменой каждого ребра на цепочку из 8 ребер, идущих в том же направлении, что и исходное ребро. Более точно, лабиринт Ь5(а) имеет множество вершин У3(а) = {уа} и (гф | г 6 1,5, е 1,й} и множество дуг
Г5(а) = {(ь0, у].), (у].,у0), Ц, г1), (у*1, <.) | iel,{8- 1), ] 6 М}, причем дуги имеют следующие отметки:

IК I = IЦ, О! = Ы+.«у I =
где г е 1, (<5 — 1), 1 е 1, й.
Пусть 21 = {А, <5, В, ф) - автомат без печати, допустимый для класса лабиринтов Сч. Определим автомат 21(5) = (А<2, В,1рз,фб) следующим образом. Пусть а — {о?1