穷举(2020年11月23日课堂内容记录)

穷举分为 回溯(Back Track) 和 分支界限(Branch & Bound)
二者都是在 解空间(state) 内 得到(search) 需要的解：

• 如何组织状态state—->数据结构
• 如何搜索search—->算法

回溯(Back Track)

回溯可以理解为选中一个初始状态，这个状态连接着许多子状态，接下来也选中一个子状态……一步一步向前走，遇到障碍不要紧，可以撤回到上一步达到的状态。这里的撤回，就是回溯的核心。

因为选择的策略是选择子状态，没有子状态才选择父状态的另一个子状态(兄弟状态)，不难看出，这是DFS(深度优先搜索)

经典例题——八皇后问题

想要挑战ACM题的同学可以先做一下这道华东师范大学在线评测系统上的题目练练手，链接如下：

链接: 八皇后问题(回溯)——ECNU OJ.

在一个8*8的国际象棋棋盘上摆下8个皇后，一共有多少种摆法？摆放规则很简单，这些皇后两两不能在同一行同一列以及同一对角线。

这个问题如何用回溯？也很容易。分析算法，我们知道，每一行必有一个皇后，只是它应该在哪一列，我们不知道。换言之，我们需要从第一行开始，对每一列探索一下，假设当前选中第 j 列，如果摆在(1,j)这个位置，能否让剩余七个皇后都在棋盘上放下，那就要继续先选择第二行，同样从第一列开始摆到最后一列，看看哪个位置能放第二个皇后，继而尝试第三个……以此类推，直到有一行尝试了所有列，都不能摆下皇后，那么就要撤回到上一行尝试下一列。

想法很简单，伪代码可以这么写(相较于老师给出的bool返回型代码，我直接返回这个size的棋盘有多少解，做了些小改进)：

def solveNQ(int row):
	#先写停止条件
	if row >= size: return 1 #size在这里就是8，原指棋盘总行/列数
	else:
		sum = 0
		for col from 1 to size, step 1:
			if (row,col) is a safe position: #这里要写一个is_safe()的辅助判断函数
				place a queen at (row,col)
				sub_sum = solveNQ(row+1) #递归，DFS
				if sub_sum > 0: #证明这个位置接下去可以找到解
					sum += sub_sum
				else: #这个位置接下去找不到解，那就撤回
					remove queen at (row,col)
		return sum #如果这里sum是0,就说明在这一行找遍了所有列，都失败了。

def is_safe(i,j): #i表示行，j表示列
	for previousPoint in previousPoints:
		if j == previousPoint.y: return false #同一列
		if (i+j) == (previousPoint.x + previousPoint.y): return false #同对角线
		if (previousPoint.x - i) == (previousPoint.y - j): return false #同对角线

代码嘛……也差不多。这里就不提供了。

分支界限 (Branch & Bound)

时间有限，周末再加班加点更新一下

本文地址：https://blog.csdn.net/weixin_45439696/article/details/110141797