Теория ханойской башни
Всякая теория - потому и теория, что состоит из теорем, не исключение и теория ханойской башни. Но сначала – приведу описание этой головоломки, ведь не все с ней знакомы.(а кто знаком, может спокойно это описание пропустить.)
Пусть у нас есть n дисков различных диаметров (и нет ни одного повторяющегося диаметра) и три позиции. Пусть в исходном состоянии все диски, в порядке уменьшения диаметра (снизу вверх) находятся в позиции 1 (исходной)
Требуется: получить ситуацию, в которой все диски (в порядке уменьшения диаметра, снизу вверх) находятся в позиции 3 (конечной)
Допустимые операции: любой диск, если он в верхней позиции, можно переносить в любую другую позицию, если она свободна или только на диск бОльшего диаметра.(чем перемещаемый диск)
В дополнение к этому сразу скажу, что вам легче будет понимать эту статью, если вы обзаведётесь соответствующим инвентарём. Например, возьмите для этого несколько монет разного достоинства: 5, 2, 1, 0.5 и 0.1 руб. И, в процессе чтения статьи, воспроизводите те ситуации, о которых идёт речь в статье.
В оригинальной головоломке – 8 дисков. Но мы, вовсе не страдая (крутым) честолюбием, сначала попробуем решить для этой задачи самый простой её вариант, банальный, с 1 диском.
В итоге - получится 1-ая теорема теории Ханойской башни:
если количество дисков=1, то диск сразу переставляем в целевую позицию.(что и позволит решить задачу в 1 шаг, то есть наиболее оптимально.)
И принимается эта теорема без доказательств.
(А точнее - без логических доказательств. Ибо доказательство мы получили на практике, путём эксперимента.
И это, как ни странно (для серьёзных геометров, например) допустимо.
Ибо серьёзные геометры, в отличие от серьёзных же физиков, не понимают, что свои аксиомы как-так они приняли без доказательств? И это, стало быть, выдумки? Нет, это результаты опыта, теперь уже геометрического. А что, разве таких (опытов) не бывает? Почему же?)
(а значит, это – аксиома, или теорема 0-го уровня. (как я их называю. А что тут голову морочить-то? Ведь и теорема и аксиома – это утверждения, причём зарегистрированные, как истинные. А кроме того, и теоремы есть разных уровней: 1-го, 2-го и т. д.)
Отсюда вывод (а точнее, гипотеза): любая теория имеет аксиомы. Но доказать эту гипотезу весьма просто: для доказательства всякой теоремы используются опорные утверждения (уже доказанные)(как минимум, стало быть, одно), поэтому в итоге придём к ситуации, когда принимать опорное утверждение придётся без доказательства. Что и разорвёт этот порочный круг.) Но это не значит, что в истинности её не надо убеждаться. Но как убедиться? А на опыте.
Да и что, собственно, нужно доказывать? Если нет короче (то есть оптимальнее) алгоритма, чем в 1 шаг? Ну, разве что то, что нет иных таких алгоритмов. Но опять же, откуда возьмутся иные (данному) алгоритму (и причём оптимальные) алгоритмы, если исходный алгоритм – состоит из одного шага? Ведь иные алгоритмы возникают для алгоритмов из 2-х и более шагов. (Доказательство: например, как достичь (кратчайшим путём) пункта Б из пункта А? Иной скажет: тут есть 2 варианта: двигаясь через пункт В или через пункт Г. Но как быть, если нет на нашей «географической» карте пункта В и пункта Г? Только так: сразу перейти из А в Б. Что и требовалось доказать.)
2-ая теорема ХБ. Она получается при переходе к более сложной задаче, для 2-х дисков. Предположим, что диск 2 (нумерацию дисков ведём по убыванию их диаметра) уже отсутствует на позиции 1, тогда бы задача свелась к уже решенной в теореме 1: надо диск 1 переложить сразу в позицию 3. Как бы мы смогли подготовить этот шаг? Понятно, что переложив диск 2 в позицию 2. Вот мы и доказали теорему 2: если в пирамиде 2 диска, то 1-ый шаг – это перекладка диска 2 в позицию 2. (а не в позицию 3, как это было в предыдущей задаче)
Отсюда возникает следующая гипотеза (в будущем – теорема3): если в пирамиде нечётное количество дисков, то 1-ый ход оптимального алгоритма – это перемещение (верхнего) диска сразу в позицию 3. А если в пирамиде – чётное количество дисков, то 1-ый ход – это перемещение верхнего диска в позицию 2 (промежуточную)
Докажем эту гипотезу. Но сначала докажем лемму (то есть вспомогательную теорему):
добавление одного диска в пирамиду приводит к смещению 1-го шага из позиции 3 в позицию 2 или наоборот.
Пускай доказано, что в решении задачи для пирамиды с n дисками 1-ый оптимальный ход – это перемещение верхнего диска в позицию х. Перейдём к решению задачи с n+1 дисками. Предположим, что верхний диск уже перемещен. Тогда решение задачи сводится к решению задачи для n дисков. 1-ый оптимальный ход которой, согласно допущению - перемещение верхнего диска в позицию х. Тогда как мы можем обеспечить выполнение этого шага? Только переместив диск n+1 – в позицию иную, чем х (то есть в позицию 2 при х=3 и наоборот) Что и требовалось доказать.
После этого доказательство основной теоремы (=теоремы3) – сводится к весьма простым рассуждениям.
Поскольку доказано, что для решения задачи при n=1 1-ый оптимальный шаг – это перемещение диска в позицию 3, то для решения задачи с n+1 дисками (в соответствии с доказанной выше леммой) 1-ый оптимальный шаг – это перемещение диска в позицию 2. Отсюда понятно, что при переходе от нечетного к чётному количеству дисков 1-ый оптимальный шаг – всегда будет меняться с перемещения диска в позицию 3 – на перемещение диска в позицию 2, и наоборот (то есть при переходе с чётного количества дисков – на нечётное) В итоге всем задачам с нечётным количеством дисков – соответствует 1-ый оптимальный шаг в позицию 3, а всем задачам с чётным количеством дисков - соответствует 1-ый оптимальный шаг в позицию 2. Что и требовалось доказать.
Заметьте, теорема1 и теорема2 – являются частными случаями теоремы3. И это – результат применения принципов решения т-задач. Теорема3 теперь основная теорема теории.
Ну что ж, вроде бы всё? Нет, нужна еще одна теорема, теорема4.
И она нужна для того, чтобы не только в начальной ситуации определять оптимальный ход, но и в любой, возникающей в процессе решения задачи.
Так, пусть n=3 и 1-ый ход уже совершён, то есть возникла ситуация С1: a=1,2; b=; c=3. (здесь позиции обозначены буквами, диски, как и прежде - числами) В этой ситуации теорема3 нам подсказывает ход к С2: a=1; b=2; c=3.
В ситуации же С2 рекомендуемый ход таков: 1:ac, но он недопустим согласно правилам. Но его можно сделать допустимым засчёт хода: 3:cb. Именно этот ход мы и назовём обеспечивающим ходом в ситуации С2, ход же 1:ac – обеспечиваемым ходом в этой ситуации. В возникшей в результате ситуации С4 опять рекомендуемый ход 2:bc опять становится обеспечиваемым и для него требуется обеспечивающий ход 3:ba, после чего мы без проволочек идём к цели.
Отсюда вывод: существуют такие промежуточной ситуации решения задачи ХБ, что рекомендуемый теоремой3 ход является недопустимым согласно правилам. В этом случае сначала выполняется ход, опеспечивающий рекомендумый ход, а потом рекомендуемый.
Поскольку основанием для запрета хода является либо занятость целевой позиции меньшим диском либо покрытость исходной позиции меньшим диском, что несовместимо, а рекомендуемый теоремой3 ход – всегда 1, то и обеспечивающий ход в любой позиции будет всего 1 (или его вообще не будет) Что и говорит об оптимальности получаемого в итоге алгоритма.
(Для пущей убедительности приведём спецификацию всех ходов в любой промежуточной ситуации:
-1 ход является обратным (поэтому неактуальным для нашей задачи, далее по этому поддереву не углубляемся);
-1 ход – нерекомендуемый (=неоптимальный, далее по этому поддереву не углубляемся)
-1 ход – рекомендуемый
Если рекомендуемый ход недопустим, то для него существует:
-1 обеспечивающий ход
-1 блокирующий ход, далее по этому поддереву не углубляемся)
(А1-)
Ну вот, теперь уфф!
Ибо в итоге нами был получен чёткий критерий, который помогает выбрать оптимальный ход в любой ситуации решения данной головоломки.(а стало быть, безошибочно находить оптимальный алгоритм для решения задач ХБ любой сложности, то есть в любым количеством дисков) Но, может, вы думаете, что получение его заняло у автора всего 1 вечер (который ушёл на написание статьи?) Нет, это стоило автору почти 2 месяца его жизни.
Да, чуть не забыл. Зачем я написал это статью? А чтобы показать, что оптимальное решение задачи создания теории (назовём такую задачу т-задачей) – лежит в русле применения теории решения такой задачи, а вовсе не метода проб и ошибок, как повелось. Метод проб и ошибок – да, допустим (и даже более того – является единственным средством решения) только для совершенно новых задач.
Что же касается реплик о том, что я здесь, вроде бы, создал некую пустяковую, в общем-то теорию – теорию некоторой игры, а поэтому какое значение это имеет для развития науки? Да ровно никакого!
То на них отвечу так: теория игры – это правила создания выигрышного алгоритма для данной игры, в данной ситуации. Но чем наше знание, например, физики – это не правила создания алгоритма вычисления при решении физических задач?
P.S. Уважаемые читатели, пожалуйста, в своих отзывах не исходите из того, что отзыв – это всего лишь похвала. Я принимаю всё: и похвалы, и критику и вопросы. И с удовольствием отвечу на все ваши реплики. Но желательно, не очень уж язвительные.
**
-А1: Всё вроде бы убедительно, но заметьте: в данном случае мы применяли теорему3 для любой подзадачи исходной задачи. Но каковы основания для этого?
Взглянем на (n)-задачу ХБ (для определённости пусть n нечётно) с другого ракурса:
1)чтобы решить (1,n)-задачу (где n>1), нужно сначала решить (2,n)-задачу (в промежуточную позицию)(и это равносильно (1,n-1)-задаче, т.к. диск1 не задействуется), затем переместить диск1 в целевую позицию, после чего опять решить (2,n)-задачу, но уже в целевую позицию.
И это, заметьте, у же не гипотеза!
Отсюда можно построить рекуррентную последовательность утверждений:
2)чтобы решить (2,n)-задачу, нужно сначала решить (3,n)-задачу (в промежуточную позицию)(и это равносильно (1,n-2)-задаче, т.к. диск2 не задействуется), затем переместить диск2 в целевую позицию, после чего опять решить (3,n)-задачу, но уже в целевую позицию.
B так далее, пока не дойдём до :
n-1)чтобы решить (n-1,n)-задачу, нужно сначала решить (n,n)-задачу (в промежуточную позицию)(и это равносильно (1,1)-задаче, т.к. диск(n-1) не задействуется), затем переместить диск(n-1) в целевую позицию, после чего опять решить (n,n)-задачу, но уже в целевую позицию.
n)чтобы решить (n,n)-задачу, нужно переместить диск(n) в целевую позицию. И всё.
Итак,теперь понятно, как устроен итоговый алгоритм при нечётном n (далее целевая позиция – c, промежуточная - b):