Как это работает? Странные Башни Ханойского Решения - PullRequest
Новая
       33

Как это работает? Странные Башни Ханойского Решения

50 голосов
/ 05 февраля 2010

Я был потерян в Интернете, когда обнаружил это необычное итеративное решение для башен Ханоя: 

for (int x = 1; x < (1 << nDisks); x++)
{
     FromPole = (x & x-1) % 3;
     ToPole = ((x | x-1) + 1) % 3;
     moveDisk(FromPole, ToPole);
}

Этот пост также имеет аналогичный код Delphi в одном из ответов.

Однако, судя по всему, я не могу найти хорошего объяснения, почему это работает.

Может кто-нибудь помочь мне понять это?

Ответы [ 3 ]

41 голосов
/ 06 февраля 2010

рекурсивное решение для Ханойских башен работает так, что если вы хотите переместить 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)

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

Если вы посмотрите на сами решения, для 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. Рекурсивное решение начинается с Ханоя (0, 2, 1, N), поэтому в среднем ряду (2 ** (N-1)) у вас должен быть Moveisk (0, 2). Теперь по правилу рекурсии, в (2 ** (N-2)) вам нужно иметь Moveisk (0, 1) и в (2 ** (N-1)) + 2 ** (N-2) MoveDisk ( 1, 2). Это создает шаблон «0,0,1» для колышков from, который виден с различными перестановками в таблице выше (проверьте строки 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 не обязательно тесно связана с проблемой Ханоя или не должна быть; достаточно того, что у него есть свойство копирования и что оно производит правильные перестановки в правильном порядке.

9 голосов
/ 20 февраля 2011

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

Первое примечание: на среднем шаге x = 2 N-1 этого алгоритма колышек "from" равен 0, а колышек "to" равен 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)

Фундаментальное наблюдение здесь: В строке (с) колышки - это точно колышки Ханоя (0, 2 N-1 , 2 N , N-1), сдвинутые на 2 N-1 % 3, т.е. это в точности колышки линии (а) с добавленной к ним суммой .

Я утверждаю, что из этого следует, что когда мы бегущая строка (с), колышки "от" и "до" - это соответствующие колышки линии (а), сдвинутые на 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 N , имеем f (2 N - i) == f (2 N + i) + 2 N % 3 и g (2 N - i) == g (2 N + i) + 2 N % 3.

И то, и другое легко показать.

4 голосов
/ 06 февраля 2010

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

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

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.

...