Hanoi Tower
最近学习到了一个很有趣的problem. 汉诺塔。
我认真的想了好几天，终于在今天找IT给我set up machine等着没事干的时候大概想通了。哈哈哈。
解决这个问题的方法让我想到了binary tree traverse 里面的in order的遍历，汉诺塔的solution之一的 recursive 的方式跟二叉树in order就是异曲同工，而且in human mind, 汉诺塔should make more sense to understand compared to binary tree.
在网上看到了一个印度小男孩对汉诺塔的分析，果然是tree.
Basically 解决汉诺塔的问题就是一个搬家公司应该怎么搬家的问题，from mission completed to start, which is from bottom to top.
Let's define Hanoi move function as:
HanoiMove(int leftToSit, int from - 0 , int to - 1, int rest - 2)
and we have n pieces in total waiting for the move
In theory, to approach the last step nth of move, we just need finish move rest of Hanoi pieces (n-1 in total) from start to rest pile,(简单说来就是，清空路障，直捣虎穴。）and then it should be able to move the last piece from start to To pile.
so we just do
1) HanoiMove(n-1, from, res, to) ---->>> left
as we planned in theory, we move
the nth piece move(from, to)
after this move, we have n-1 pieces sit in the rest pile, and our problem is to simplify to move n-1 pieces from res pile to To pile and using From pile as a mid layer.
2) HanoiMove(n-1, res, to, from) ---->>> right
Thinking about what's the current state of Hanoi now.
currently, our Hanoi state is n-1 pieces sitting on pile - 2 and we want to move it to pile - 1
3) HanoiMove(n-2, res, from, to) ---->>> right -> left
and then, we could have n-1th piece moving to Target pile
the n-1th move(res, to)
then our target switch to 4) HanoiMove(n-2, from, to, res) ---->>> right -> right
认真分析一下不难看出，以上1， 2， 3， 4的function call两两一组，1/2, 3/4就像遍历binary tree 的left/right一样, 而中间的Move 就是 inorder visit。
汉诺塔的iterative solution
汉诺塔的变形题
Find the minimum number of operations subject to the constraint that each operation must involve P3.
Find the minimum number of operations subject to the constraint that each operation must be from P1 to P2, P2 to P3, or P3 to P1.
Find the minimum number of operations subject to the constraint that a ring can never be transferred directly from P1 to P2 (transfers from P2 to P1 are allowed)
我认真的想了好几天，终于在今天找IT给我set up machine等着没事干的时候大概想通了。哈哈哈。
解决这个问题的方法让我想到了binary tree traverse 里面的in order的遍历，汉诺塔的solution之一的 recursive 的方式跟二叉树in order就是异曲同工，而且in human mind, 汉诺塔should make more sense to understand compared to binary tree.
在网上看到了一个印度小男孩对汉诺塔的分析，果然是tree.
Basically 解决汉诺塔的问题就是一个搬家公司应该怎么搬家的问题，from mission completed to start, which is from bottom to top.
Let's define Hanoi move function as:
HanoiMove(int leftToSit, int from - 0 , int to - 1, int rest - 2)
and we have n pieces in total waiting for the move
In theory, to approach the last step nth of move, we just need finish move rest of Hanoi pieces (n-1 in total) from start to rest pile,(简单说来就是，清空路障，直捣虎穴。）and then it should be able to move the last piece from start to To pile.
so we just do
1) HanoiMove(n-1, from, res, to) ---->>> left
as we planned in theory, we move
the nth piece move(from, to)
after this move, we have n-1 pieces sit in the rest pile, and our problem is to simplify to move n-1 pieces from res pile to To pile and using From pile as a mid layer.
2) HanoiMove(n-1, res, to, from) ---->>> right
Thinking about what's the current state of Hanoi now.
currently, our Hanoi state is n-1 pieces sitting on pile - 2 and we want to move it to pile - 1
3) HanoiMove(n-2, res, from, to) ---->>> right -> left
and then, we could have n-1th piece moving to Target pile
the n-1th move(res, to)
then our target switch to 4) HanoiMove(n-2, from, to, res) ---->>> right -> right
认真分析一下不难看出，以上1， 2， 3， 4的function call两两一组，1/2, 3/4就像遍历binary tree 的left/right一样, 而中间的Move 就是 inorder visit。
汉诺塔的iterative solution
汉诺塔的变形题
Find the minimum number of operations subject to the constraint that each operation must involve P3.
Find the minimum number of operations subject to the constraint that each operation must be from P1 to P2, P2 to P3, or P3 to P1.
Find the minimum number of operations subject to the constraint that a ring can never be transferred directly from P1 to P2 (transfers from P2 to P1 are allowed)
Comments
Post a Comment