Обобщенные башни Ханоя — оптимальный алгоритм

Проблема Ханойских башен хорошо известна и решена, но есть ее обобщения, которые все еще представляют некоторые проблемы. Теперь у нас есть оптимальный алгоритм для решения проблемы с четырьмя колышками — можно ли его обобщить на проблему с n колышками?

Головоломка «Ханойские башни» была представлена в 1833 году и состоит из трех колышков и стопки дисков разного размера. Цель состоит в том, чтобы переместить все диски от начальной привязки к конечной привязке, перемещая по одному диску на другую привязку, при условии, что вы никогда не помещаете диск большего размера на диск меньшего размера.

Существует ряд алгоритмов, решающих задачу с наименьшим числом ходов, и все они эквивалентны, будь то итерационные или рекурсивные. Вы можете доказать, что задача n-disk 3-peg может быть решена за 2n-1 ходов.

В 1909 году книга головоломок включала версию игры с четырьмя колышками под названием «Головоломка Рива». Это, конечно, первая в последовательности из n, m головоломок с n дисками и m колышками — стандартная головоломка — n, 3, а головоломка Рива — n, 4.

Ясно, что у любой обобщенной головоломки есть решение, потому что вы можете просто игнорировать дополнительные колышки и рассматривать ее как задачу n, 3, имеющую хорошо известный алгоритм. Однако алгоритм доказуемо оптимален только для задачи n, 3, а не для задачи n, 4 или n, m.

То есть вы можете решить задачу n, m за 2n-1, но можно ли сделать меньше шагов и какое минимальное количество шагов требуется? Учитывая, что у вас есть дополнительные колышки, кажется вполне разумным предположить, что их можно использовать для уменьшения количества ходов, но каков оптимальный алгоритм?

В 1941 г. журнал American Mathematical Monthly опубликовал два эквивалентных алгоритма. Фрейма и Стюарта, которые решили общую задачу n, m, но ни одна из них не оказалась оптимальной — они просто выполняли свою работу быстрее, чем стандартный алгоритм Ханойских башен.

Алгоритм Стюарта / Фрейма предназначен для n дисков, m колышков, а T (n, m) — минимальное количество ходов для n, m задачи:

Для некоторого k, 1 <= k 4?

Прочтите статью, чтобы узнать больше.