回溯算法1 #

1. 回溯算法的概念
2. 回溯算法代码框架1
3. 回溯算法代码框架2

回溯算法的概念 #

• 回溯是计算机解题中常用的算法，也称为试探法。回溯是递归的副产物，我们需要回溯的时候基本是通过递归实现。再调用递归函数时我们已经发现，在函数递归执行行完毕后，就会回溯到上层函数继续执行(详见261~262递归函数的讲解)。
• 回溯法的本质就是限定条件的穷举，是一种暴力搜索方法。
• 它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。

回溯算法的代码框架1 #

def dfs(step): #定义回溯函数dfs(step),step代表该问题分为几步去解决
	if step>n: #说明解决问题的一条路径已经完成
		输出结果
		return
	for (当前的一个选择) in (当前所有可能的选择):#选择一个当前的可能选择
		if(符合条件)
			保存step的结果
			dfs(step+1)           #寻找下一步的可行选择
			撤销本步骤的选择	  #恢复到保存step的结果之前的状态
dfs(1)#从第一步开始，到第n步解决问题为止，通过每个步骤的试探输出所有符合条件的解

回溯算法的代码框架2 #

def dfs(step):定义回溯函数dfs(step),step代表该问题分为几步去解决
	for (当前的一个选择) in (当前所有可能的选择):#选择一个当前的可能选择
		if(符合条件):
			保存step的结果
				if(step>n):#说明解决问题的一条路径已经完成
					输出结果
					return
				else:
					dfs(step+1)    #寻找下一步的可行选择	
			撤销本步骤的选择      #恢复到保存step的结果之前的状态
dfs(1)#从第一步开始，到第n步解决问题为止，通过每个步骤的试探输出所有符合条件的解

上述的回溯算法的两个常用的代码框架，并无本质上的差异，选择其中之一理解即可。迷宫问题就是典型的回溯算法的应用:
在迷宫问题中：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进,如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。

小结 #

• 掌握回溯算法的概念，了解回溯与递归的关系
• 理解回溯算法的代码框架

习题 #

1. 谈一谈自己对回溯的理解，回溯算法和递归算法有什么关系呢？为什么回溯到上一步的时候需要递归呢？
2. 尽可能多的举一些生活中使用回溯算法的例子