【数据结构与算法之回溯法】回溯法的基本思想

末蓝、 2024-03-25 20:19 98阅读 0赞

#### 【数据结构与算法之回溯法】回溯法的基本思想 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之回溯法】回溯法的基本思想

回溯法的适用范围很广，它可以系统地搜索一个问题的解空间树，并得到该问题的全部解。

回溯法 → “通用解题算法”美誉。

【基本思想】在包含问题所有解的解空间树中，按照深搜的策略从根节点出发搜索解空间树，当搜素到某个节点时，判断该节点是否包含问题的解，如果包含问题的 解(满足约束条件)，就从该节点出发继续进行深搜，如果不包含问题的解(不满足约束条件)，则说明以该节点为根节点的子解空间树中也一定不包含该问题的解，所以就跳过对该节点以及其子树的系统搜索，向解空间的上一层“回溯”。这个过程就叫做解空间树的“剪枝”。

当搜索完整棵解空间树后( 回溯到了整棵树的根节点)，就可以得到问题的全部解。如果只希望得到问题的某个解，那么在搜索解空间树时只需要找到问题的一个解后就可以结束。

【“四皇后”问题】

四皇后和八皇后本质上是一样的，只是四皇后规模更小。

问题描述：

有一个4 x 4 的棋盘，要在上面摆放4 颗皇后棋子，要求任意一颗皇后棋子所在位置的水平方向、竖直方向、以及对角线方向(45° 斜线)上都不能出现其他皇后棋子。

![在这里插入图片描述][95c22cd5cd9e4623821d77c7fc132a8c.png_pic_center]

问这样一共可以有多少种摆法？

简单绘制一棵解空间树如下：

![在这里插入图片描述][19dc73d1346940389ec6f052974eee67.png_pic_center]

按照这种办法画下去，最后会得到  4 4 = 256 4^4 = 256 44=256 个叶子结点，对应着256 种四皇后的放法。而且这个解空间树是一棵满四叉树。当然这256 种放法中绝大部分都不满足我们问题的要求。

我们要做的是通过深度优先搜索这棵解空间树，最终找出满足要求的四皇后放法。

从根节点出发，比如说来到了下面的这样一个位置

![在这里插入图片描述][79448d0e4c80439cae2840262d347e12.png_pic_center]

我们不能等到生成叶子节点(就是四个皇后都摆完了)之后 再去判断棋盘局面是否满足要求，而是在生成棋盘局面的过程中就预先判断，如果当前的局面不满足要求，而后续的局面都是基于这个局面生成的，则提前终止对一路的搜索。

相比穷举，使用回溯法深度优先搜索解空间树可以大大减少搜索的步数，从而更快的找到问题的答案。

[95c22cd5cd9e4623821d77c7fc132a8c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c0c76baf913e47ef9fa9d64d29c84445.png
[19dc73d1346940389ec6f052974eee67.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7f07ad3aceb048fd9f8e221f1b38bda2.png
[79448d0e4c80439cae2840262d347e12.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/f63a54c1c1344575bbb6d90c6152cb0f.png