回溯
回溯法（back tracking）（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
1 基本思想
从一条路往前走，能进则进，不能进则退回来，换一条路再试。
2 一般步骤
- 定义一个解空间（子集树、排列树二选一）
- 适于搜索的方法组织解空间。
- 利用深度优先法搜索解空间。
- 利用剪枝函数避免移动到不可能产生解的子空间。
3 子集树模板
遍历子集树，时间复杂度 O(2^n)
如果解的长度是不固定的，那么解和元素顺序无关，即可以从中选择0个或多个。例如：子集，迷宫，...
如果解的长度是固定的，那么解和元素顺序有关，即每个元素有一个对应的状态。例如：子集，8皇后，...
解空间的个数是指数级别的，为2^n,可以用子集树来表示所有的解，适用于：幂集、子集和、0-1背包、装载、8皇后、迷宫、...
# 子集树递归模板
n = 4
#a = ['a','b','c','d']
a = [1, 2, 3, 4]
x = [] # 一个解（n元0-1数组）
X = [] # 一组解
# 冲突检测：无
def conflict(k):
global n, x, X, a
return False # 无冲突
# 一个例子
# 冲突检测：奇偶性相同，且和小于8的子集
def conflict2(k):
global n, x, X, a
if k==0:
return False
# 根据部分解，构造部分集
s = [y[0] for y in filter(lambda s:s[1]!=0, zip(a[:k+1],x[:k+1]))]
if len(s)==0:
return False
if 0 < sum(map(lambda y:y%2, s)) < len(s) or sum(s) >= 8: # 只比较 x[k] 与 x[k-1] 奇偶是否相间
return True
return False # 无冲突
# 子集树递归模板
def subsets(k): # 到达第k个元素
global n, x, X
if k >= n: # 超出最尾的元素
#print(x)
X.append(x[:]) # 保存（一个解）
else:
for i in [1, 0]: # 遍历元素 a[k] 的两种选择状态:1-选择，0-不选
x.append(i)
if not conflict2(k): # 剪枝
subsets(k+1)
x.pop() # 回溯
# 根据一个解x，构造一个子集
def get_a_subset(x):
global a
return [y[0] for y in filter(lambda s:s[1]!=0, zip(a,x))]
# 根据一组解X, 构造一组子集
def get_all_subset(X):
return [get_a_subset(x) for x in X]
# 测试
subsets(0)
# 查看第3个解，及对应的子集
#print(X[2])
#print(get_a_subset(X[2]))
print(get_all_subset(X))
[[1, 3], [1], [2, 4], [2], [3], [4], []]
4 实例
4.1 八皇后问题
我们可以先将八皇后简化为四皇后，解题思路如下：
-
尝试先放置第一枚皇后，被涂黑的地方是不能放皇后
step1 -
第二行的皇后只能放在第三格或第四格，比方我们放第三格，则：
step2 -
可以看到再难以放下第三个皇后，此时我们就要用到回溯算法了。我们把第二个皇后更改位置，此时我们能放下第三枚皇后了。
step3 - 虽然是能放置第三个皇后，但是第四个皇后又无路可走了。返回上层调用（3号皇后），而3号也别无可去，继续回溯上层调用（2号），2号已然无路可去，继续回溯上层（1号），以此类推继续回溯。
这样就能在一步一步的测试中把八皇后的问题解决出来了
import random
# 随机模块
#state 保存的是已经确定皇后的列的坐标 [0,2]
#pos 表示新增加的皇后列的坐标 2
def conflict(state, pos):
nextY = len(state)
if pos in state: return True
'''判断斜线'''
for i in range(nextY):
if nextY-pos == i-state[i]: return True
if nextY+pos == i+state[i]: return True
return False
def queens(num=8, state=()):
# 生成器函数
for pos in range(num):
#print(state, pos)
if not conflict(state, pos):
#print(state,pos)
if len(state) == num - 1:
yield (pos,) #生成器 range(10)
else:
for result in queens(num, state + (pos,)):
yield (pos,) + result
def queenprint(solution):
# 打印函数
def line(pos, length=len(solution)):
#print('pos:',pos)
return '. ' * (pos) + 'X ' + '. ' * (length - pos - 1)
for pos in solution:
print(line(pos))
# for solution in list(queens(8)):
# print("aaaaa")
# print(solution)
# print(' total number is ' + str(len(list(queens()))))
# print(' one of the range is:\n')
queenprint(random.choice(list(queens())))
X . . . . . . .
. . . . . . X .
. . . . X . . .
. . . . . . . X
. X . . . . . .
. . . X . . . .
. . . . . X . .
. . X . . . . .
这里随机给出了把皇后的一种答案
4.2 背包问题
4.2.1 背包问题的解题思路
有N件物品和一个容量为V的背包。第i件物品的体积是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
这是最基础的背包问题，总的来说就是：选还是不选，这是个问题
相当于用s[i]表示放进背包的前i个物体的总体积，v[i]表示放进背包的前i个物体的总价值，只有两种情况：
- 第i件不放进去，这时背包内的物品体积为s[i-1]，背包的价值为v[i-1]
- 第i件放进去，这时背包内的物品体积为s[i]，背包的价值为v[i]
4.2.2 问题的解空间
用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少包含问题的一个(最优)解。对于 n=3 时的 0/1 背包问题，可用一棵完全二叉树表示解空间，如图所示：
1表示选取，0表示不选
4.2.3 代码实现
#bestV 最优的价值
bestV=0
#当前重量
curW=0
#当前价值
curV=0
#当价值最优的时候的，背包的物品列表
bestx=None
def backtrack(i):
global bestV,curW,curV,x,bestx
if i>=n:
if bestV<curV:
bestV=curV
bestx=x[:]
else:
if curW+w[i]<=c:
x[i]=True
curW+=w[i]
curV+=v[i]
backtrack(i+1)
curW-=w[i]
curV-=v[i]
x[i]=False
backtrack(i+1)
if __name__=='__main__':
#表示总共有几种商品
n=5
#最大容量
c=10
#w代表每种商品的重量
w=[2,2,6,5,4]
#v代表每种的价值
v=[6,3,5,4,6]
#是当前背包情况
x=[False for i in range(n)]
backtrack(0)
print(bestV)
print(bestx)
15
[True, True, False, False, True]
总结
问题：
八皇后中的queens()函数中没有用return，而使用的是yield，不太清楚这个函数是什么意思？
答：yield和return的关系和区别，带yield的函数是一个生成器，而不是一个函数了，这个生成器有一个函数就是next函数，next就相当于“下一步”生成哪个数，这一次的next开始的地方是接着上一次的next停止的地方执行的，所以调用next的时候，生成器并不会从foo函数的开始执行，只是接着上一步停止的地方开始，然后遇到yield后，return出要生成的数，此步就结束。
需要详细了解yield()函数的可以访问以下链接：
python中yield的用法详解——最简单，最清晰的解释
