http://en.wikipedia.org/wiki/Tower_of_Hanoi
I need help developing a Hanoi algorithm which follows the same rules as the standard game, however the nodes that are transversed is different. In this graph Nodes represent a peg in the Hanoi algorithm. The algorithm must account for an unknown number of disks aka "n".
Given a Graph: G = {V,E}
Where V={Start,Node1,Node2,Node3,Node4,End}
Where E={(Start,Node1),(Node1,Node2),(Node2,Node3),(Node3,Node4),(Node4,End),(Node4,Node1)}
Note: The edges above are one directional. Example: You can move from node1 to node2 but you cannot move from node1 to node4
Using the elements of recursion, create an algorithm that solves the above Hanoi game using the graph above. What is the time complexity? The original Hanoi game has a complexity of: (2^n)-1
You can just move the whole stack from Start to 1 to 4 to End in the usual way, using $3(2^n-1)$ steps, so that is an upper bound. Even without nodes 2 and 3 you have additional freedom. You can move the whole stack to node 1 $(2^n-1$ moves), then move all but the last back to start $(2^{n-1}-1$ moves), then move the bottom all the way ($2$ moves). This leads to a recursion $T(n+1)=(2^{n+1}-1)+(2^n-1)+2+T(n)$, but that is no better. Another approach is to move $m$ disks to node $2$ using $2(2^m-1)$ moves, then move the remaining to 1,4,End using $3(2^{n-m}-1)$ moves, then move the $m$ disks to end using $3(2^m-1)$ moves. This is a total of $5(2^m-1)+3(2^{n-m}-1)$ moves. We want $5 \cdot 2^m \approx 3\cdot 2^{n-m}$ or $m+\log_2 5\approx (n-m)+\log_2 3, m \approx \frac 12(n+ \log_2 3-\log_2 5)$. Ignoring the two logs, we get $8(2^{\frac n2}-1)$ total moves. I don't know if there is a better strategy.