artificial-intelligence - 通过使用良好的状态空间和搜索树来解决河内塔

Question

我想通过使用良好的“状态空间”来解决“河内塔”问题。使用适当的状态空间是一些 AI 技术建议的一种方式。拥有良好的状态空间后，我希望能够构建搜索树，然后使用诸如“DFS”（深度优先搜索）之类的策略来找到解决方案。

我的问题是，我只是不知道如何开发一个好的状态空间，然后用它来构建一个搜索树。谁能描述如何为河内塔问题创建状态空间？然后告诉我如何为此构建搜索树？

Answer 1

我建议以下状态空间：

假设你有 n 块砖和 3 座塔，用 0、1、2 表示。用三进制数表示当前状态，例如（在 n=9 的情况下）：

987654321
001102020 (current state)

这意味着砖块 9,8,5,3 和 1 在 0:th 塔中。第 1 塔中的 7 号和 6 号砖以及第 2 号塔中的 4 号和 2 号砖。

这会给你一个大小为 3^n 的状态空间，它不是太大。

（这只是部分答案。但是每个状态字符串都会对应一个合法状态。也就是说，

1. 在每座塔中，砖块的大小将从下到上递减，

2. 两个不同的塔中不会出现砖块。

因此，我认为建议的状态空间是最小的。)

Answer 2

我认为最优解 (2^n - 1)

状态空间由 3^n 给出

这是另一个带有树形图的链接，您可以使用它来计算状态（我认为这与您关于状态空间的问题有关）

Answer 3

2^(n+1)-1 is not correct for the towers of hanoi problem. If you look at figure 2 here, then when applying n=3 to 2^(n+1)-1 gives 2^4 - 1 or 15 states. But figure 2 shows 27 states.

Answer 4

我认为您可以使用分而治之的方法轻松解决此问题：假设您必须使用一些辅助挂钩来解决将 n 个圆盘从 src 移动到 dest 的问题。U 可以递归地定义一个函数：

towers(n,src,dest,peg)
{
    if(n==1) //BASE CASE
        move a disc from src to dest. 

   else  //INDUCTIVE CASE
   {
    towers(n-1,src,aux,dest);
    towers(1,src,dest,aux);
    towers(n-1,aux,dest,src)
   }
}

复杂度分析：T(n)=2T(n-1)+1

这导致解 T(n)=O(2^n) [指数顺序]。

也许你也可以使用某种记忆来存储已经解决的子问题的解决方案，以进一步提高时间复杂度，但这是为了增加空间复杂度的使用而做出的权衡。