带 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[]) { ... }

我知道 Frame-Stewart 算法，它很可能是最优的，但不是最优的经过验证，它会为您提供移动次数。然而，我对严格递归解决方案感兴趣，该解决方案遵循 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]

I.e.用 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 的启发式就是下限（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 的步骤注释如下：

• 按照惯例，当调用 hanoi 时，目标被定义（不失一般性）：将磁盘从第一个钉转移到第二个钉，使用所有剩余的钉进行临时处理。贮存。我们在递归时使用此约定来定义分治子问题的源、目标和允许的存储。
• 因此，源挂钩是 p1，目标挂钩是 p2。所有剩余的钉子都可以作为临时存储，用于解决顶级河内问题。
• 步骤 1，“对于某些 k，1 <= k < n，将前 k 个磁盘转移到单个其他挂钩”：我们选择 p3 作为“单个其他挂钩”。
• 因此，“不干扰现在包含前 k 个磁盘的挂钩”（步骤 2）意味着使用除 p3 之外的所有挂钩进行递归。即p1，p2，以及p3之外的其余部分。
• “将前 k 个盘转移到目标桩”（步骤 3）意味着从“其他桩”（p3）转移到 p2。

这有道理吗？

Answer 2

要解决河内塔问题，您所需要做的就是：

Frame Stewart 算法实际上并没有那么复杂。本质上，您必须将一定数量的磁盘（例如一半）移动到某个钉子上：将这些磁盘视为它们自己的独立塔。为 1 或 2 个磁盘定义解决方案很容易，将前半部分移动到其目的地，将后半部分移动到它需要结束的位置。

如果你想让它更容易编写，你可以不断地对其进行分段（唯一的特殊情况变成1），但如果没有大量的钉子，它就行不通。

此外，如果k >= 3，您可以像河内的 3 个钉塔一样解决它，只需忽略其余的钉子，尽管这不是最佳的。

Answer 3

欣泽、拉尔夫. 功能性珍珠：La Tour D'Hanoi，http://www.comlab.ox.ac.uk/ralf.hinze/publications/ICFP09.pdf

这颗珍珠旨在展示
全麦和投射的想法
使用河内塔进行编程
拼图作为一个运行示例。这
拼图有它自己的美，我们
希望一路曝光。

Answer 4

Facebook k-peg N 河内圆盘塔可以通过 BFS 算法求解。如需解决方案，请访问 http://www. woodor.com/InterviewMitra/41/facebook-k-peg-of-tower-of-hanoi-solution

Answer 5

河内塔谜题由法国数学家爱德华·卢卡斯（Edouard Lucas）于 1883 年以笔名 N. Lucas de Siam 向西方世界出版。游戏附带的“传说”称，在佛希皇帝统治时期，贝拿勒斯有一座带有圆顶的印度寺庙，标志着世界的中心（喀什维什瓦纳特）。在圆顶内，（婆罗门）祭司在 3 个钻石针尖（磨损的柱子）之间移动金色圆盘，这些圆盘高一肘，粗如蜜蜂的身体。上帝（梵天）在创造时将 64 个金盘放在一根针上。 （圆盘按照梵天不变的法则移动，将它们从一个钉子转移到另一个钉子上）据说，当他们完成任务时，宇宙就会终结。不同地点的传说有所不同，但大体上是一致的。
梵天制定的‘法则’是这样的：
1) 一次只能移动 1 个光盘
2) 较小的光盘上不能放置任何光盘
3) 只有顶部的圆盘可以被移除，然后放置在另一个钉子及其圆盘的顶部
当整堆圆盘被移动到另一个钉子上时，游戏结束。人们很快发现存在 3 钉解决方案，但没有解决 4+ 钉解决方案。
1939年，美国数学月刊举办了一场求解m peg和n圆盘的竞赛。两年后，JS Frame 和 BM Stewart 发布了两个独立的（但后来被证明是相同的）算法。两者都尚未被证明是正确的，尽管人们普遍认为它们是正确的。目前还没有关于适当解决方案的进一步进展。
*****这仅适用于 3 个钉问题*****
n 个圆盘塔的最小移动次数很快被证明为 2n−1，简单的递归解决方案如下：标记三个钉子开始、目标和临时。要通过临时桩将 n 个桩从起始桩移动到目标桩：
对于n> 1、
(i) 通过目标递归地将前 n−1 个磁盘从 start 移动到 temp 。
(ii) 将第 n 个圆盘从起点移动到终点。
(iii) 通过 start 递归地将 n−1 个圆盘从 temp 移动到目标。
该解需要 2n−1 次移动：
(1) 如果 n = 1，则 f(n) = 1 = 2n−1
(2)如果n＞； 1、f(n) = 2 * (2n−1−1)+1 = 2n−2+1 = 2n−1
解决这个问题的简单方法... 1,3,7,15,31是前几n个圆盘的解决方案。递归地类似于 nk=2nk-1+1。由此我们可以推出 n=2n-1。我把归纳法证明留给你了。
******基本 Frame/Stewart 算法*****
对于 m 个钉子和 n 个圆盘，选择 l 使得 0 ≤ l < n（而 l 是一个整数，可以最小化以下设置中的步骤）...
• 将顶部l 圆盘从起始桩移至中间桩；这可以通过 Hk(l) 次移动来完成（因为底部的 n−l 盘根本不干扰移动）。
• 使用Hk−1(n−l) 次移动将底部的n − l 个圆盘从起始桩移动到目标桩。 （由于一个钉子被一塔较小的磁盘占据，因此在此阶段无法使用它。）
• 在Hk(l) 步中将原来的l 个圆盘从中间桩移动到目标桩。
所以本质上是 Hk(n)= 2Hk(l) + Hk-1(n-1) -----> l 最小化
*****简单易行！！不是！*****
验证它是否适用于我们的 3 挂钩解决方案应该很容易。
使用k=2；我们设置H2(0)=0，H2(1)=1，并且H2(n>1)=∞。
对于k=3，我们可以设置l=n-1。 （它导致我们的 H2(n-1) 变得有限）这将允许我们写 H3(n)=2H3(n-1)+H2(1) 等于 2n−1。这有点文字游戏，但确实有效。
*****稍微不同的描述有助于澄清*****
Frame-Stewart 算法为四个（甚至更多）钉子提供了可能的最佳解决方案，描述如下：
定义 H(n,m) 为使用 m 个钉子转移 n 个圆盘所需的最小移动次数
该算法可以递归地描述：
1. 对于某些 l, 1

`Option VBASupport 1
Option Explicit
Dim n as double
dim m as double
dim l as double
dim rx as double
dim rxtra as double
dim r as double
dim x as double
dim s1 as double
dim s2 as double
dim i as integer
dim a ()
dim b ()
dim c ()
dim d ()
dim aa as double
dim bb as double
dim cc as double
dim dd as double
dim total as double

Sub Hanoi
on error goto errorhandler

m=inputbox ("m# pegs=??")
n=inputbox ("n# discs=??")
x=-1
l=m-1
rx=1
s1=0
s2=0
aa=0

while n>rx
        x=x+1
        r=(l+x)/(x+1)
        rx=r*rx
wend
rx=1
for i=0 to x-1
        r=(l+i)/(i+1)
        rx=r*rx
        redim a (-1 to x)
        redim b (-1 to x)
        redim c (-1 to x)
        redim d (-1 to x)
            a(i)=rx
            b(i)=i
            bb=b(i)
            c(i)=rx-aa
            aa=a(i)
            cc=c(i)
            d(i)=cc*2^bb
            dd=d(i)
            s1=s1+dd
next

rxtra=n-aa
s2=rxtra*2^(bb+1)
total = 2*(s1+s2)-1
msgbox total

exit sub
errorhandler: msgbox "dang it!!"
'1, 3, 5, 9, 13, 17, 25, 33 first 8 answers for 4 peg
'16=161,25=577,32=1281,64=18433
End Sub`

披露：这些来源用于确认答案和问题的一些历史记录。很难给出确切的信用来源，因为使用了多个站点来验证......所以它们是历史许多部分的所有来源。

Answer 6

我愿意贡献我认为的 Frame-Stewart 算法中的最佳 k。该算法本身并未针对无法解决汉诺塔的情况进行定义。

frameStewart :: Integer -> Integer -> Integer
frameStewart d c
  | c <= 2    = error "must have more than two pegs"
  | c == 3    = 2^d-1
  | d <  c    = 2*d-1
  | otherwise = frameStewart k c + frameStewart (d-k) (c-1) + frameStewart k c
    where
      k = solve $ div (4*d-2*c) c
        where
          solve a
            | a*2*d-a*a <= d^2-2*a = a
            | otherwise  = solve (a-1)

---

维基百科页面显示n 磁盘减去2*n + 1的平方根，在特殊括号内找到最接近的整数，+1等于k。我发现通过考虑 d = 4（d 代表磁盘）和 k = 2 来摆脱这些括号很有用，并操纵公式直到我得出以下不等式：存在于代码中。仅此一项就可以解决 4 个钉子的问题。

最后一步是找出用哪个值来解决这个不等式，并将其视为 4*d-2*c（c 代表钉子或我的语言中的“cavilhas”）除以数字钉子c。我认为它的结果与 Ben Houston 研究中的 4 个钉子的表格相匹配，这些钉子存在 此处。

但是，这不会为您提供移动列表，而只会提供最少的移动数量。

Answer 7

http://tristan -interview.blogspot.com/2012/02/n-disks-and-k-pegs-extension-problem-of.html