河内塔与 K 钉 [英] Towers of Hanoi with K pegs
问题描述
河内塔问题是递归的经典问题.给你 3 个钉子，其中一个钉子上有圆盘，你必须按照给定的规则将所有圆盘从一个钉子移到另一个钉子上.您还必须以最少的移动次数做到这一点.
The Towers of Hanoi problem is a classic problem for recursion. You are given 3 pegs with disks on one of them, and you must move all the disks from one peg to another, by following the given rules. You must also do this with the minimum number of moves.
这是解决问题的递归算法:
Here's a recursive algorithm that solves the problem:
void Hanoi3(int nDisks, char source, char intermed, char dest)
{
if( nDisks > 0 )
{
Hanoi3(nDisks - 1, source, dest, intermed);
cout << source << " --> " << dest << endl;
Hanoi3(nDisks - 1, intermed, source, dest);
}
}
int main()
{
Hanoi3(3, 'A', 'B', 'C');
return 0;
}
现在，想象同样的问题，只有 4 个挂钩，所以我们添加另一个中间挂钩.当面临必须在任何一点选择哪个中间挂钩的问题时，我们会选择最左边的，以防超过 1 个是免费的.
Now, imagine the same problem, only with 4 pegs, so we add another intermediary peg. When faced with the problem of having to choose which intermediary peg to choose at any one point, we will choose the leftmost one, in case more than 1 is free.
对于这个问题，我有以下递归算法:
I have the following recursive algorithm for this problem:
void Hanoi4(int nDisks, char source, char intermed1, char intermed2, char dest)
{
if ( nDisks == 1 )
cout << source << " --> " << dest << endl;
else if ( nDisks == 2 )
{
cout << source << " --> " << intermed1 << endl;
cout << source << " --> " << dest << endl;
cout << intermed1 << " --> " << dest << endl;
}
else
{
Hanoi4(nDisks - 2, source, intermed2, dest, intermed1);
cout << source << " --> " << intermed2 << endl;
cout << source << " --> " << dest << endl;
cout << intermed2 << " --> " << dest << endl;
Hanoi4(nDisks - 2, intermed1, source, intermed2, dest);
}
}
int main()
{
Hanoi4(3, 'A', 'B', 'C', 'D');
return 0;
}
现在，我的问题是如何将这种递归方法推广到 K 挂钩?递归函数将接收一个 char[] ，它会保存每个堆栈的标签，因此该函数看起来像这样:
Now, my question is how would I generalize this recursive approach to work for K pegs? The recursive function would receive a char[] which would hold the labels of each stack, so the function would look something like this:
void HanoiK(int nDisks, int kStacks, char labels[]) { ... }
我知道 Frame-Stewart 算法，它很可能是最优的，但未经证实，它为您提供移动次数.但是，我对遵循 3 和 4 个钉子的递归解决方案模式的严格递归解决方案感兴趣，这意味着它会打印实际移动.
I know about the Frame-Stewart algorithm, which is most likely optimal but not proven, and which gives you the number of moves. However, I am interested in a strictly recursive solution that follows the pattern of the recursive solutions for 3 and 4 pegs, meaning it prints the actual moves.
至少对我来说，维基百科上提供的 Frame-Stewart 算法的伪代码相当抽象，我还没有成功地将它翻译成打印动作的代码.我会接受它的参考实现(对于随机 k)，或者更详细的伪代码.
For me at least, the pseudocode of the Frame-Stewart algorithm presented on Wikipedia is rather abstract, and I haven't been successful at translating it into code that prints the moves. I would accept a reference implementation of that (for random k), or even more detailed pseudocode.
我试图想出某种算法来相应地排列标签数组，但我没有运气让它工作.任何建议表示赞赏.
I tried to come up with some sort of algorithm that permutes the labels array accordingly, but I've had no luck getting it to work. Any suggestions are appreciated.
更新:
用函数式语言解决这个问题似乎要容易得多.这是基于 LarsH 的 Haskell 解决方案的 F# 实现:
This seems to be a lot easier to solve in a functional language. Here's an F# implementation based on LarsH's Haskell solution:
let rec HanoiK n pegs =
if n > 0 then
match pegs with
| p1::p2::rest when rest.IsEmpty
-> printfn "%A --> %A" p1 p2
| p1::p2::p3::rest when rest.IsEmpty
-> HanoiK (n-1) (p1::p3::p2::rest)
printfn "%A --> %A" p1 p2
HanoiK (n-1) (p3::p2::p1::rest)
| p1::p2::p3::rest when not rest.IsEmpty
-> let k = int(n / 2)
HanoiK k (p1::p3::p2::rest)
HanoiK (n-k) (p1::p2::rest)
HanoiK k (p3::p2::p1::rest)
let _ =
HanoiK 6 [1; 2; 3; 4; 5; 6]
并且不将 3 个钉视为边缘情况:
And without treating 3 pegs as an edge case:
let rec HanoiK n pegs =
if n > 0 then
match pegs with
| p1::p2::rest when rest.IsEmpty
-> printfn "%A --> %A" p1 p2
| p1::p2::p3::rest
-> let k = if rest.IsEmpty then n - 1 else int(n / 2)
HanoiK k (p1::p3::p2::rest)
HanoiK (n-k) (p1::p2::rest)
HanoiK k (p3::p2::p1::rest)
请注意，这不会处理没有解决方案的退化情况，例如 HanoiK 2 [1;2]
Note that this does not handle degenerate cases for which there is no solution, such as HanoiK 2 [1; 2]
推荐答案
这里是 Haskell 中的一个实现 (更新: 通过使 k = n-1 当 r=3):
Here is an implementation in Haskell (update: took care of 3-peg case by making k = n-1 when r=3):
-- hanoi for n disks and r pegs [p1, p2, ..., pr]
hanoiR :: Int -> [a] -> [(a, a)]
-- zero disks: no moves needed.
hanoiR 0 _ = []
-- one disk: one move and two pegs needed.
hanoiR 1 (p1 : p2 : rest) = [(p1, p2)] -- only needed for smart-alecks?
{-
-- n disks and 3 pegs -- unneeded; covered by (null rest) below.
hanoiR n [p1, p2, p3] =
hanoiR (n - 1) [p1, p3, p2] ++
[(p1, p2)] ++
hanoiR (n - 1) [p3, p2, p1]
-}
-- n disks and r > 3 pegs: use Frame-Stewart algorithm
hanoiR n (p1 : p2 : p3 : rest) =
hanoiR k (p1 : p3 : p2 : rest) ++
hanoiR (n - k) (p1 : p2 : rest) ++
hanoiR k (p3 : p2 : p1 : rest)
where k
| null rest = n - 1
| otherwise = n `quot` 2
因此在 GHCi 中加载并输入
So load this in GHCi and enter
hanoiR 4 [1, 2, 3, 4]
即用 4 个圆盘和 4 个钉子运行河内塔.您可以随意命名 4 个挂钩，例如
I.e. run the Towers of Hanoi with 4 disks and 4 pegs. You can name the 4 pegs whatever you want, e.g.
hanoiR 4 ['a', 'b', 'c', 'd']
输出:
[(1,2),(1,3),(2,3),(1,4),(1,2),(4,2),(3,1),(3,2),(1,2)]
即将顶部磁盘从挂钩 1 移动到挂钩 2，然后将顶部磁盘从挂钩 1 移动到挂钩 3，依此类推
I.e. move the top disk from peg 1 to peg 2, then the top disk from peg 1 to peg 3, etc.
我对 Haskell 还很陌生，所以我必须承认我很自豪它的工作原理.但我可能会犯一些愚蠢的错误，因此欢迎提供反馈.
I'm pretty new to Haskell so I must admit I'm proud that this works. But I may have silly mistakes so feedback is welcome.
从代码中可以看出，k 的启发式只是 floor(n/2).我没有尝试优化 k，尽管 n/2 似乎是一个不错的猜测.
As you can see from the code, the heuristic for k is simply floor(n / 2). I haven't tried to optimize k, though n/2 seemed like a good guess.
我已经验证了 4 个磁盘和 4 个挂钩的答案的正确性.夜深了我再去验证，不写模拟器了.(@_@) 这里还有一些结果:
I've verified the correctness of the answer for 4 disks and 4 pegs. It's too late at night for me to verify more, without writing a simulator. (@_@) Here are a few more results:
ghci> hanoiR 6 [1, 2, 3, 4, 5]
[(1,2),(1,4),(1,3),(4,3),(2,3),(1,4),(1,5),(1,2),
(5,2),(4,2),(3,1),(3,4),(3,2),(4,2),(1,2)]
ghci> hanoiR 6 [1, 2, 3, 4]
[(1,2),(1,4),(1,3),(4,3),(2,3),(1,2),(1,4),(2,4),(1,2),
(4,1),(4,2),(1,2),(3,1),(3,4),(3,2),(4,2),(1,2)]
ghci> hanoiR 8 [1, 2, 3, 4, 5]
[(1,3),(1,2),(3,2),(1,4),(1,3),(4,3),(2,1),(2,3),(1,3),(1,2),
(1,4),(2,4),(1,5),(1,2),(5,2),(4,1),(4,2),(1,2),
(3,2),(3,1),(2,1),(3,4),(3,2),(4,2),(1,3),(1,2),(3,2)]
这是否阐明了算法?
真正重要的是
hanoiR k (p1 : (p3 : (p2 : rest))) ++ -- step 1; corresponds to T(k,r)
hanoiR (n-k) (p1 : (p2 : rest)) ++ -- step 2; corresponds to T(n-k, r-1)
hanoiR k (p3 : (p2 : (p1 : rest))) -- step 3; corresponds to T(k,r)
我们将 Frame-Stewart 算法的步骤 1、2 和 3 的移动序列连接起来.为了确定移动，我们将 F-S 的步骤注释如下:
where we concatenate the sequences of moves for steps 1, 2, and 3 of the Frame-Stewart algorithm. In order to determine the moves, we annotate F-S's steps as follows:
- 传统上，当调用 hanoi 时，目标被定义为(不失一般性)将磁盘从第一个挂钉转移到第二个挂钉，使用所有剩余的挂钉进行临时存储.我们在递归时使用此约定来定义分而治之的子问题的源、目标和允许的存储.
- 因此源挂钩是 p1，目标挂钩是 p2.所有剩余的桩都可用作临时存储，用于解决顶级河内问题.
- 第 1 步，对于某些 k，1 <= k
- 因此，在不干扰现在包含前 k 个磁盘的挂钩的情况下"(第 2 步)意味着使用除 p3 之外的所有挂钩进行递归.IE.p1、p2 以及 p3 之外的其余部分.
- 将前 k 个磁盘转移到目标挂钩"(步骤 3)意味着从另一个挂钩"(p3)转移到 p2.
有意义吗?
这篇关于河内塔与 K 钉的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
