Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

3.4. Лингвистические и поисковые графы

Задача о ханойской башне

Граф аккумулирует в пространственной форме многосложный процесс поиска решений самых разнообразных задач. Поэтому часто узлы и связи между ними снабжены какими-либо характеристиками, так что граф выступает в качестве иллюстрации пошаговой процедуры, имеющей самую непредсказуемую природу. Что мешает использовать графы, т.е. некие совокупности точек и линий, в лингвистике для генерации слов и предложений? Как было показано в предыдущем подразделе, лингвистическая природа естественно высказанных слов и предложений такова, что вычерчивание схем, наподобие тех, что изображены на рис. 3.59 и 3.60, имеет весьма низкую эвристическую ценность. Следовательно, не точки и линии сами по себе определяют граф, а внутренняя природа объекта, к которому пытаются применить теорию графов. Закрепим эту важную мысль задачей о ханойской башне.

Имеется башня из n дисков различного диаметра, нанизанных на один из трех стержней. Требуется построить аналогичную башню на другом стержне с использованием третьего, причем так, чтобы не нарушить два условия: во-первых, перемещать можно только один диск; во-вторых, ни один из дисков большего диаметра не может быть размещен на диске меньшего диаметра. На рис. 3.63 изображены восемь состояний для трех дисков — a, b, c. Каждому из восьми состояний отвечает кодовое слово, составленное из трех больших букв. Например, первый переход малого диска c со стержня А на стержень C можно обозначить как AAA → AAC.

Рис. 3.63

Эта цепочка отвечает правильной реализации решения в огромном пространстве разрешенных и неразрешенных состояний. Но если задача будет решена для трех дисков, алгоритм ее решения несложно будет распространить на любое конечное число дисков. Оптимальное решение задачи с n дисками требует N = 2^{n – 1} перемещений. Задача о трех дисках должна иметь семь перемещений, задача о перемещении двух дисков — три перемещения. Таким образом, задача о перемещении трех дисков разбивается на две задачи о перемещении двух дисков или на семь задач о перемещении одного диска. Подобное разбиение сложной задачи на совокупность простых используется всякий раз, когда составляется оптимальный алгоритм поиска решений. На рис. 3.64 приведено дерево поиска нужного решения для двух дисков с указанием всех разрешенных состояний, ребра — переходы дисков с одного стержня на другой. Путь к верному решению пронумерован и обозначен полужирными стрелками.

Рис. 3.64

Теперь построим дерево для перемещения трех дисков, но в качестве вершин графа возьмем не сами состояния дисков, которые изображены на рис. 3.63, а коды переходов того или иного диска с одного стержня на другой в соответствии с введенными обозначениями. Дерево переходов, показанное на рис. 3.65, вполне наглядно демонстрирует поиск нужного решения и адекватно заменяет дерево состояний, которое для трех дисков будет иметь восемь уровней.

Рис. 3.65

Первоначально задача поиска в пространстве состояний представлена совокупностью трех составляющих: множеством начальных состояний, множеством конечных состояний и множеством переходов. В процессе реализации сплошного поиска происходит выявление промежуточных состояний. Однако процедура сплошного перебора всех возможных переходов очень нерациональна, выделить же один обязательный переход вполне возможно. Так, перенос диска c со стержня A на стержень C является обязательной процедурой. Отсюда возникает редукционный алгоритм, который предусматривает разбиение исходной задачи на две менее сложные задачи. При этом начальный, конечный и промежуточный стержни постоянно меняются.

Действительно, для того чтобы диск c перенести с А на С (В — серединный), нужно сначала перенести диски a и b на стержень В (С — серединный). Когда диски a и b переносятся на стержень С, стержень А берет на себя функции серединного. За семь шагов серединным стержнем становятся поочередно стержни В, С, А, В, С, А, В. Далее две менее сложные задачи снова разбиваются на две еще менее сложные. Эта редукционная процедура продолжается до тех пор, пока не будет достигнуто окончательное решение в форме элементарной задачи по переносу одного-единственного диска согласно условию задачи. Стратегию поиска можно выбрать иную, вместе с ней изменится и граф поиска нужного решения.

Задача о ханойской башне попадает в обширный класс задач аналогичного свойства о перемещении конечного числа объектов с одного места на другое с какими-либо ограничениями. Вот одна из таких задач: паромщику нужно перевести через реку волка, козу и капусту. Паром небольшой, так что на нем могут уместиться сам паромщик и что-то одно — либо волк, либо коза, либо капуста. Имеется и еще одно ограничивающее условие: если на берегу оставить волка наедине с козой, он съест козу, а если оставить козу с капустой, она съест капусту. Вопрос: как перевезти на пароме три названных объекта?