- Рекурсивне рішення [ правити | правити код ]
- «Трикутна» рішення [ правити | правити код ]
- Циклічне рішення [ правити | правити код ]
- Застосування коду Грея для вирішення [ правити | правити код ]
- З чотирма і більше стрижнями [ правити | правити код ]
- Алгоритм фрейм - Стюарта [ правити | правити код ]
open wikipedia design.
Ханойська вежа є однією з популярних головоломок XIX століття . Дано три стрижня, на один з яких нанизані вісім кілець, причому кільця відрізняються розміром і лежать менше на більшій. Завдання полягає в тому, щоб перенести піраміду з восьми кілець за найменше число ходів на інший стрижень. За один раз дозволяється переносити тільки одне кільце, причому не можна класти більше кільце на меншу.
Цю гру придумав французький математик Едуард Люка в 1883 році [1] , Її продавали як забавну іграшку. Спочатку вона називалася «Професор Клаус (Claus) з Коледжу Лі-Су-Стьян (Li-Sou-Stian)» [1] , Але незабаром виявилося, що таємничий професор з неіснуючого коледжу - не більше ніж анаграма прізвища винахідника гри, професора Люка (Lucas) з коледжу Сен-Луї (Saint Louis).
Існує кілька підходів до вирішення, всі вони дають ідентичні результати c одним і тим же підсумком.
Рекурсивне рішення [ правити | правити код ]
Рекурсивно вирішуємо завдання «перенести вежу з n -1 диска на 2-й штир». Потім переносимо найбільший диск на 3-й штир, і рекурсивно вирішуємо завдання «перенеси вежу з n -1 диска на 3-й штир».
Звідси методом математичної індукції робимо висновок, що мінімальне число ходів, необхідне для вирішення головоломки, дорівнює 2 n - 1, де n - число дисків [2] [3] .
В інформатиці завдання, засновані на легенді про Ханойські вежі, часто розглядають як приклад використання рекурсивних алгоритмів і перетворення їх до нерекурсівние.
«Трикутна» рішення [ правити | правити код ]
Розташуємо штирі у вигляді трикутника. Почнемо з самого маленького кільця і перекладемо його на будь-яку позначку. Надалі це кільце потрібно переміщати в тому ж напрямку, що і при першому перекладанні. Потім перенесемо яке-небудь з решти кілець (такий хід єдиний), після чого знову перекладемо найменше кільце і т. Д. (Цікаво зауважити, що Перенумерувати «кільця» по порядку, ми доб'ємося несподіваного ефекту: парні кільця будуть переміщатися з однієї вершини трикутника в іншу в одному напрямку, а непарні - в протилежному напрямку.)
Циклічне рішення [ правити | правити код ]
Позначимо через «1-2» така дія: перекласти диск або з 1-го штиря на 2-й, або з 2-го на 1-й, в залежності від того, де він менше. Тоді, щоб вирішити головоломку з парним кількістю дисків, треба багато разів повторювати дії: 1-2, 1-3, 2-3. Якщо число дисків непарній - 1-3, 1-2, 2-3.
Застосування коду Грея для вирішення [ правити | правити код ]
код Грея , Рефлексний двійкового коду в двійковій системі числення , В якому два сусідніх значення розрізняються тільки в одному двійковому розряді. Спочатку код Грея призначався для захисту від помилкового спрацьовування електромеханічних перемикачів. Сьогодні коди Грея широко використовуються для спрощення виявлення і виправлення помилок в системах зв'язку, а також у формуванні сигналів зворотного зв'язку в системах управління. Код отримав ім'я дослідника лабораторій Bell Labs Френка Грея. Він запатентував (за номером 2632058) і використовував цей код в своїй імпульсної системі зв'язку.
Коди Грея можуть бути застосовані у вирішенні задачі про Ханойські вежах.
Нехай N - кількість дисків. Почнемо з коду Грея довжини N, що складається з одних нулів (тобто G0), і будемо рухатися по кодам Грея (від Gi переходити до Gi + 1). Поставимо у відповідність кожному i-ому біту поточного коду Грея i-ий диск (причому наймолодшому біту відповідає найменший за розміром диск, а найстаршому біту - найбільший). Оскільки на кожному кроці змінюється рівно один біт, то ми можемо розуміти зміна біта i як переміщення i-го диска. Зауважимо, що для всіх дисків, окрім найменшого, на кожному кроці є рівно один варіант ходу (за винятком стартової та фінальної позицій). Для найменшого диска завжди є два варіанти ходу, проте є стратегія правильного вибору ходу: для непарного N послідовність переміщень найменшого диска f → t → r → f → t → r → ... (де f - стартовий стрижень, t - фінальний стрижень, r - залишився стрижень), а для парного f → r → t → f → r → t → ....
З чотирма і більше стрижнями [ правити | правити код ]
Хоча варіант з трьома стержнями має просте рекурсивне рішення, оптимальне рішення Ханойська вежі з чотирма стержнями довгий час було невирішеною проблемою.
Очевидно, що для будь-якої кількості стрижнів існує алгоритм для знаходження оптимальних рішень, досить уявити головоломку у вигляді неорієнтованого графа, зіставивши розміщень дисків вершини, а ходам - ребра, і використовувати будь-який алгоритм пошуку (Наприклад, пошук в ширину ) Для знаходження оптимального рішення. Однак ефективної стратегії визначення оптимального рішення для великого числа дисків немає: кількість ходів, необхідне для вирішення головоломки з 10 стрижнями і 1000 дисками, залишається невідомим.
Існує імовірно оптимальний алгоритм фрейм - Стюарта, розроблений в 1941 році [4] . Пов'язана гіпотеза фрейм - Стюарта стверджує, що алгоритм фрейм - Стюарта завжди знаходить оптимальне рішення. Оптимальність алгоритму фрейм - Стюарта була експериментально перевірена аж до 30 дисків на 4 стрижнях [5] . У 2014 році було остаточно доведено, що для чотирьох стрижнів Алгоритм фрейм - Стюарта є оптимальним [6] .
Інші варіанти вирішення Ханойська вежі з чотирма стержнями розглядаються в оглядовій статті Пола Стокмайера [7] .
Алгоритм фрейм - Стюарта [ правити | правити код ]
Алгоритм фрейм - Стюарта, що дає оптимальне рішення для чотирьох і імовірно оптимальне рішення для більшої кількості стрижнів, описується наступним чином:
Алгоритм може бути описаний рекурсивно:
- Для деякого k {\ displaystyle k}
, 1 ≤ k <n {\ displaystyle 1 \ leq k <n}
, Перенести верхні k {\ displaystyle k}
ходів.
- Чи не використовуючи стрижень i, що містить тепер верхні k {\ displaystyle k}
дисків на кінцевий стержень, використовуючи тільки залишилися r - 1 {\ displaystyle r-1}
стрижнів і витративши на це T (nk, r - 1) {\ displaystyle T (nk, r-1)}
ходів.
- Нарешті, перемістити верхні k {\ displaystyle k}
На весь процес потрібно 2 T (k, r) + T (nk, r - 1) {\ displaystyle 2T (k, r) + T (nk, r-1)} 
Придумана професором Люка легенда свідчить, що в Великому храмі міста Бенарес , Під собором, який зазначає середину світу, знаходиться бронзовий диск, на якому укріплені 3 алмазних стержня, висотою в один лікоть і товщиною з бджолу. Давним-давно, на самому початку часів, монахи цього монастиря завинили перед богом Брахмою. Розгніваний Брахма спорудив три високих стрижня і на один з них поклав 64 диска, зроблених з чистого золота. Причому так, що кожен менший диск лежить на більшій.
Як тільки всі 64 диска будуть перекладені зі стрижня, на який Брахма склав їх при створенні світу, на інший стрижень, вежа разом з храмом звернуться в пил і під грім загине світ.
Кількість перекладань залежно від кількості кілець обчислюється за формулою 2 n - 1 {\ displaystyle 2 ^ {n} -1} 
Число переміщень дисків, які повинні зробити монахи, так само 18 446 744 073 709 551 615 . Якби монахи, працюючи день і ніч, робили кожну секунду одне переміщення диска, їх робота тривала б майже 585 мільярдів років.
В оповіданні Еріка Френка Рассела «Ваш хід» (Now Inhale, в іншому перекладі - «Гра на виживання») [9] , Щоб відтягнути час страти інопланетянами, головний герой вибирає гру в Ханойську вежу з 64 дисками в якості останньої гри. Оголошені правила модифіковані для двох гравців - гравці повинні перекладати диски по одному за хід, переможцем вважається той, хто зробить останній хід. Герой називає таку гру «арки-маларкі» і клянеться, що «священнослужителі бенареська храму» на Землі грають в цю гру.
У фільмі " Повстання планети мавп »Ханойську вежу використовують в якості перевірки інтелекту піддослідних. Мавпа збирає головоломку з чотирьох кілець за двадцять ходів.
Ханойська вежа - одна з традиційних головоломок в відеоіграх канадської компанії BioWare - зокрема, " Jade Empire »,« Star Wars: Knights of the Old Republic »І« Mass Effect ». Зустрічаються вони і в квесті Legend of Kyrandia II.
- ↑ 1 2 Мартін Гарднер, Математичні головоломки й розваги
- ↑ Petković, Miodrag. Famous Puzzles of Great Mathematicians. - AMS Bookstore, 2009. - P. 197. - ISBN 0-8218-4814-3 .
- ↑ Graham, Ronald. Concrete Mathematics: A Foundation for Computer Science. - Addison-Wesley, 1998. - P. 21. - ISBN 0201558025 .
- ↑ Solution to advanced problem 3819, American Mathematical Monthly, 1941.
- ↑ Korf, Richard E., and Ariel Felner (2007). "Recent Progress in Heuristic Search: a Case Study of the Four-Peg Towers of Hanoi Problem" . IJCAI : 2324-2329.
- ↑ Bousch, T. (2014 року). "La quatrieme tour de Hanoi". Bull. Belg. Math. Soc. Simon Stevin. 21: 895-912.
- ↑ Paul Stockmeyer (1994). "Variations on the Four-Post Tower of Hanoi Puzzle" . Congressus Numerantium. 102: 3-12.
- ↑ University of Toronto CSC148 Slog (неопр.) (April 5, 2014 року). Дата обертання 22 липня 2015.
- ↑ Рассел, Ерік Френк (4 1994). "Ваш хід". якщо : 34-42.