![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Исследование лабиринта
Процесс поиска на графах становится поучительным, если представлять его в терминах эквивалентной задачи, которая имеет долгую и интересную историю (см. раздел ссылок), - задачи поиска выхода из лабиринта, который состоит из перекрестков, соединенных коридорами. В этом разделе представлен подробный анализ базового метода исследования каждого коридора в заданном лабиринте. Для некоторых лабиринтов конкретная задача может быть решена с применением простого правила, однако для большей части лабиринтов требуется более сложная стратегия (см. рис. 18.1). Использование терминов лабиринт (maze) вместо граф, коридор (passage) вместо ребро и перекресток (intersection) вместо вершина есть ни что иное, как просто семантическое различие, однако на данной стадии переход на другую терминологию поможет глубже прочувствовать задачу. Один из приемов, применявшийся для исследования лабиринта без риска заблудиться и известный еще с античных времен (берет начало, по меньшей мере, от легенд о Тесее и Минотавре), заключается в том, чтобы разматывать клубок по мере продвижения вглубь лабиринта. Нить гарантирует, что мы всегда сможем выбраться из лабиринта, однако мы заинтересованы в том, чтобы исследовать каждую часть лабиринта и не хотим проходить по уже пройденному пути, пока в этом не появится необходимость. Для достижения этих целей нам нужно некоторое средство, чтобы помечать те места, в которых мы уже были. Разумеется, можно с этой целью использовать и нить, однако мы воспользуемся другим методом, который с большой точностью соответствует компьютерной реализации. Глава 18. Поиск на графе
(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, но мы осветили его, открыв двери с обоих концов.
|