河内的塔与K钉

Question

在河内塔问题是递归的一个经典问题.在其中一个上有3个带磁盘的挂钩,您必须按照给定的规则将所有磁盘从一个挂钩移动到另一个挂钩.您还必须使用最少的移动次数执行此操作.

这是一个解决问题的递归算法:

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个以上是免费的.

我有这个问题的递归算法:

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[]将保存每个堆栈的标签,因此该函数看起来像这样:

void HanoiK(int nDisks, int kStacks, char labels[]) { ... }

我知道帧斯图尔特算法,这是最有可能的优化,但没有得到证实,和它给你的号码的移动.但是,我对一个严格的递归解决方案感兴趣,该解决方案遵循3和4个挂钩的递归解决方案的模式,这意味着它打印实际的移动.

至少对我来说,维基百科上提出的Frame-Stewart算法的伪代码是相当抽象的,我没有成功地将它转换为打印动作的代码.我会接受它的参考实现(随机k),甚至更详细的伪代码.

我试图提出某种算法来相应地置换标签数组,但我没有运气让它起作用.任何建议表示赞赏.

更新:

这似乎在功能语言中更容易解决.这是基于LarsH的Haskell解决方案的F#实现:

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个钉子视为边缘情况:

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]

Answer 1

这是Haskell中的一个实现(更新:通过在r = 3时使k = n-1来处理3-peg情况):

-- 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个钉子,例如

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等.

我对Haskell很陌生,所以我必须承认,我为此感到自豪.但我可能有愚蠢的错误,所以欢迎反馈.

从代码中可以看出,k的启发式只是floor(n/2).我没有试过优化k,虽然n/2似乎是一个很好的猜测.

我已经验证了4个磁盘和4个挂钩答案的正确性.对于我来说,在没有编写模拟器的情况下进行更多验证已经太晚了.(@ _ @)以下是一些结果:

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的移动序列.为了确定移动,我们注释FS的步骤如下:

• 传统上,当呼叫河内时,使用所有剩余的钉用于临时存储,将磁盘从第一钉固定到第二钉,从而定义(不失一般性)目标.我们在递归时使用此约定来定义分割和征服的子问题的源,目标和允许的存储.
• 因此,源挂钩是p1,目标挂钩是p2.所有剩余的钉子都可以作为临时存储,用于顶级河内问题.
• 步骤1,"对于某些k,1 <= k <n,将前k个磁盘转移到另一个挂钩":我们选择p3作为"单个其他挂钩".
• 因此,"在不打扰现在包含前k个磁盘的挂钩"的情况下(步骤2)意味着使用除p3之外的所有挂钩来递归.即p1,p2,其余的超出p3.
• "将前k个磁盘转移到目标挂钩"(步骤3)意味着从"其他挂钩"(p3)转移到p2.

那有意义吗？