Полный текст

Введение. Головоломка «Ханойская башня» или «Ханойские башни» [1] известна со второй половины ХIХ века (рис. 1). Рис. 1. Головоломка «Ханойская башня» В практическом плане «диаметры» дисков могут иметь смысл, например, это габариты груза, значения уязвимостей (с точки зрения защиты информации) или время, скажем, с начала эксплуатации. Вообще, ставится задача оптимального и в каком-то смысле безопасного (с точки зрения «законов Брамы»!) «перемещения упорядоченности чего-либо» с одного объекта на другой с дополнительными вспомогательными объектами размещения этой самой упорядоченности. Известна задача ротации носителей информации для создания резервных копий с учётом их ресурсов (время нахождения в эксплуатации, число циклов копирования) [2]. Здесь подразумеваются сеансы вместо перекладываний и уровни резервного копирования вместо дисков [2], на одном уровне хранится только одна резервная копия, а все устаревшие резервные копии должны удаляться. Тем самым обеспечивается эффективное хранение данных: больше резервных копий накапливается к настоящему времени. Так, при трёх носителях 1,2,3 (номера соответствуют условному времени нахождения в эксплуатации, первый - самый «молодой»), порядок их использования, например, для записи видеоинформации такой: 1,2,1,3,1,2,1. Эта последовательность - так называемый палиндром, читается одинаково слева направо и справа налево - есть не что иное, как порядок перекладываний дисков в Ханойской башне с n = 3 (не сказано куда, но указано - кто, какой диск берётся) и расписание «работы»: понедельник - 1, вторник - 2, среда - опять 1 и так далее. Первый диск работает 4 раза, второй - 2, третий - 1(7 шагов). Если будет четыре носителя, получим количество раз: 8,4,2,1 (15 шагов), т.е. при наличии четырех резервных копий можно восстановить данные по состоянию на сегодня, вчера, три дня назад и неделю назад. При пяти носителях: 15,8,4,2,1 (31 шаг), т.е. при пятиуровневой схеме можно восстановить данные, резервные копии которых были созданы две недели назад [2]. Ясно, что это последовательность степеней числа 2. Таким образом, каждый следующий уровень резервного копирования удваивает максимальный период «отката» данных [2]. Автоматизацию такой процедуры обеспечивает пакет программного обеспечения Acronis Backup & Recovery 10 (до 16 уровней резервного копирования!) [3]. 1. Решение задачи на графе. Проанализируем особенности задачи в соответствии с прекрасным материалом в [4, 5]. Рассмотрим n = 1 и назовём стержни X, Y, Z. Изобразим задачу в виде графа (рис. 2). Перекладывание в формате «откуда ® куда» выглядит так: (Х ® Z). Здесь движение идёт как бы направо из исходного состояния. В графе для n = 2 надо двигаться всегда налево (рис. 3). Рис. 2. Граф задачи о Ханойской башне для n = 1 Рис. 3. Граф задачи о Ханойской башне для n = 2 Здесь получаем: (Х ® Y),(Х ® Z),(Y ® Z). В случае n = 3 имеем (Х ® Z),(Х ® Y),(Z ® Y), (Х ® Z),(Y ® Х), (Y ® Z),(Х ® Z), в этом случае надо двигаться всегда направо (рис. 4). Рис. 4. Граф задачи о Ханойской башне для n = 3 Анализ задачи при n = 4 ((Х ® Y),(Х ® Z),(Y ® Z),(Х ® Y), (Z ®Х),(Z ® Y),(Х ® Y),(Х ® Y),(Y ® Z),(Y ® Х),(Z ® Х),(Y ® Z), (Х ® Y),(Х ®Z),(Y ®Z)) показывает, что в соответствующем графе надо двигаться всегда налево [6-11]. Следовательно, напрашивается предположение, что при нечётном n - направо, при чётном - налево! Да, но где право, где лево, если не строить граф, а решать задачу пошагово?! 3. Анализ движения дисков в треугольнике из стержней. Вернёмся к задаче для n = 3. Будем обозначать диски номерами так, что номер - это как бы «диаметр» диска. Чем больше номер, больше диаметр. Изобразим стержни X, Y, Z не на одной линии, а в виде треугольника. Первый шаг. Первый диск переносится против часовой стрелки (рис. 5). а б Рис. 5. Задача о Ханойской башне для n = 3, а - перенос первого диска - на стержнях; б - перенос первого диска - против часовой стрелки в графе - треугольнике с помеченными вершинами Второй шаг. Второй диск переносится по часовой стрелке (рис. 6). а б Рис. 6. Задача о Ханойской башне для n = 3: а - перенос второго диска - на стержнях; б - перенос второго диска - по часовой стрелке в графе - треугольнике с помеченными вершинами Аналогично рассматриваем остальные шаги. Оказывается, первый диск при нечётном общем числе дисков движется против часовой стрелки, а при чётном общем числе дисков - по часовой стрелке (рис. 3-5) [12-14]. Построим таблицу местоположения дисков (рис. 7). Рис. 7. Таблица местоположения дисков Ещё раз проанализируем последовательность переноса для трёх дисков 1213121, для четырёх дисков: 1213121412131215121312141… Делаем выводы [12-16]: 1. Итак, каждый нечетный перенос - это перенос первого диска. 2. Сначала переносится первый диск, потом не первый, затем снова первый, потом не первый и т. д. 3. Для первого диска всегда два варианта переноса. Если начальное количество дисков четное, то первый диск движется по часовой стрелке, а если нечетное - против. 4. Понятие «не первый диск» полностью определяет, какой диск и куда следует переносить в данный момент, поскольку для «не первого диска» вариант всего один. 4. Алгоритмическое решение задачи о Ханойской башне. Попробуем построить схему алгоритма. Получаем (рис. 8). Рис. 8. Общий алгоритм решения задачи о Ханойской башне Теперь надо раскрыть подалгоритмы переноса дисков. Перенос против часовой стрелки (рис. 9). Рис. 9. Алгоритм переноса против часовой стрелки Перенос по часовой стрелке (рис. 10). Рис. 10. Алгоритм переноса по часовой стрелке Рассмотрим перенос не первого диска - наименьшего из не первых (предполагается, что определение не первого выполнено). Для этого преобразуем схему алгоритма на рис. 10, сделаем три выхода, получим (рис. 11). Рис. 11. Алгоритм переноса по часовой стрелке с выходами А, В, С Эти три алгоритма со входами А, В, С применимы и для переноса по часовой стрелке с такими же выходами А, В, С (рис. 12). Рис. 12. Алгоритм переноса по часовой стрелке с выходами А, В, С Выводы. Таким образом, алгоритм решения задачи о Ханойской башне на графе «двигаться вправо, если число дисков нечётное», «двигаться влево, если число дисков чётное» без использования графической интерпретации может быть интерпретирован как движения по кругу с чередованием «по часовой стрелке», «против часовой стрелки». Если начальное количество дисков четное, то первый диск движется по часовой стрелке, а если нечетное - против. Для «не первого диска» вариант всего один. В этом плане, оказывается, задача о Ханойской башне хорошо согласуется с такой структурой, как куб [16-19]. Оптимальное решение - это движение почти по гамильтонову циклу для трёхмерного куба ХУХZХУZ и для четырехмерного ХУХZХУХWХУХZХУХ (рис. 13). Рис. 13. Ханойская башня и куб соседних чисел Оказывается, если заменить обозначения Х на А, Y на В, Z на С, то указанный на рис. 13 оптимальный путь в четырёхмерном кубе будет соответствовать обозначениям на дюймовой линейке [20].

Об авторах

С. Ф Тюрин

Пермский национальный исследовательский политехнический университет

Email: tyurinsergfeo@yandex.ru

Список литературы

Статистика

Просмотры

Аннотация - 65

PDF (Russian) - 24

Ссылки

• Ссылки не определены.