Глава 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. Поиск на графе

Упражнения