天才一秒记住【久久文学】地址：https://www.jjwxx.com
·最初，我们只能选择移动最小的金环，只有将它移动到中间或者最右边的柱子上。
所以对应第一步，我们只有两种移动可能，以及两种不同的新状态。
·如果我们选择将最小的金环移动到中间柱子（初始状态左下方箭头对应的状态），那么我们随后可以执行三种操作：将最小的金环移动到最左侧或者最右侧的柱子，或者将第二个金环移动到最右侧柱子（不能将第二个金环移动到中间柱子，因为它会位于最小金环的上方，这就违背了移动规则）。
·以此类推。
图4 汉诺塔问题搜索树的一小部分片段
因为我们逐级逐级地在生成搜索树，这就意味着我们考虑到了所有的移动可能性，因此，如果这个问题确定是有解决方案的，我们就可以确保使用搜索的方法最终能够找到它（“最终”
这个词在句中是至关重要的，至于为什么，很快就会揭晓）。
那么，解决汉诺塔问题需要移动的最少次数是多少呢？也就是说，从初始状态到目标状态，最少需要移动多少次？对于三个金环而言，答案很简单，是7次。
你不可能找到少于7次的解决方案了。
当然，也有很多方案可以用超过七步的方式解决问题（实际上是有无穷多方案），但它们不是最优的，因为我们想用最少的步骤、在最短的时间内解决问题。
现在，考虑到我们所描述的搜索过程是详细无遗漏的——考虑到了每一步搜索树的所有可能性——搜索技术不光能保证寻找到解决方案，也能保证寻找到最优解决方案。
这就意味着，穷举搜索的方式不仅能保证在问题可解的时候寻找到问题的解，还能保证寻找到问题的最优解。
另外，作为计算机的算法，穷举搜索非常简单——编写一个程序来实现它非常容易。
不过，哪怕我们只是粗略研究图4所示的片段都能够看出来，如刚才所描述的那样，采用穷举搜索的方式来解决问题是个相当愚蠢的过程。
比如，仔细看看搜索树最左边的分支，仅仅移动两步以后，问题又返回到了初始状态，这是在无谓地浪费精力。
如果是你来研究解决汉诺塔问题，可能会在寻找解决方案的时候犯一两次类似的错误，不过你会很快发现问题所在，并且学会避免做一些徒劳的移动。
然而，一台简单执行穷举搜索的计算机却无法做到：它只能穷举出所有移动下的所有新状态，哪怕某些穷举步骤就是在浪费时间，它也会走回头路，回到已经被确认过失败的状态。
除了太多重复和低效率以外，穷举搜索还有一个根本的问题。
如果你做过一些实验，会发现在大部分状态下，汉诺塔问题都有三种移动的可能性，即分支因子为3。
不同的问题对应着不同的分支因子。
比如，围棋的分支因子为250，这就意味着在游戏给定的任意状态下，每个玩家约有250种落子的可能性，当然，这只是平均值。
所以，我们来看看搜索树随着分支因子能增长到多大——对确定了分支因子数的搜索树，在不同层级有多少种状态。
以围棋为例[24]：
·搜索树的第一级有250种状态，因为在游戏棋盘的初始状态下，可以有250种新出现的状态。
·第二级搜索树有250×250=62500种状态，因为我们必须考虑到250种落子选择后，每一种状态都有250种可能出现的新状态。
·第三级搜索树有62500×250，大约有1560多万种状态。
·以此类推，第四级搜索树就会有大约39亿种状态。
本章未完，请点击下一章继续阅读！若浏览器显示没有新章节了，请尝试点击右上角↗️或右下角↘️的菜单，退出阅读模式即可，谢谢！