Как рассчитать максимальный коэффициент ветвления для Ханойских башен

Question

Я моделирую проблему башен Ханоя с n дисками и k колышками и пытаюсь найти ее максимальный коэффициент ветвления. Проблема заключается в том, что, поскольку число дисков и колышков является переменным, то количество действий, возможных для каждого узла. Как мне найти общий c способ оценки максимального коэффициента ветвления в зависимости от k и n?

Answer 1

Как правило, самый маленький диск c может перемещаться к любому другому варианту колышка: k-1.

Второй самый маленький диск (в верхней части стека на колышке; может быть не вторым самым маленьким) в целом) может перемещаться на любые колышки, кроме одного с наименьшими параметрами dis c: k-2.

Это продолжается до самого большого диска на вершине колышка, который никуда не может переместиться (при условии n> k).

Итак, ожидаемый коэффициент ветвления: (k-1) + (k-2) + (k-3) + ... + 2 + 1 = (k-1) * k / 2

Единственный раз, когда вы не получите это, когда один из колышков не содержит дисков. Если n >> k, это случится редко. Но это означает, что если вы осуществляете поиск из случайных состояний в целевое состояние, вам следует рассмотреть возможность поиска в обратном направлении, поскольку стандартное целевое состояние имеет самый низкий коэффициент ветвления, поскольку только один колышек имеет дис c.

. Случай n

k (k-1) / 2 - (кн) (кн-1) / 2