41. Поиск на графах. Исследование лабиринта

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

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

Наша цель заключается в том, чтобы зажечь все лампы и открыть все двери.

Для достижения этой цели мы должны иметь в своем распоряжении набор правил, которым будем систематически следовать. Следующая стратегия исследования лабиринта, которую мы будем называть исследованием Тремо, известна, по меньшей мере, с девятнадцатого столетия:

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

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

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

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

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

Следовательно, применяя индуктивное предположение еще раз, мы знаем, что посетили все перекрестки (игнорируя коридоры, ведущие из отправной точки на перекрестки в (ii), которые освещены). ▪

Существуют четыре различные ситуации, которые возникают при выборе очередного коридора и которые мы должны учитывать, принимая одно из возможных решений:

(i) Коридор не освещен, следовательно, мы его выбираем.

(ii) Коридор уже был использован (в нем мы размотали нить), следовательно, мы выбираем его (и сматываем нить в клубок).

(iii) Дверь на другом конце коридора закрыта (но сам перекресток освещен), в силу этого обстоятельства мы пропускаем этот коридор.

(iv) Дверь на другом конце коридора открыта (а перекресток освещен), в силу этого обстоятельства мы пропускаем этот коридор.

Первая и вторая ситуации относятся к любому коридору, который мы обходим, сначала с одного его конца, а затем с другого. Третья и четвертая ситуация относятся к любому коридору, который мы пропускаем, сначала с одного его конца, а затем с другого. Далее мы увидим, как этот план исследования лабиринта преобразуется непосредственно в поиск на графе.

< Предыдущая		Следующая >