Гипотезы

Вернемся к нашим таблицам

table41.png

table42.png

Основываясь на данных таблиц можно выдвинуть следующие гипотезы об оптимальном количестве ходов в алгоритме Фрейма-Стюарта:

1) Оптимальное число ходов алгоритмом Фрейма-Стюарта определяется следующей рекуррентной формулой (такой, в которой последующее значение выражается через одно или несколько предыдущих) 

image039.png

 где k – номер треугольного числа, такого, что image041.png

2) Число q дисков, перекладываемых в первую очередь равно

image043.png

Верность данных гипотез доказана в работах разных авторов, например, в [6]. Давайте опираясь на формулы, приведенные выше выведем явные формулы для вычисления количества ходов.

Сначала выведем явную формулу, когда число дисков треугольное С2k+1. В этом случае в первую очередь выгодно переложить С2k диск. Поскольку С2k+1-С2k=k, то

image055.png

image057.png

image059.png

    Остается доказать, что именно алгоритм Фрейма-Стюарта дает оптимальное решение среди всех возможных способов перекладывания дисков. Один из методов доказательства этого факта основывается на методах теории графов.

Читать дальше


[6] Klavžar, S. Simple Explicit Formulas for the Frame-Stewart Numbers//S. Klavžar, U. Milutinović/ Ann. of Comb. 6(2002), 157–167.