Алгоритм Фрейма-Стюарта для p=4


Еще в 1941 году Фрейм и Стюарт [4,5] предложили алгоритм, который является предположительно оптимальным для данной задачи. Гипотеза о его оптимальности называется соответственно гипотезой Фрейма-Стюарта. Предположим, что у нас есть n дисков (сыров) и p подставок (табуреток если хотите).

1)    Обозначим минимальное число ходов, использующее n подставок и необходимое для перекладывания k дисков, как F(n,k). Так, например, мы уже знаем, что F(3,k)=2n-1, а F(4,3)=5.

2)    Теперь для некоторого числа дисков, например, q перенесем их на другой стержень за F(q,p) ходов. После этого свободных подставок, которые можно использовать для перекладывания станет на одну меньше.

3)    Оставшиеся диски можно будет переложить за F(n-q,p-1)

4)    Далее первые q дисков можно положить на стопку из больших дисков за F(p,q) ходов.

5)    На всю процедуру потребуется F(n,p)=F(n-q,p-1)+2F(q,p) ходов.

6)    Значение q выбирается таким способом, чтобы минимизировать F(n,p).

В результате получаем формулу:

image013.png

Давайте попробуем понять как работает этот алгоритм в случае с четырьмя подставками. Для одного, двух и трех дисков ситуация очевидна: F(1,4)=1, F(2,4)=3, F(3,4)=5. Для дальнейших вычислений будем строить таблицы.

table1.png

Анализ приведенный в таблице, позволяет нам сделать вывод, что F(4,4)=9 и достигается при q=1 или 2.

table2.png

В последней строке таблицы пользуемся свойством F(4,4)=9, доказанным на предыдущем шаге. Итак для каждого последующего значения n мы будем составлять таблицы, на каждом новом шаге задействуя результаты предыдущих вычислений. Рассмотрим теперь, что получится при n не превосходящем 10.

table3.png

Проанализируем таблицу и представим численные результаты в следующем виде:

table41.png               table42.png

Таким образом

image007.png

На основании этих наблюдений можно выдвинуть гипотезу о  том, что F(11,4)=F(10,4)+24, что подтверждается прямыми вычислениями.

Итак, что мы видим. Каждый раз, когда число дисков доходит до определенного рубежного значения: 1, 3, 6, 10, 15, 21 и.т.д. формула для вычисления числа ходов изменяется. Эти "рубежные значения"  заслуживают особого внимания. 

Читать далее


[4] Frame, J.S. Problems and Solutions: Advanced Problems: Solutions: 3918// J.S. Frame / The Amer. Math. Mon. 48 (1941) 216-217.

[5] Stewart, B. M. Problems and Solutions: Advanced Problems: Solutions: 3918// B.M. Stewart / The Amer. Math. Mon. 48 (1941) 217-219.