I am modeling the towers of Hanoi problem with n discs and k pegs, and I am trying to find its maximun branching factor. The problem is that, as the number both of discs and pegs is variable, so is the number of actions possible for each node. How can I find a generic way of assesing the maximum branching factor depending on k and n?
In general the smallest disc can move to any other peg: k-1 options.
The second smallest disk (at the top of the stack on a peg; might not be the second smallest overall) can move onto any pegs except the one with the smallest disc: k-2 options.
This continues until the largest disk on the top of a peg, which can't move anywhere (assuming n>k).
So, the expected branching factor is: (k-1)+(k-2)+(k-3)+...+2+1 = (k-1)*k/2
The only time you won't get this is when one of the pegs contains no disks. If n>>k this will rarely happen. But, it means that if you are searching from random states to a goal state, you should consider searching backwards, because the standard goal state has the lowest branching factor since only one peg has a disc.
The n < k case can be similarly analyzed, except that you stop after n disks and subtract an additional term for the moves we counted the first time around that aren't available now:
k(k-1)/2 - (k-n)(k-n-1)/2