Как это работает? Странные башни Ханоя

Ответ 1

рекурсивное решение для башен Ханоя работает так, что если вы хотите переместить N дисков из привязки A в C, вы сначала перемещаете N-1 из A в B, затем вы перемещаете нижний на C, а затем вы перемещаете снова N-1 дисков от B до C. По существу,

hanoi(from, to, spare, N):
  hanoi(from, spare, to, N-1)
  moveDisk(from, to)
  hanoi(spare, to, from, N-1)

Ясно, что hanoi (_, _, _, 1) принимает один ход, а hanoi (_, _, _, k) принимает столько ходов, сколько 2 * hanoi (_, _, _, k-1) + 1 Таким образом, длина решения растет в последовательности 1, 3, 7, 15,... Это та же последовательность, что и (1 < k) - 1, что объясняет длину цикла в алгоритме, который вы опубликовали.

Если вы посмотрите на сами решения, то для N = 1 вы получите

FROM   TO
          ; hanoi(0, 2, 1, 1)
   0    2    movedisk

При N = 2 вы получаете

FROM   TO
          ; hanoi(0, 2, 1, 2)
          ;  hanoi(0, 1, 2, 1)
   0    1 ;   movedisk
   0    2 ;  movedisk
          ;  hanoi(1, 2, 0, 1)
   1    2 ;   movedisk

И для N = 3 вы получите

FROM   TO
          ; hanoi(0, 2, 1, 3)
          ;  hanoi(0, 1, 2, 2)
          ;   hanoi(0, 2, 1, 1)
   0    2 ;    movedisk
   0    1 ;   movedisk
          ;   hanoi(2, 1, 0, 1)
   2    1 ;    movedisk
   0    2 ;  movedisk ***
          ;  hanoi(1, 2, 0, 2)
          ;   hanoi(1, 0, 2, 1)
   1    0 ;    movedisk
   1    2 ;   movedisk
          ;   hanoi(0, 2, 1, 1)
   0    2 ;    movedisk

Из-за рекурсивности решения столбцы FROM и TO следуют рекурсивной логике: если вы берете среднюю запись в столбцах, части выше и ниже являются копиями друг друга, но с перестановкой чисел. Это является очевидным следствием самого алгоритма, который не выполняет арифметику на кодах привязки, а только переставляет их. В случае N = 4 средний ряд равен x = 4 (отмечен тремя звездами выше).

Теперь выражение (X и (X-1)) выводит из строя младший бит бит X, поэтому он отображает, например. чисел от 1 до 7 следующим образом:

   1 ->  0
   2 ->  0
   3 ->  2
   4 -> 0 (***)
   5 ->  4 % 3 = 1
   6 ->  4 % 3 = 1
   7 ->  6 % 3 = 0

Фокус в том, что, поскольку средняя строка всегда имеет точную мощность в два и, следовательно, имеет ровно один бит, часть после средней строки равна части перед ней, когда вы добавляете значение средней строки (4 в этом случае ) к строкам (т.е. 4 = 0 + 4, 6 = 2 + 6). Это реализует свойство "copy", добавление средней строки реализует перестановочную часть. Выражение (X | (X-1)) + 1 устанавливает младший нулевой бит, который имеет свои правые и очищает их, поэтому он имеет схожие свойства, как ожидалось:

   1 ->  2
   2 ->  4 % 3 = 1
   3 ->  4 % 3 = 1
   4 -> 8 (***) % 3 = 2
   5 ->  6 % 3 = 0
   6 ->  8 % 3 = 2
   7 ->  8 % 3 = 2

Что касается того, почему эти последовательности действительно создают правильные номера кодов, рассмотрим столбец FROM. Рекурсивное решение начинается с hanoi (0, 2, 1, N), поэтому в среднем ряду (2 ** (N-1)) у вас должен быть moveisk (0, 2). Теперь по правилу рекурсии (2 ** (N-2)) вам нужно иметь moveisk (0, 1) и в (2 ** (N-1)) + 2 ** (N-2) moveisk ( 1, 2). Это создает шаблон "0,0,1" для столбцов, которые видны с различными перестановками в таблице выше (проверьте строки 2, 4 и 6 для 0,0,1 и строки 1, 2, 3 для 0,0, 2 и строки 5, 6, 7 для 1,1,0, все перестановленные версии одного и того же шаблона).

Теперь, после того, как все функции, обладающие этим свойством, создают собственные копии вокруг степеней двух, но с смещениями, авторы выбрали те, которые производят по модулю 3 правильные перестановки. Это не слишком трудная задача, потому что существует только 6 возможных перестановок трех целых чисел 0..2 и перестановки в логическом порядке в алгоритме. (X | (X-1)) + 1 не обязательно глубоко связана с проблемой Ханоя, или это необязательно; достаточно, чтобы он обладал свойством копирования и что он создает правильные перестановки в правильном порядке.

Ответ 2

Решение antti.huima, по сути, правильное, но я хотел что-то более строгое, и оно было слишком большим, чтобы вписаться в комментарий. Здесь:

Первое примечание: на среднем шаге x = 2 ^N-1 этого алгоритма "от" привязки равно 0, а привязка "до" равна 2 ^N% 3. Это оставляет 2 ^(N-1)% 3 для "запасной" привязки. Это также верно для последнего шага алгоритма, поэтому мы видим, что фактически алгоритм авторов это небольшой "чит": они перемещают диски с привязки 0 на привязку 2 ^N% 3, а не фиксированные, предварительно заданная привязка. Это может быть изменено с небольшой работой.

Оригинальный алгоритм Ханоя:

hanoi(from, to, spare, N):
    hanoi(from, spare, to, N-1)
    move(from, to)
    hanoi(spare, to, from, N-1)

Включение "от" = 0, "до" = 2 ^N% 3, "запасной" = 2 ^N-1% 3, мы получаем (подавляя % 3-х):

hanoi(0, 2**N, 2**(N-1), N):
(a)   hanoi(0, 2**(N-1), 2**N, N-1)
(b)   move(0, 2**N)
(c)   hanoi(2**(N-1), 2**N, 0, N-1)

Основное замечание здесь: В строке (с) штифты являются точками привязки hanoi (0, 2 ^N-1 2 ^N N-1), сдвинутыми на 2 ^{N -1}% 3, т.е. они являются точками привязки строки (a) с добавленной к ним суммой.

Я утверждаю, что из этого следует, что когда мы (c), привязки "от" и "до" представляют собой соответствующие привязки линии (a), сдвинутые на 2 ^N-1% 3. Это следует из простой, более общей леммы о том, что в hanoi(a+x, b+x, c+x, N) "от и" до "штифтов сдвинуты точно в x из hanoi(a, b, c, N).

Теперь рассмотрим функции f(x) = (x & (x-1)) % 3
g(x) = (x | (x-1)) + 1 % 3

Чтобы доказать, что данный алгоритм работает, нам нужно только показать, что:

• f (2 ^N-1) == 0 и g (2 ^N-1) == 2 ^N
• для 0 < я < 2 ^N имеем f (2 ^N - i) == f (2 ^N + i) + 2 ^N% 3 и g (2 ^N - i) == g (2 ^N + i) + 2 ^N% 3.

Оба из них легко показать.

Ответ 3

Это напрямую не отвечает на вопрос, но было слишком долго, чтобы добавить комментарий.

Я всегда делал это, анализируя размер диска, который должен двигаться дальше. Если вы посмотрите на перемещенные диски, это получится:

1 disk  : 1
2 disks : 1 2 1
3 disks : 1 2 1 3 1 2 1
4 disks : 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

Нечетные размеры всегда движутся в противоположном направлении от четных, чтобы, если колышки (0, 1, 2, повтор) или (2, 1, 0, повтор).

Если вы посмотрите на шаблон, кольцо для перемещения - это старший бит набора xor количества ходов и числа ходов + 1.