回溯法

发表于 分类于 ， ， 本文字数： 362

##回溯法

###基本原理：递归
###套路模板:

1
2
3
4
5
6
7
8
9
10
11
12
13
res = []
state = []
p,q,r
def back(状态，条件...)：
    if 不满足条件
        return
    elif 状态满足要求
        res.apend(state)
        return
    递归过程
    back(状态，条件...)
return res

###使用回溯法的明显标志
1.排列、组合（子集、幂集、字符全排列）
2.数值、字符串，给定一个特定规则，尝试搜索迭代找到这个解
3.二维数组下的DFS搜索（八皇后、黄金矿工、数独）
###加速方法
####传递数组下标而不是整个剩余数组
####剪枝
利用已知的先验条件，将后面不可能满足任务目标的搜索路径去掉
####构建图
将题目给出的数组数据建立联系，尝试构建一个图，回溯法转换为对图的DFS搜索，极大缩小了解空间
####回溯法转构造法

------ 本文结束感谢您的阅读 ------
请我一杯咖啡吧！
itingyu 微信打赏 微信打赏