Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 18. Поиск но графе
РИСУНОК 18.3. ПРИМЕР ИССЛЕДОВАНИЯ ТРЕМО КОНКРЕТНОГО ЛАБИРИНТА (ПРОДОЛЖЕНИЕ) Далее мы продвигаемся к перекрестку 7 (слева вверху), открываем дверь и видим, что перекресток 0 освещен (слева, вторая диаграмма сверху), а затем проходим к перекрестку 1 (слева, третья диаграмма сверху). В этой точке, когда большая часть лабиринта уже пройдена, мы используем нить, чтобы вернуться в начало пути, двигаясь от 1 до 7, далее до 4, до 6, до 2 и до 0. Вернувшись на перекресток О, мы завершаем наше исследование, проверяя коридоры, ведущие к перекрестку 5 (справа, вторая диаграмма снизу) и к перекрестку 7 (внизу справа), после чего все коридоры и перекрестки становятся освещенными. И снова оба коридора, соединяющие перекрестки 0 с 5 и 0 с 7, освещены, поскольку мы открыли двери с обоих концов, однако мы через них не проходим. Часть 5. Алгоритмы на графах Доказательство: Чтобы доказать это утверждение методом индукции, мы сначала отметим, что оно выполняется в тривиальном случае, т.е. для лабиринта, который содержит один перекресток и ни одного коридора - мы просто включаем свет. Для любого лабиринта, который содержит более одного перекрестка, мы полагаем, что это свойство справедливо для всех лабиринтов с меньшим числом перекрестков. Достаточно показать, что мы посетили все перекрестки, поскольку мы открываем все двери на каждом посещенном перекрестке. Теперь рассмотрим первый коридор, который мы выбираем на первом перекрестке, и разделим все перекрестки на два подмножества: (i) те, которые мы можем достичь, выбрав этот коридор и не возвращаясь в отправную точку, и (ii) те, которые мы не можем достичь, не вернувшись в отправную точку. По индуктивному предположению мы знаем, что посетили все перекрестки в (i) (игнорируя все коридоры, возвращающие на начальный перекресток, который освещен) и вернулись на начальный перекресток. Следовательно, применяя индуктивное предположение еще раз, мы знаем, что посетили все перекрестки (игнорируя коридоры, ведущие из отправной точки на перекрестки в (ii), которые освещены). ■ Из подробного примера, представленного на рис. 18.2 и 18.3, мы видим, что существуют четыре различных ситуаций, которые возникают при выборе очередного коридора и которые мы должны учитывать, принимая одно из возможных решений: (i) Коридор не освещен, следовательно, мы его выбираем. (ii) Коридор уже был использован (в нем мы размотали нить), следовательно, мы выбираем его (и сматываем нить в клубок). (iii) Дверь на другом конце коридора закрыта (но сам перекресток освещен), в силу этого обстоятельства мы пропускаем этот коридор. (iv) Дверь на другом конце коридора открыта (а перекресток освещен), в силу этого обстоятельства мы пропускаем этот коридор. Первая и вторая ситуации относятся к любому коридору, который мы обходим, сначала с одного его конца, а затем с другого. Третья и четвертая ситуация относятся к любому коридору, который мы пропускаем, сначала с одного его конца, а затем с другого. Далее мы увидим, как этот план исследования лабиринта преобразуется непосредственно в поиск на графе. РИСУНОК 18.4. РАЗЛОЖЕНИЕ ЛАБИРИНТА НА ЧАСТИ Для доказательства методом индукции, что исследование Тремо приводит в любую точку лабиринта (верхний рисунок), мы разбиваем его на две части меньших размеров посредством удаления всех ребер, соединяющих первый перекресток с любым другим перекрестком, который можно достичь из первого коридора без необходимости возврата через первый перекресток (рисунок внизу). Глава 18. Поиск на графе Упражнения > 18.1. Предположим, что из лабиринта, показанного на рис. 18.2 и 18.3, удалены перекрестки 6 и 7 (а также все ведущие к ним коридоры), зато добавлен коридор, который соединяет перекрестки 1 и 2. В стиле рис. 18.2 и 18.3 покажите, как протекает исследование Тремо полученного лабиринта. о 18.2. Какая из представленных ниже последовательностей не может служить последовательностью включения освещения коридоров в процессе проведения исследования Тремо на лабиринте, представленном на рис. 18.2 и 18.3? 0-7-4-5-3-1-6-2 0-2-6-4-3-7-1-5 0-5-3-4-7-1-6-2 0-7-4-6-2-1-3-5 • 18.3. Сколько существует путей обхода лабиринта, показанного на рис. 18.2 и 18.3, при проведении исследования Тремо?
|