Backtrack

  • 是暴力搜索法中的一种
  • 回溯法采用试错的思想,它尝试分步的去解决一个问题。在分步解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现,在反复重复上述的步骤后可能出现两种情况:
    • 找到一个可能存在的正确的答案
    • 在尝试了所有可能的分步方法后宣告该问题没有答案

经典例题

八皇后问题
  • 很多人都知道 8皇后问题,即在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上。一种可能的放置方法法如下:

  • 解题步骤:

    • 在第n行寻找可以插入的位置,中间涉及到位置合法性的判断
    • 如果没有可以插入的位置,返回
    • 如果有可以插入的位置, 插入数据。此时再判断是否已经是最后一行,如果是,打印输出返回;反之继续对下一行数据进行试探处理。
  • Python代码:

1
2
3
4
5
6
7
8
9
10
11
12
def eight_queen_question(arr=[None] * 8, n=0):
if n == len(arr):
print(arr)
return
for col in range(len(arr)):
arr[n], flag = col, True # 表示把第n行的皇后放在col列上
for row in range(n):
if arr[row] == col or abs(col - arr[row]) == n - row: # 判断是否跟前面的皇后冲突
flag = False
break
if flag:
eight_queen_question(arr, n+1)
46. Permutations
  • 给定一个不同整数的集合,返回所有可能的排列。举例:
1
2
3
4
5
6
7
8
9
10
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
  • 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 回溯
class Solution:
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
tmp = []
def backtrack(nums, tmp, arr):
if len(arr) == len(nums): tmp.append(arr)
else:
for i in range(len(nums)):
if nums[i] not in arr: backtrack(nums, tmp, arr + [nums[i]])

backtrack(nums, tmp, [])
return tmp
47. Permutations II

给定一组可能包含重复项的数字,返回所有可能的唯一排列。举例:

1
2
3
4
5
6
7
Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
  • 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 回溯
# time:276 ms space:6.7 MB
class Solution:
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
def dfs(nums, cur, res):
if not nums: res.add(cur)
else:
for i in range(len(nums)):
dfs(nums[:i] + nums[i + 1:], cur + (nums[i], ), res)

res = set()
dfs(nums, (), res)
return list(res)
51. N-Queens
  • N皇后之谜是把N皇后放在一个N×N棋盘上,这样就不会有两个皇后互相攻击。给定一个整数n,将所有不同的解返回到n-queens难题。每一种解决办法都有一个单单的单子配置,而在哪里都有的。举例:
1
2
3
4
5
6
7
8
9
10
11
12
13
Input: 4
Output: [
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],

["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
解释:有两个不同的解决方案,4皇后难题,如上图所示。
  • 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
self.result = []
self.col = set()
self.left = set()
self.right = set()
self.dfs(n, 0, [])
return self.result

def dfs(self, n, row, curstate):
if row >= n: return self.result.append(curstate)
for col in range(n):
if col in self.col or ((row + col) in self.left) or ((row - col) in self.right): # 砍树枝
continue
self.col.add(col)
self.left.add(col + row)
self.right.add(row - col)
self.dfs(n, row + 1, curstate + ['.'*col+'Q'+'.'*(n-col-1)]) # 逐行绘制
self.col.remove(col)
self.left.remove(col + row)
self.right.remove(row - col)
Donate comment here