利用良好的状态空间和搜索树解决河内塔问题

Question

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

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

Answer 1

我建议使用以下状态空间：

假设您有n块砖和3个塔，用0,1,2表示。用n个三进制数表示当前状态，例如(在案例n=9中)：

987654321
001102020 (current state)

这意味着砖块9,8,5,3和1在0:th塔中。第一个塔的砖块7和6，2:nd塔的砖块4和2。

这将为您提供一个大小为3^n的状态空间，该空间并不太大。

(这只是部分答案。但是每个状态字符串都将对应于一个合法的状态。也就是说,

1. 在每个塔中，砖块的大小会从下到上逐渐减小，
2. 不会出现在两个不同的塔中。

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

Answer 2

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

状态空间由3^n给出

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

Answer 3

2^(n+1)-1不适用于河内塔问题。如果您查看图2的here，那么当将n=3应用于2^(n+1)-1时，会得到2^4 -1或15个状态。但figure 2显示了27个州。