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