我正在用n个圆盘和k个钉子对河内问题的塔进行建模，我试图找到其最大分支因子。问题在于，由于圆盘和桩钉的数量都是可变的，因此每个节点可能执行的动作数量也是如此。如何找到一种根据k和n评估最大分支因子的通用方法？
通常，最小的光盘可以移动到任何其他钉：k-1个选项。
第二个最小的磁盘（在一个钉的堆栈的顶部；可能不是第二个最小的磁盘）可以移动到任何钉上，除了磁盘最小的那个：k-2个选项。
此操作将一直持续到钉子顶部的最大磁盘，该磁盘无法移动到任何位置（假设n> k）。
因此，预期分支因子为：（k-1）+（k-2）+（k-3）+ ... + 2 + 1 =（k-1）* k / 2
您唯一一次不会得到的是其中一个钉不包含任何磁盘时。如果n >> k，这种情况很少发生。但是，这意味着，如果您要从随机状态搜索到目标状态，则应考虑向后搜索，因为标准目标状态的分支因子最低，因为只有一个钉子有一个圆盘。
可以对n k（k-1）/ 2-（k-n）（k-n-1）/ 2