河内用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[]) { ... }

我知道帧斯图尔特算法，这是最有可能的优化，但没有得到证实，和它给你的举动在号。不过，我感兴趣的严格递归的解决方案，遵循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.

至少对我来说，psented维基百科帧斯图尔特算法$ P $的伪code是比较抽象的，而我还没有成功地将其翻译成一个打印的招式code。我会接受一个参考实现的（随机 K ），或更详细的伪code。

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.

我试图想出某种算法，即相应permutes标签阵列，但我已经没有运气得到它的工作。任何的建议是AP preciated。

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的哈斯克尔解决方案的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 （更新实现：照顾了3-PEG情况下，只要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中并输入

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)]

即。从PEG 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.

我是pretty的新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.

正如你可以从code看到的，启发式的k是简单的地板（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)]

这是否澄清算法？

Does this clarify the algorithm?

真正的关键一环是

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)

在这里我们串联动作让步骤1，2序列，和3帧斯图尔特算法。为了确定在移动，我们标注FS的步骤如下：

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:

• 通常，当河内被调用时，目标被定义（不失一般性），为传送盘从第一钉住第二销钉，使用所有剩余钉用于临时存储。递归时，定义源，目标，并允许存储的划分和被征服的子问题，我们使用这种约定。
• 因此源PEG为P1，而目标PEG为p2。所有剩余的桩钉可作为临时存储，对于顶层河内问题。
• 第1步，​​对于一些K，1＆LT; = K＆n种，转移前k个磁盘的单一盯住其他：我们选择P3作为单一钉住其他
• 在这样，而不会干扰当前包含前k个磁盘上的挂钩（步骤2），是指使用除P3所有钉递归。即P1，P2，和P3以外的其余部分。
• 转移相关的前k磁盘到目的地栓（步骤3）指从其他栓（P3）传送到P2。

这是否有道理？

这篇关于河内用K钉塔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！