Исследование лабиринта

Процесс поиска на графах становится поучительным, если представлять его в терми­нах эквивалентной задачи, которая имеет долгую и интересную историю (см. раздел ссы­лок), - задачи поиска выхода из лабиринта, который состоит из перекрестков, соединен­ных коридорами. В этом разделе представлен подробный анализ базового метода исследования каждого коридора в заданном лабиринте. Для некоторых лабиринтов кон­кретная задача может быть решена с применением простого правила, однако для боль­шей части лабиринтов требуется более сложная стратегия (см. рис. 18.1). Использование терминов лабиринт (maze) вместо граф, коридор (passage) вместо ребро и перекресток (intersection) вместо вершина есть ни что иное, как просто семантическое различие, одна­ко на данной стадии переход на другую терминологию поможет глубже прочувствовать задачу.

Один из приемов, применявшийся для исследования лабиринта без риска заблудиться и известный еще с античных времен (берет начало, по меньшей мере, от легенд о Тесее и Минотавре), заключается в том, чтобы разматывать клубок по мере продвижения вглубь лабиринта. Нить гарантирует, что мы всегда сможем выбраться из лабиринта, однако мы заинтересованы в том, чтобы исследовать каждую часть лабиринта и не хотим проходить по уже пройденному пути, пока в этом не появится необходимость. Для достижения этих целей нам нужно некоторое средство, чтобы помечать те места, в которых мы уже были. Разумеется, можно с этой целью использовать и нить, однако мы воспользуемся другим методом, который с большой точностью соответствует компьютерной реализации.

Глава 18. Поиск на графе

Мы полагаем, что на каждом перекрестке установле­ны лампы, которые в исходном состоянии выключены, и двери в обоих концах каждого коридора, которые в исходном состоянии закрыты. Далее мы полагаем, что в двери встроены окна, а источники света достаточно мощные и коридоры достаточно прямые, так что мы, от­крыв дверь, можем определить, освещен или нет пере­кресток на другом конце коридора (если даже дверь на другом конце коридора закрыта). Наша цель заключает­ся в том, чтобы зажечь все лампы и открыть все двери. Для достижения этой цели мы должны иметь в своем распоряжении набор правил, которым будем системати­чески следовать. Следующая стратегия исследования ла­биринта, которую мы будем называть исследованием Тре­мо (Tremaux exploration), известна, по меньшей мере, с девятнадцатого столетия {см. раздел ссылок):

(i) Если на текущем перекрестке нет закрытых две­рей, переходите к шагу (Hi). В противном случае от­кройте любую дверь любого коридора, ведущую из текущего перекрестка (и оставьте ее открытой).

(ii) Если вы видите, что лампа, установленная на пе­рекрестке на другом конце этого коридора уже включена, попробуйте открыть другую дверь на теку­щем перекрестке (шаг (i)). Иначе (если вы видите, что перекресток на другом конце соответствующего коридора не освещен), проследуйте по коридору к этому перекрестку, разматывая при этом нить, вклю­чите свет и переходите к шагу (i).

(iii) Если все двери на текущем перекрестке откры­ты, проверьте, не находитесь ли вы в отправной точ­ке. Если да, то процесс окончен. Если нет, восполь­зуйтесь нитью, чтобы двигаться назад вдоль коридора, который привел вас в этот перекресток в первый раз, разматывая нить по мере продвижения, и ищите дру­гую замкнутую дверь уже там (т.е. вернитесь к шагу (/).

РИСУНОК 18.1. ИССЛЕДОВАНИЕ ЛАБИРИНТА

Мы можем исследовать простой лабиринт, пройдя по каждому коридору и руководствуясь простым правилом типа " держи­тесь правой рукой за стену". Следуя этому правилу, в лабирин­те, изображенном в верхней части рисунка, мы исследуем весь лабиринт, проходя по каждому коридору один раз в каждом направлении. Но если мы будем соблюдать это правило при обходе лабиринта, содержащего цикл, мы вернемся в начальную точку, так и не обследовав весь граф, в чем нетрудно убедиться на примере лабиринта в нижней части рисунка.

На рисунках 18.2 и 18.3 представлен пример обхода графа и показано, что в рассмат­риваемом случае все лампы зажжены и все двери открыты. Эти рисунки отображают один из множества возможных успешных исходов исследования, поскольку нам предоставле­на возможность открывать любую дверь в любом порядке на каждом перекрестке. Что­бы убедиться в том, что этот метод всегда остается эффективным, воспользуйтесь мето­дом математической индукции; для вас это будет очень полезным упражнением.

Свойство 18.1. Когда мы проводим исследование Тремо некоторого лабиринта, мы зажи­гаем все лампы и открываем все двери в лабиринте и завершаем обход там, где его начи­нали.

Часть 5. Алгоритмы на графах

РИСУНОК 18.2. ПРИМЕР ИССЛЕДОВАНИЯ ТРЕМО КОНКРЕТНОГО ЛАБИРИНТА

На этой диаграмме места, которые мы еще не посетили, заштрихованы (темные), а те места, в которых мы уже были, не заштрихованы (светлые). Мы полагаем, что на перекрестках горит свет, и что когда мы открываем двери с обоих концов светлого коридо­ра, этот коридор освещен. Исследова­ние лабиринта мы начинаем с перекрестка 0 и выбираем коридор к перекрестку 2 (вверху слева). Далее мы продвигаемся по маршруту 6, 4, 3 и 5, открывая двери в коридоры и зажигая свет на перекрестках по мере продвижения и разматывая нить (слева). Открывая дверь, которая ведет из 5 в 0, мы замечаем, что перекресток 0 освещен, поэтому мы игнорируем этот коридор (вверху справа). Аналогично, мы пропускаем коридор от 5 к 4(справа, вторая диаграмма сверху), а здесь нам не остается ничего другого как вернуться из 5 в 3 и далее в 4, наматывая нить на клубок. Когда мы откроем дверь коридора, ведущего из 4 в 5, мы видим через открытую дверь на другом конце коридора, что перекресток 5 освещен, и в силу этого обстоятельства пропускаем этот коридор (справа внизу). Мы ни разу не прошли по коридору, соединяющему перекрестки 4 и 5, но мы осветили его, открыв двери с обоих концов.