回溯法
算法框架
- 非递归
int a[n], i;初始化数组a[]; i = 1; while (i > 0(有路可走) and(未达到目标)) // 还未回溯到头 { if (i > n) // 搜索到叶结点 { 搜索到一个解，输出； } else // 处理第i个元素 { a[i]第一个可能的值； while (a[i]在不满足约束条件且在搜索空间内) { a[i]下一个可能的值； } if (a[i]在搜索空间内) { : 标识占用的资源；20 : i = i + 1; // 扩展下一个结点 21: } 22: else 23: { 清理所占的状态空间； // 回溯25: i = i –1; } } } - 递归
回溯法是对解空间的深度优先搜索，在一般情况下使用递归函数来实现回溯法比较简单，其中i为搜索的深度，框架如下
int a[n]; try(int i) { if(i>n) 输出结果; else { for(j = 下界; j <= 上界; j=j+1) // 枚举i所有可能的路径 { if(fun(j)) // 满足限界函数和约束条件 { a[i] = j; ... // 其他操作 try(i+1); 回溯前的清理工作（如a[i]置空值等）; } } } }
三着色问题
一个无向图，邻接矩阵存储，输出所有可能的三着色结果
- 递归
```python
def color(level):
for i in range(1,4):
c[level] = i if ok(c): print(c) else: color(level+1)
a = [[0,1,1,0], [1,0,1,1], [1,1,0,1], [0,1,1,0]] c = [0,0,0,0] k = 1 flag = False color(0)
2. 非递归
```python
def ok(level):
l = list()
for i in c:
if i!=0 and i in l:
return 0
elif i!=0 and i not in l:
l.append(i)
else:
return 1
return 6
a = [[0,1,1,0],
[1,0,1,1],
[1,1,0,1],
[0,1,1,0]]
c = [0,0,0,0,0] # 1,2,3有效
k = 1
flag = False
while k>=1:
while c[k]<=2:
c[k] += 1
if ok(c) == 6:
print(c)
elif ok(c) == 1:
k += 1
c[k] = 0
k -= 1
全排列
# -*- coding:utf-8 -*-
'''
全排列问题
回溯法
'''
Count = 0 # 记录迭代的次数
MaxDeep = 3
List = [0] * (MaxDeep+1)
def Try(CurDeep):
'''探索第CurDeep层'''
global Count
for i in range(List[CurDeep]+1, MaxDeep+1):
Count += 1
List[CurDeep] = i
if OK(CurDeep): #前面符合条件=>继续深一层Try
if CurDeep == MaxDeep:
print(List[1:])
break
Try(CurDeep+1)
List[CurDeep] = 0
def OK(CurDeep):
s = set(List[1:CurDeep+1])
if len(s) == CurDeep:
return True
else:
return False
if __name__ == "__main__":
Try(1)
print("Count:",Count)
素数环问题
- 注意正序反序都一样，平移以后也一样
- 锁定第一个恒为1即可锁定 TODO :需要优化
# -*- coding:utf-8 -*-
'''
素数环问题
回溯
'''
Count = 0 # 记录迭代的次数
MaxDeep = 8
List = [0] * (MaxDeep + 1)
AllPrimeNumber = [x for x in range(3, 2 * MaxDeep, 2)] # 存储所有的素数
def Try(CurDeep):
'''探索第CurDeep层'''
global Count
start = 2 - CurDeep%2 # 前后一定一奇一偶,第一个已锁定为1，后续奇偶确定
for i in range(start, MaxDeep + 1, 2): # 恒为奇数或偶数
Count += 1
List[CurDeep] = i
if OK(CurDeep) == 1: #前面符合条件=>继续深一层Try
if CurDeep == MaxDeep:
print(List[1:-1])
break
Try(CurDeep + 1)
def OK(CurDeep):
if List[CurDeep] in List[1:CurDeep]: # 当前的值不能和之前的重复
return False # 这个判断力度最大，有效减少不必要的判断
for i in range(1, CurDeep):
if List[i] + List[i + 1] not in AllPrimeNumber:
return False
if CurDeep == MaxDeep: # 如果是最后一层，还要判断和第一个元素是否满足
if List[CurDeep] + List[1] not in AllPrimeNumber:
return False
return True
if __name__ == "__main__":
for i in range(1, MaxDeep * 2, 2): # 将不是素数的奇数删除
for ii in range(2, int(1 + i / 2)):
if i % ii == 0:
AllPrimeNumber.remove(i)
break
List[1] = 1
Try(2) # 第一个锁定，从第二个开始
print("Count:", Count)
组合问题
# -*- coding:utf-8 -*-
'''
组合问题 , 相比全排列，三处改动
回溯法
'''
Count = 0 # 记录迭代的次数
MaxDeep = 3
MaxValue = 4
List = [0] * (MaxDeep+1)
def Try(CurDeep):
'''探索第CurDeep层'''
global Count
# 相比全排列，两处改动
# for i in range(List[CurDeep]+1, MaxDeep+1): #全排列
for i in range(List[CurDeep-1]+1, MaxValue+1):
Count += 1
List[CurDeep] = i
if OK(CurDeep): #前面符合条件=>继续深一层Try
if CurDeep == MaxDeep:
print(List[1:])
# break # 全排列
continue
Try(CurDeep+1) # 没到最后一层
List[CurDeep] = 0
def OK(CurDeep):
s = set(List[1:CurDeep+1])
if len(s) == CurDeep:
return True
else:
return False
if __name__ == "__main__":
Try(1)
print("Count:",Count)
二维平面上的回溯法
leetcode79. 单词搜索
leetcode 200. 岛屿的个数
floodfill算法，一类经典问题