写在前面
算法很美,真的很美
当我们去尝试理解某种算法的过程中可能不会那么顺利
一旦悟透了其中的思想,不仅能让我们身心愉悦,更能丰富编程思维
从这篇博客开始我准备写一系列关于算法的博客,顺便备赛一下蓝桥杯
博客原文:https://syjun.vip/archives/289.html
基本概念
深度优先搜索算法（Depth First Search，简称DFS）：一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件(不满足条件也被称为剪枝)，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。
算法思想
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
我这里准备了一张GIF图片,希望能够帮助你理解其中的思想
DFS可以理解为一条路走到底,不撞南墙不回头
撞南墙有两种情况
DFS的另一种结束条件,就是找到了目标出口,也就是找到了题目的答案
DFS的本质其实就是枚举
算法模板
光看概念就想理解一种算法肯定不太现实,所以接下来我会通过两道题目进行讲解
在做题之前,我们可以看看这种题目的算法模板
看不懂没关系,当你做完后面的两道题目的时候
再回过头来看,我相信你一定能够茅塞顿开
-----------------------深度优先搜索-----------------------
def dfs(current: int):
if (判断边界):
输出结果
for (尝试每一种可能):
if (满足check条件):
标记
继续下一步dfs(current + 1)
回溯, 恢复初始状态(可根据题目要求选择是否回溯)
def check(param):
if (满足条件):
return Ture
return False
-----------------------深度优先搜索-----------------------
素数环
素数环是一道非常经典的DFS算法题,这道题目很好理解,我就不做过多的解释
我就理一下这道题目的限制条件
- 第一个数一定是1
- 相邻两个数之和是素数,包括第一个数和最后一个数之和
- 素数环中不能存在重复的数字
那么,我们怎么利用DFS的思想完成这道题目呢?
首先,我们知道DFS的本质就是枚举,它会列举每一种情况进行判断,如果满足题目要求就输出结果
如果,遇到限制条件(相邻两个数之和不是素数)就会回溯,继续进行下一层的判断
我这里也准备了一张图片,方便大家理解枚举的整个过程
枚举的过程比较容易理解,但是回溯的过程可能就不是那么容易了
我给大家举个例子,比如程序正在跑这条路线(可结合开头的GIF图片理解)
题目理解的差不多了,就可以开始写代码了,本题以Python举例
(不出意外的这个系列的所有代码都会用Python,因为比赛是用Python )
代码化想法
在写代码之前,可能脑海里面冒出的第一个问题就是:如何枚举每一种情况呢?
我们可以利用for循环和列表进行这样的操作
如果,我们需要求当n=6时,素数环的情况
我们就可以循环六次,将1-6这6个数放进列表中
其实也不用循环六次,五次就够了,我们从题目中的隐藏条件就可以知道,第一个数一定是1
所有只需要循环五次,将2-6放进列表中,当然这样还不够
在循环的时候,就需要用到深度优先搜索,在循环时需要进行递归操作
我先给大家看看伪代码吧
def dfs(num,rec,cur):
# num 代表n,也就是素数环的长度
# rec 代表一个列表,用于存储数据
# cur 代表当前素数环的位置
if 满足条件输出结果:
print(结果)
return
for i in range(2,num+1):
if check():# 满足题目要求
rec[cur] = i
dfs(num, rec, cur + 1) # cur+1 进行递归操作,也就是DFS
rec[cur] = 0 # 回溯 即将当前状态变为初始值
大致的代码逻辑就是这样,我们继续将代码补充完整
import math
def dfs(num, rec, cur):
# 当前需要填的位置,等于素数环的长度时和
# 第一个数和最后一个数之和为素数时即满足题目要求
if cur == num and isPrime(rec[0]+rec[-1]):
print(rec)
return
for i in range(2, num + 1): # 填数字
if check(i, rec, cur): # 剪枝
rec[cur] = i
dfs(num, rec, cur + 1)
rec[cur] = 0 # 回溯 即将当前状态变为初始值
# 如果不进行回溯操作的话,
# 当出现一种正确的结果时 rec = [1, 4, 3, 2, 5, 6]
# 再次进行check的时候,后面的判断都会是False 原因:num in set(rec)
def check(num, rec, cur): #判断是否后面的值在前面出现或者前面一个数和当前的数之和为素数
if num in set(rec) or (isPrime(rec[cur - 1] + num)) != True:
return False
else:
return True
def isPrime(n): # 判断是否为素数
if n <= 1:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
if __name__ == '__main__':
num = 6
num_list = [0 for i in range(num)]
num_list[0] = 1
dfs(num, num_list, 1)
当你将这道题目理解清楚后,回头看一下算法模板,是不是感觉非常Amazing呢
N皇后
接着,我们再来做一道经典的DFS算法题目
题目描述
在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
题目的限制条件
- 2个皇后不允许处在同一排,同一列
- 不允许处在与棋盘边框成45角的斜线上
有了上一题的经验,我就直接上解析图了,枚举就完事了
解题细节
在写代码的时候,有的同学可能就会思考,如何表示皇后所在的行列位置
极大可能会想到二维列表,一个元素表示行数,一个元素表示列数
其实仔细分析一下上面的图片,就能想到一种简单的表示方式,一维列表就能解决
每行只能放一位皇后,那么我们就可以使用列表的索引表示,行数
然后通过索引对应的值,表示列数,每位皇后的位置就能表示出来
例如,上图的解就可以这样表示: [1, 3, 0, 2]
解决保存皇后位置的问题后,又会浮现一个新的问题
题目的限制条件,如何通过if判断语句写出来
判断2个皇后是否处在同一排,同一列;这个还好
如何判断2个皇后是否处在45角的斜线上呢,这里就有一个小技巧,我就直接上图了
当我们想要找到(1,1)这个坐标正对角线的其他值时{(0,0),(2,2),(3,3)}
可以发现一个规律:列数-行数的值是相等的
同样,反对角上的值{(0,2),(2,0)}
可以发现一个规律:列数+行数的值是相等的
所有,我们就可以通过这两个规律进行if判断
代码化思想
def dfs(rec, row):
global n # 引用全局变量
if row == n : # 跳出递归的条件
print(rec)
return
for col in range(0, n): # 尝试将皇后放在某列中
if check(rec,col,row): # 剪枝
rec[row] = col # 标记
dfs(rec,row+1) # 深度优先搜索,继续搜索下一行
# rec[row] = 0 可以回溯也可以不用
# 之所以这里可以不用回溯,是因为执行回溯操作不会对剪枝造成影响
def check(rec,col,row):
for i in range(row): # 此循环判断 是否满足题目要求
if (rec[i] == col or i + rec[i] == row + col or rec[i] - i == col - row):
return False
return True
if __name__ == '__main__':
n = 4
rec = [0 for _ in range(n)]
dfs(rec, 0)
当你将这道题目理解清楚后,回头看一下算法模板,是不是感觉非常Amazing呢
写在后面
深度优先搜索的题目,只要理解了算法模板
那么,之后碰到类似的题目就可以信手拈来
枚举+递归+回溯 = DFS
[复制链接]
发表于 2021-3-29 20:03
