Введение
1. Исторический обзор
С задачей нахождения выхода из лабиринта люди сталкивались уже на ранних этапах развития цивилизации. Свидетельством этого может служить древнегреческий миф о том, как Тезей, убив Минотавра, сумел найти выход из лабиринта.
Математической моделью лабиринта является граф, ребра которого соответствуют коридорам, а вершины-- перекресткам лабиринта. Таким образом, в терминах графов задача о лабиринте заключается в построении метода, позволяющего найти маршрут в графе, который начинается в заданной вершине г»о (вход) и наверняка приводит в другую заданную вершину у\ (выход). В такой постановке задача о лабиринте близка к задачам обхода графов, то есть к задачам, в которых требуется построить замкнутый маршрут, содержащий все вершины или все ребра графа. Действительно, следуя такому маршруту, мы обойдем все вершины графа, а. значит, обязательно достигнем выхода.
Опубликованная в 1736 году статья Л. Эйлера о кенигсбергских мостах, в которой им был сформулирован и доказан критерий существования в графе замкнутого маршрута, содержащего все ребра ровно по одному разу, положила начало теории графов как математической дисциплине и, в частности, явилась первой работой по проблеме обхода графов. Разнообразные задачи, связанные с обходами графов, актуальны и по сей день. Так, например, остается открытой проблема о существовании полиномиального алгоритма для задачи коммивояжера и задачи о существовании гамильтонова цикла.
2
Первый систематический процесс (алгоритм) для решения собственно задачи о лабиринте, по-видимому, был предложен Винером (C. Wiener) в 1833 году. Другие, более экономичные, способы решения этой же задачи были предложены Тэрри (G. Tarry) и Тремо (Tremaux). Алгоритмы, предложенные этими авторами, по своей сути были схожими с широко известным ныне алгоритмом поиска в глубину в графе.
Первым, кто начал изучать возможности автоматов по обходу лабиринтов, был К. Шеннон. В его работе 1951 года [20] рассматривалась задача поиска автоматом-мышью определенной цели в лабиринте. Модель Шеннона была формализована К. Деппом. В работе [7, 8] в качестве лабиринтов им рассматривались связные конфигурации клеток на плоскости или кубиков в пространстве (так называемые шахматные лабиринты), а в качестве автомата - конечный автомат, который, обозревая некоторую окрестность клетки, в которой находится, может затем перемещаться в соседнюю клетку в одном из координатных направлений. В этой работе было доказано существование для любого конечного автомата трехмерного шахматного лабиринта-ловушки и высказано предположение о существовании такой ловушки на плоскости.
Плоская ловушка для произвольного конечного автомата была построена X. Мюллером [18], но эта ловушка имела вид 3-графа (графа, у которого степени вершин не превышают 3). JI. Будах [5] доказал, что не существует конечного автомата, который обходил бы все плоские шахматные лабиринты. Этот результат был несколько усилен X. Мюллером [19], который заметил, что в качестве ловушки для доказательства теоремы Будаха может быть выбран не более чем 3-связный лабиринт. Оценка сложности такой ловушки была получена X. Антельманом [2], который показал, что количество клеток в ней имеет порядок 2°^minm)} где т _ количество состояний автомата. A.C. Подколзин [30, 31 существенно упростил доказательство Будаха, а Г. Килибарда [26] привел другое доказательство, логически более простое, однако приводящее к более сложной ловушке.
Если же дополнительно потребовать, чтобы автоматы фиксировали факт обхода, то ловушка может быть найдена в значительно более узких клас-
3
сах лабиринтов. Так, например, М. Булл и А. Хеммерлинг [6] доказали, что не существует автомата, который обходит и останавливается после обхода каждого лабиринта из класса всех конечных плоских мозаичных лабиринтов, являющихся деревьями, или из класса всех односвязных конечных плоских шахматных лабиринтов.
Поиски положительного решения задачи обхода велись в двух направлениях. Первое направление связано с рассмотрением классов лабиринтов, для которых можно построить автомат, обходящий любой лабиринт из данного класса. Отметим несколько интересных результатов, полученных в этом направлении.
К. Депп [7, 8] построил автомат, который обходит произвольный конечный плоский односвязный шахматный лабиринт, а Г. Килибарда [25] установил, что минимальное число состояний для такого автомата равно четырем. В той же работе Г. Килибарда описывает еще два класса лабиринтов, для которых удается не только построить универсальные обходящие автоматы, но и получить точные нижние оценки для числа состояний таких автоматов.
В ряде работ были рассмотрены классы лабиринтов с ограничениями на размеры и расположение дыр. А.Н. Зыричез [24] доказал, что класс конечных шахматных лабиринтов, диаметры дыр которых не превосходят заданной константы в,, обходится некоторым автоматом, имеющим не более, чем С(Р состояний. Г. Килибарда [27] понизил эту оценку до Сс1, указав при этом, что этот результат останется верным, если вместо шахматных рассматривать мозаичные лабиринты. А.А. Золотых показал, что можно ослабить ограничения, наложенные на размеры дыр. Более точно, в работе [23] он рассматривал класс лабиринтов, внутренние дыры которых ограничены в некотором рациональном направлении константой с1 (длина проекции любой дыры на некоторую прямую с рациональным угловым коэффициентом не превосходит в), и доказал, что для этого класса существует универсальный автомат, число состояний которого линейно зависит от с1. Кроме того, в той же работе рассматривался случай, когда каждая внутренняя дыра ограничена числом (1 хотя бы в одном из некоторого конечного множества
4
рациональных направлений, и для этого случая, при наложении некоторого ограничения на взаимное расположение дыр, построен универсальный обходящий автомат, имеющий не более, чем С(12 состояний.
Второе направление в поисках положительных решений задачи обхода связано с усилением возможностей автоматов. Одно из возможных усилений - рассмотрение систем автоматов. Рассматривались системы двух типов. Первый тин - это так называемые независимые системы автоматов. Поведение в лабиринте каждого автомата из такой системы не зависит ни от положения, ни от состояний других автоматов из этой системы. Поэтому возможности таких систем почти не отличаются от возможностей одного автомата. X. Антельман, Л. Будах и Х.-Л. Роллик [1] индукцией по числу автоматов установили существование плоской ловушки для любой конечной независимой системы автоматов, а также построили бесконечную плоскую ловушку сразу для всех автоматов. Другое, не индуктивное, доказательство этого факта получено Ф. Хоффманом [15].
В отличии от независимых систем, системы взаимодействующих автоматов, называемые также коллективами, уже могут решать задачу обхода как для класса конечных, так и класса бесконечных плоских прямоугольных лабиринтов. Автомат из такого коллектива в каждой вершине лабиринта получает информацию не только о возможных направлениях дальнейшего передвижения, но и о состояниях других автоматов, находящихся в той же вершине. При рассмотрении коллективов особо выделяют простейших членов коллектива - автоматы-камни. Камни это автоматы без памяти, перемещение которых определяется другими автоматами коллектива. Коллектив, состоящий из п автоматов и т камней называется коллективом типа (п,т).
М. Блюм и Д. Козен [3] доказали, что существуют коллектив тина (1,2) и коллектив типа (2,0), которые обходят произвольный конечный плоский мозаичный лабиринт и останавливаются после обхода. А. Хеммерлинг [11] обобщил этот результат на случай плоских прямоугольных лабиринтов. Ф. Хоффман [15, 16] показал, что коллектив из одного автомата и одного камня не может обойти все плоские мозаичные лабиринты. Однако, класс
5
плоских прямоугольных лабиринтов допускает естественное расслоение такое, что для каждого слоя найдется коллектив типа (1,1), который обходит любой лабиринт из этого слоя. В качестве параметра расслоения берется число дыр лабиринта. В работах К. Кригела и А. Хеммерлинга [10, 12, 17] было доказано, что для любого к € N существует коллектив типа (1,1), обходящий все плоские мозаичные лабиринты, у которых не более к дыр, причем в работах [10, 12] этот результат обобщается на случай ^-связных графов, степени вершин которых не превосходят некоторого числа 6, но вместо автомата с камнем рассматривается автомат с указателем (указатель отмечает не только вершину, в которой находится, но и одно из входящих в эту вершину ребер).
Задача о нахождении обходящих коллективов, минимальных по числу автоматов и камней, исследовалась и для класса всех конечных и бесконечных плоских мозаичных лабиринтов. М. Блюм и У. Сакода [4] дали эскиз доказательства того, что существует коллектив типа (1,7), обходящий любой лабиринт из этого класса. 3. Хабасинский и М. Карпинский [9] уточнили это доказательство, а А. Шепитовский [21] построил коллектив типа (1,5), решающий ту же задачу. В конструкции А. Шепитовского два камня могут быть заменены одним автоматом. Таким образом, А. Шепитовский. по сути, доказал, что существует коллектив типа (2,3) (а, значит, и коллективы типов (3, 2), (4,1) и (5,0)), обходящий произвольный конечный или бесконечный плоский мозаичный лабиринт. Минимальность этих коллективов была установлена Г. Килибардой [28], который доказал, что для любого коллектива, имеющего один из типов (4,0), (3,1), (2,2) или (1,3), существует бесконечная плоская мозаичная ловушка. Открытой проблемой остался лишь случай коллектива, состоящего из одного автомата и четырех камней.
При рассмотрении лабиринтов более общего вида становится возможным построение ловушек для коллективов автоматов. В работе М. Блюма и У. Сакоды [4] было сформулировано утверждение о существовании конечной трехмерной мозаичной ловушки для любого коллектива автоматов и, для случая, когда все автоматы стартуют из одной вершины, оно было час-
б
- Київ+380960830922