14. Задача о Ханойской башне. Нахождение кратчайшего пути в графах с ребрами единичной длины.
Задача о Ханойской башне

Рассмотрим пример представления графом изменения состояний дис-кретной системы [18].
Это так называемая задача о Ханойской башне. Имеется три стержня, на первом из которых нанизано n дисков, диаметр которых убывает снизу вверх. Ставится цель: перекладывая диски по одному, расположить их в таком же порядке на третьем стержне, используя в качестве промежуточного, второй стержень и, соблюдая условия, чтобы ни на каком шаге больший диск не оказался выше меньшего ни на одном из стержней. Оптимизация заключается в достижении цели за наименьшее число шагов.
Легенда гласит, что в одном буддийском монастыре во Вьетнаме на первом стержне нанизано 64 диска. Если переложить все их по указанным правилам на третий стержень, то наступит конец света. Конец света – вопрос философский, но, тем не менее, не будем испытывать судьбу и рассмотрим задачи с меньшим числом дисков.
Рассмотрим n=1 (рис. 24).

Рис. 24. Задача о Ханойской башне для n=1

Задача для n=1 решается за один шаг, но возможен и неоптимальный вариант – два шага, т.е. сначала диск устанавливают на второй стержень, а потом на третий.
Обозначим X, Y и Z множества дисков, надетых соответственно на первый, второй и третий стержни. Состояние такой системы будем описывать набором элементов этих множеств (X,Y,Z).
Тогда возможные состояния такой системы имеют вид:
X Y Z
(1,0,0) – исходное,
(0,0,1) – целевое,
(0,1,0) – промежуточное.
Представим состояния системы в виде графа с использованием коор-динатной плоскости с осями X и Z (рис. 25). Такое представление избавляет нас от необходимости указывать состояние вершин.

Рис. 25. Представление графом задачи о Ханойской башне при n=1

Третья ось на рис. 25 не указана, множество Y всегда можно получить как дополнение множеств X, Z до полного множества дисков.
Тогда путь 11 соответствует оптимальному решению задачи, а путь 101 – неоптимальному.
Рассмотрим случай n=2. Будем описывать элементы множеств в виде столбца цифр, соответствующих убыванию диаметра дисков:
X Y Z
( ,0,0) – исходное состояние,
(2,1,0) – 1-й шаг,
(0,1,2) – 2-й шаг,
(0,0, ) – 3-й шаг, целевое состояние.
Это оптимальное решение задачи – за 3 шага. Возможны также неоп-тимальные последовательности. Изобразим вначале все возможные последовательности в виде графа и обозначим все ребра следующим образом (рис. 26)

Рис. 26. Возможные последовательности решения
задачи о Ханойской башне для n=2
а) для трех множеств X,Y,Z, б) для двух множеств X,Z

Представим теперь случай n=2 на координатной плоскости, используя координаты – множества X,Z (первая и третья координаты). Получим рис. 27, на котором отмечены дуги, соответствующие рис. 26б. Видно, что этот граф как бы содержит в себе три графа для n=1, а оптимальное решение соответствует последовательности дуг а,b,с ( ,0;2,0;0,2;0, ).
Общий способ решения задачи о Ханойской башне может быть полу-чен путем анализа трансформации графа для n дисков при переходе к n+1 диску.
Граф в задаче о Ханойской башне имеет ту особенность, что все ребра имеют одинаковую длину, равную единице, что соответствует одному шагу состояния дискретной системы.

Рис. 27. Представление графом задачи
о Ханойской башне для n=2

Оптимальный переход всегда из нижней левой точки крайнего правого треугольника! Степени всех вершин, кроме крайних равны 3. Есть три пути, как у витязя на распутье. Кратчайший путь для данных графов можно найти полным перебором возможных путей. Рассмотрим систематический метод определения этого пути. Общее правило нахождения кратчайшего пути в графе с ребрами единичной длины состоит в том, чтобы каждой вершине хi приписать индекс li, равный длине кратчайшего пути из данной вершины в конечную:
1) конечной вершине приписывается индекс 0;
2) всем вершинам, из которых идет ребро в конечную вершину, приписывается индекс 1;
3) всем вершинам, ещё не имеющим индексов, из которых идет ребро в вершину с индексом li приписывается индекс li+1.
Так продолжается до тех пор, пока не будет помечена начальная вер-шина. По окончании разметки индекс начальной вершины будет равен длине кратчайшего пути.
Сам кратчайший путь найдем, двигаясь из начальной вершины в на-правлении убывания индексов.
Такой способ определения кратчайшего пути является частным случаем нахождения оптимального решения по методу динамического программирования (Р. Беллмана).
Подобную задачу должен решать интеллектуальный транспортный робот на складе при перекладке, например, ящиков различной величины с одной площадки на другую с использованием одной промежуточной площадки.
Нахождение кратчайшего пути в графе с ребрами неединичной длины.
Если граф имеет ребра неединичной длины, то подобное присвоение индексов должно учитывать их длину, причем индексы эти могут умень-шаться в ходе разметки вершин с учетом индексов всех соседних вершин [18]. Оптимальный путь ищут, двигаясь из начальной вершины в сторону тех вершин, индекс которых равен индексу текущей минус длина ребра. Может быть, таких оптимальных (кратчайших) путей будет и не один, но все они имеют длину, равную индексу начальной вершины после завершения разметки.