NarcissusBlog回溯算法(或DFS)
目录
1、框架
深度优先搜索就是回溯算法，解决一个回溯问题，实际上就是一个决策树的遍历过程。需要思考三个问题：
- 路径：已经做出的选择。
- 选择列表：当前可以做的选择。
- 结束条件：到达决策树底层，无法再做选择的条件。
框架如下：
核心就是for循环里面的递归，在递归调用之前做选择，递归调用之后撤销选择。
注意：回溯算法一般复杂度较高，需要配合剪枝。
2、全排列问题
n个不重复的数，全排列有n!个。比如给三个数[1,2,3],决策树如下：
回溯算法的核心框架如下：
只要在递归之前做出选择，在递归之后撤销刚才的选择，就能正确得到每个节点的选择列表和路径。代码如下：
func permute(nums []int) [][]int {
// 回溯算法
var result [][]int
var backtrack func(track, nums []int, length int)
backtrack = func(track, nums []int, length int) {
// 结束条件
if len(track) == length {
temp := make([]int, length)
copy(temp, track)
result = append(result, temp)
return
}
n := len(nums)
for index, val := range nums {
// 做选择
track = append(track, val)
nums[index], nums[n - 1] = nums[n - 1], nums[index]
nums = nums[:n - 1]
// 进入下一层决策
backtrack(track, nums, length)
// 撤销选择
track = track[:len(track) - 1]
nums = append(nums, val)
nums[index], nums[n - 1] = nums[n - 1], nums[index]
}
}
var track []int
length := len(nums)
backtrack(track, nums, length)
return result
}
3、N皇后问题
回溯算法一般要配合剪枝降低复杂度。代码如下：
func solveNQueens(n int) [][]string {
// 回溯算法
var (
result [][]string
dfs func(board [][]byte, row int)
)
dfs = func(board [][]byte, row int) {
// 结束条件
if row == n {
var temp []string
for i := 0; i < n; i++ {
temp = append(temp, string(board[i]))
}
result = append(result, temp)
return
}
for col := 0; col < n; col++ {
// 剪枝
if !isValid(board, row, col, n) {
continue
}
// 做选择
board[row][col] = 'Q'
// 下一层决策
dfs(board, row + 1)
// 撤销决策
board[row][col] = '.'
}
}
board := make([][]byte, n)
// 初始化
for i := 0; i < n; i++ {
board[i] = make([]byte, n)
for j := 0; j < n; j++ {
board[i][j] = '.'
}
}
dfs(board, 0)
return result
}
func isValid(board [][]byte, row, col, n int) bool {
// 检查列
for i := 0; i < row; i++ {
if board[i][col] == 'Q' {
return false
}
}
// 检查左斜线
for i := 1; row - i >= 0 && col - i >= 0; i++ {
if board[row - i][col - i] == 'Q' {
return false
}
}
// 检查右斜线
for i := 1; row - i >= 0 && col + i < n; i++ {
if board[row - i][col + i] == 'Q' {
return false
}
}
return true
}
- 代码中，通过isValid函数对回溯算法进行了剪枝。不符合就不需要继续进入下一层决策，降低了复杂度。
4、回溯解决排列,子集,组合问题
求子集、求排列、求组合这几个问题都可以用回溯思想解决。(排列问题见上面)
子集
代码如下：
func subsets(nums []int) [][]int {
// 回溯算法
var (
result [][]int
dfs func(track []int, index int)
)
dfs = func(track []int, index int) {
// 加入结果集
temp := make([]int, len(track))
copy(temp, track)
result = append(result, temp)
// 结束条件
if index == len(nums) {
return
}
for i := index; i < len(nums); i++ {
// 做选择
track = append(track, nums[i])
// 进入下一层决策
dfs(track, i + 1)
// 撤销决策
track = track[:len(track) - 1]
}
}
track := []int{}
dfs(track, 0)
return result
}
决策树如下：
组合
代码如下：
func combine(n int, k int) [][]int {
// 回溯思想
var (
result [][]int
dfs func(track []int, index int)
)
dfs = func(track []int, index int) {
// 结束条件
if len(track) == k {
temp := make([]int, k)
copy(temp, track)
result = append(result, temp)
return
}
// 剪枝
if len(track) + n - index + 1 < k {
return
}
for i := index; i <= n; i++ {
// 做出选择
track = append(track, i)
// 进入下一层
dfs(track, i + 1)
// 撤销决策
track = track[:len(track) - 1]
}
}
var track []int
dfs(track, 1)
return result
}
决策树如下：
5、解数独
代码如下：
func solveSudoku(board [][]byte) {
// 回溯
var dfs func(board [][]byte, row, col int) bool
dfs = func(board [][]byte, row, col int) bool {
m, n := 9, 9
// 结束条件
if row == m {
return true
}
for i := col; i < n; i++ {
if board[row][i] != '.' {
continue
}
for c := '1'; c <= '9'; c++ {
// 剪枝
if !isValid(board, row, i, byte(c)) {
continue
}
// 做选择
board[row][i] = byte(c)
// 进入下一层决策
if dfs(board, row, i + 1) {
return true
}
// 撤销决策
board[row][i] = '.'
}
return false
}
// 进入下一行
return dfs(board, row+1, 0)
}
dfs(board, 0, 0)
}
func isValid(board [][]byte, row, col int, char byte) bool {
for i := 0; i < 9; i++ {
// 判断行是否有重复
if board[row][i] == char {
return false
}
// 判断列是否有重复
if board[i][col] == char {
return false
}
// 判断小九宫格是否有重复
if board[(row / 3)*3 + i / 3][(col / 3)*3 + i % 3] == char {
return false
}
}
return true
}
6、合法括号生成
括号问题可以简单分为两类：一是括号合法性判断；另一个是括号生成。括号合法性判断一般需要用到栈，括号生成一般考虑回溯思想。
关于括号问题，有以下两个特点：
- 一个合法括号组合的左括号数量一定等于右括号数量。
- 对于一个合法的括号字符串组合
p，必然对于任何0 <= i < len(p)都有：子串p[0..i]中左括号的数量都大于或等于右括号的数量。
代码如下：
func generateParenthesis(n int) []string {
// 回溯
var (
result []string
dfs func(track []byte, leftNum, rightNum int)
)
dfs = func(track []byte, leftNum, rightNum int) {
// 结束条件
if len(track) == 2 * n {
if leftNum == rightNum {
temp := make([]byte, 2 * n)
copy(temp, track)
result = append(result, string(temp))
}
return
}
// 剪枝
if rightNum > leftNum || leftNum > n {
return
}
track = append(track, '(')
dfs(track, leftNum + 1, rightNum)
track = track[:len(track) - 1]
track = append(track, ')')
dfs(track, leftNum, rightNum + 1)
track = track[:len(track) - 1]
}
var (
track []byte
leftNum, rightNum int
)
dfs(track, leftNum, rightNum)
return result
}