从 DFS 到回溯法,再看 N 皇后问题
问题 回溯 DFS 皇后
2023-06-13 09:12:48 时间
这是我参与11月更文挑战的第7天,活动详情查看:2021最后一次更文挑战
上一篇 已经讲到了 DFS 一些基础的点,由于 DFS 太重要了,不得不再往前深挖一步!
DFS 是深度搜索,是暴力的,是一条道走到黑的,是一次性搜到底的!那么,搜到底发现没有路了,就得回退去找另外的路,再继续莽着搜!既然要回退,就必须保存走过每个点的所有信息,包括先后顺序;这个回退的过程就叫 回溯。
根据回溯思想,演进到回溯算法来解决寻找问题。看一下wiki对回溯法的解释:
回溯法采用 试错 的思想,它尝试分步的去解决一个问题。在分步解决问题的过程中,当它通过尝试发现,现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的答案。
简化理解:回溯算法 = 树的深度优先搜索 + 剪枝函数
- 什么是剪枝函数? 为了提高搜索效率,在搜索过程中使用约束函数,可以避免无谓地搜索那些已知不含答案状态的子树。如果是最优化问题,还可以使用限界函数剪去那些不可能含有最优解的子树。约束函数和限界函数目的相同,都是为了剪去不必要搜索的子树,减少问题求解所需实际生成的状态结点数,他们统称为剪枝函数。
OK,以上是概念介绍,下面来一道经典之经典之经典的回溯算法题:N皇后
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。 给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1:
输入:n = 4
输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释:如上图所示,4 皇后问题存在两个不同的解法。
示例 2:
输入: n = 1
输出: [["Q"]]
N 皇后问题很多时候作为例题出现在教科书中,可以当做理解回溯算法的例题进行学习;
以 4 皇后问题为例,递归树如下:
解题思路:
- 回溯算法的通用解题思路就是在递归之前做选择,在退出递归之前撤销选择;
- 通过恰当的方式将不符合条件的情况剪枝;
回溯三部曲:
- 递归函数参数;
- 递归终止条件;
- 单层搜索的逻辑;
回溯模板:
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
处理节点;
backtracking(路径,选择列表); // 递归
回溯,撤销处理结果
}
}
JavaScript 实现:
var solveNQueens = function(n) {
function isValid(row, col, chessBoard, n) {
// 检查列
for(let i = 0; i < row; i++) { // 这是一个剪枝
if(chessBoard[i][col] === 'Q') {
return false
}
}
// 检查 45度角是否有皇后
for(let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if(chessBoard[i][j] === 'Q') {
return false
}
}
// 检查 135度角是否有皇后
for(let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if(chessBoard[i][j] === 'Q') {
return false
}
}
return true
}
// 存放结果
function transformChessBoard(chessBoard) {
let chessBoardBack = []
chessBoard.forEach(row => {
let rowStr = ''
row.forEach(value => {
rowStr += value
})
chessBoardBack.push(rowStr)
})
return chessBoardBack
}
let result = []
// 回溯
function backtracing(row,chessBoard) {
if(row === n) { // 终止条件
result.push(transformChessBoard(chessBoard))
return
}
for(let col = 0; col < n; col++) {
if(isValid(row, col, chessBoard, n)) {
chessBoard[row][col] = 'Q' // 处理节点
backtracing(row + 1,chessBoard) // 递归
chessBoard[row][col] = '.' // 回溯,撤销处理结果
}
}
}
let chessBoard = new Array(n).fill([]).map(() => new Array(n).fill('.'))
backtracing(0,chessBoard)
return result
};
代码作者:carlsun-2,已验证通过;
回溯算法跟 DFS 深度搜索算法都很经典,需同步理解,对比、吸收;
我是掘进安东尼,公众号同名,日拱一卒、日掘一金,再会~
相关文章
- Pycharm和Anaconda的python版本问题
- 如何解决eclipse乱码问题?「建议收藏」
- ESP32-Drone四旋翼无人机代码编译发现的二个问题及解决方法
- N 皇后问题_用回溯法解N皇后问题
- 如何解决EasyNVR使用WebRTC协议无法播放的问题?
- 01背包问题回溯法_回溯法解决01背包问题时间复杂度
- Avada kedavra_用回溯法解N皇后问题
- 回溯法之n皇后问题总结_用回溯法求解n皇后问题的思路
- 算法之美:0-1背包问题(动态规划法,回溯法,贪心法)
- K8S 生态周报| kube-scheduler 频繁抢占时内存泄漏问题得到修正
- 时间解决Java中Redis过期时间设置问题(redisjava过期)
- 解决Linux文件上传问题(linux不能上传文件)
- 主机访问Linux主机遇到外网无法访问的问题(外网无法访问linux)
- 管理用EBS Oracle管理薪资,轻松解决薪酬结算问题(ebs oracle薪水)
- 利用Redis提升集群性能(redis解决集群问题)
- 采用C++实现区间图着色问题(贪心算法)实例详解