【数据结构与算法之回溯法】回溯法的基本思想
【数据结构与算法之回溯法】回溯法的基本思想
文章目录
- 【数据结构与算法之回溯法】回溯法的基本思想
回溯法的适用范围很广，它可以系统地搜索一个问题的解空间树，并得到该问题的全部解。
回溯法 → “通用解题算法”美誉。
【基本思想】在包含问题所有解的解空间树中，按照深搜的策略从根节点出发搜索解空间树，当搜素到某个节点时，判断该节点是否包含问题的解，如果包含问题的 解(满足约束条件)，就从该节点出发继续进行深搜，如果不包含问题的解(不满足约束条件)，则说明以该节点为根节点的子解空间树中也一定不包含该问题的解，所以就跳过对该节点以及其子树的系统搜索，向解空间的上一层“回溯”。这个过程就叫做解空间树的“剪枝”。
当搜索完整棵解空间树后( 回溯到了整棵树的根节点)，就可以得到问题的全部解。如果只希望得到问题的某个解，那么在搜索解空间树时只需要找到问题的一个解后就可以结束。
【“四皇后”问题】
四皇后和八皇后本质上是一样的，只是四皇后规模更小。
问题描述：
有一个4 x 4 的棋盘，要在上面摆放4 颗皇后棋子，要求任意一颗皇后棋子所在位置的水平方向、竖直方向、以及对角线方向(45° 斜线)上都不能出现其他皇后棋子。
问这样一共可以有多少种摆法？
简单绘制一棵解空间树如下：
按照这种办法画下去，最后会得到 4 4 = 256 4^4 = 256 44=256 个叶子结点，对应着256 种四皇后的放法。而且这个解空间树是一棵满四叉树。当然这256 种放法中绝大部分都不满足我们问题的要求。
我们要做的是通过深度优先搜索这棵解空间树，最终找出满足要求的四皇后放法。
从根节点出发，比如说来到了下面的这样一个位置
我们不能等到生成叶子节点(就是四个皇后都摆完了)之后 再去判断棋盘局面是否满足要求，而是在生成棋盘局面的过程中就预先判断，如果当前的局面不满足要求，而后续的局面都是基于这个局面生成的，则提前终止对一路的搜索。
相比穷举，使用回溯法深度优先搜索解空间树可以大大减少搜索的步数，从而更快的找到问题的答案。
柔光的暖阳◎
àì夳堔傛蜴生んèń
野性酷女
骑猪看日落
Bertha 。
还没有评论，来说两句吧...