当前位置: 首页> 文旅> 美景 > 日本室内设计网站推荐_深圳高端网站定制_中国免费网站服务器主机域名_seo自学网官方

日本室内设计网站推荐_深圳高端网站定制_中国免费网站服务器主机域名_seo自学网官方

时间:2025/7/11 22:47:11来源:https://blog.csdn.net/a72024791/article/details/146988059 浏览次数:1次
日本室内设计网站推荐_深圳高端网站定制_中国免费网站服务器主机域名_seo自学网官方

一、核心知识点清单

1. DFS基础概念
  • 定义:深度优先搜索(Depth-First Search),一种“一条路走到底”的递归搜索算法。从初始点v出发,访问v,后选择与v相邻且未被访问的点w,以w为初始点,继续访问,递归进行。

  • 类比:像走迷宫时,优先选择一条路走到死胡同,再回退到上一个岔路口(回溯),直到碰到一个未走过的岔路口、继续探索。

  • 核心思想:递归 + 回溯。

2. DFS递归模板(Python版)
def dfs(当前状态):if 达到终止条件:  # 例如找到了解、越界、访问过记录结果或处理逻辑returnfor 选择 in 所有可能的分支:  # 遍历所有子节点或方向if 不满足条件:  # 剪枝(跳过无效分支)continue标记当前状态(如visited[i] = True)dfs(下一状态)  # 递归进入下一层撤销标记(回溯,如visited[i] = False)
3. 术语
  • 递归:函数调用自身,注意终止条件。

  • 回溯:撤销上一步操作,恢复状态(关键易错点!)。

  • 剪枝:提前跳过无效分支,提升效率。

4.举例说明

以这个图为例,从0开始,到1之后将1设为初始点,寻找未被遍历过且与之相邻的点3;这时将3设为初始点,继续寻找,此时的情况是,2和4均相邻且未被遍历,假设我们选择4进行下一步的初始点,访问之后已无相邻且未被遍历的点,即无满足条件的目标。此时回溯到上一初始点3,选择合适的目标2进行访问,访问完之后同样“ 到头”,继续回溯,一直都没有满足条件的目标,直到回溯到初始点0,此次搜索结束。

由此我们还可得出,dfs的搜索结果不唯一,此题中,01342和01324皆为答案。

5. 树的DFS遍历(最直观例子)
  • 前序遍历:根 → 左 → 右

  • 代码示例:

    class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef dfs(root):if not root:returnprint(root.val)  # 处理当前节点dfs(root.left)    # 递归左子树dfs(root.right)  # 递归右子树


二、学习安排

第1个30分钟:理解概念
  1. 学习dfs基础知识点(例如网络视频和上述知识讲解),重点关注:

    • DFS的“深度优先”如何体现?

    • 递归调用栈的执行顺序。

  2. 用纸笔画出二叉树的DFS遍历过程(如下图):

        1/ \2   3/ \
    4   5

    预期输出:1 → 2 → 4 → 5 → 3

第2个30分钟:手写模板
  1. 抄写并背诵DFS模板。

  2. 修改模板实现二叉树的中序遍历(左→根→右)。

    def inorder(root):if not root:returninorder(root.left)print(root.val)inorder(root.right)
第3个30分钟:基础题目实战
  1. 题目1:二叉树的所有路径(LeetCode 257)

    • 要求:输出从根节点到所有叶子节点的路径。

    • 关键点:用字符串记录路径,回溯时删除末尾节点。

    • 代码框架:

      def binaryTreePaths(root):def dfs(node, path):if not node.left and not node.right:res.append(path + str(node.val))returnif node.left:dfs(node.left, path + str(node.val) + "->")if node.right:dfs(node.right, path + str(node.val) + "->")res = []if root: dfs(root, "")return res
第4个30分钟:N皇后问题

洛谷题目https://www.luogu.com.cn/problem/P1219

蓝桥n皇后题目

  1. 题目理解:在N×N的棋盘上放置N个皇后,使得它们互不攻击(即任意两个皇后不能在同一行、同一列或同一对角线上)。

  2. 简化版思路

    • 用一维数组queens记录每行皇后的列号。

    • DFS逐行放置皇后,检查冲突时剪枝。

  3. 代码提示:

    def solveNQueens(n):def dfs(row):nonlocal resif row == n:  # 所有行已放满res = [['.' * i + 'Q' + '.' * (n - i - 1) for i in queens]]returnfor col in range(n):if all(col != queens[i] and row - i != abs(col - queens[i]) for i in range(row)):queens[row] = col  # 放置皇后dfs(row + 1)       # 进入下一行queens = [0] * n  # queens[i]表示第i行皇后的列号res = []dfs(0)return res# 测试输出一种解
    print(solveNQueens(4))
    # 输出示例:[['.Q..', '...Q', 'Q...', '..Q.']]
关键点解释
  1. 剪枝条件

    • col != queens[i]:检查列冲突

    • row - i != abs(col - queens[i]):检查对角线冲突

  2. 回溯:通过queens[row] = col和递归后的隐式回溯(无需显式撤销,因为每次循环覆盖赋值)。

上面那个代码是输出一种解,即输出n皇后陈列放射最后的样态,如果要输出有几种摆法,还有下面一种算法。下面的代码对应的是蓝桥杯中n皇后的题目。

def NQueens(n):# 定义深度优先搜索函数,row 表示当前处理的行def dfs(row):# 当 row 等于 n 时,说明已经成功放置了 n 个皇后,方案数加 1if row == n:nonlocal countcount += 1return# 遍历当前行的每一列for col in range(n):# 检查当前列、主对角线和副对角线是否被占用if not (cols[col] or diag1[row + col] or diag2[row - col + n - 1]):# 若未被占用,标记当前列、主对角线和副对角线已被占用cols[col] = diag1[row + col] = diag2[row - col + n - 1] = True# 递归处理下一行dfs(row + 1)# 回溯操作,将当前列、主对角线和副对角线标记为未被占用cols[col] = diag1[row + col] = diag2[row - col + n - 1] = False# 初始化列标记数组,用于记录每一列是否被占用cols = [False] * n# 初始化主对角线标记数组,用于记录主对角线是否被占用diag1 = [False] * (2 * n - 1)# 初始化副对角线标记数组,用于记录副对角线是否被占用diag2 = [False] * (2 * n - 1)# 初始化方案数为 0count = 0# 从第 0 行开始进行深度优先搜索dfs(0)# 返回总的方案数return count# 读取用户输入的 n
N = int(input())
# 调用 NQueens 函数计算方案数并打印结果
print(NQueens(N))

 来详细分析一下这个代码,定义一个总函数,总函数中包含dfs函数和初始化标记。

1、主函数NQueens是一个接受一个整数参数 n 的函数,n 代表棋盘的大小(即 n×n 的棋盘),函数的目的是返回在这个棋盘上放置 n 个皇后的所有可行方案的数量。

2、初始化标记

    cols = [False] * ndiag1 = [False] * (2 * n - 1)diag2 = [False] * (2 * n - 1)count = 0
  • cols 是一个长度为 n 的布尔型列表,用于标记每一列是否已经被皇后占据。初始时,所有列都未被占据,所以列表中的元素都为 False
  • diag1 是一个长度为 2 * n - 1 的布尔型列表,用于标记从左上到右下的主对角线是否被皇后占据。因为在 n×n 的棋盘上,主对角线的数量为 2 * n - 1 条,所以列表长度为 2 * n - 1。初始时,所有主对角线都未被占据,元素都为 False
  • diag2 是一个长度为 2 * n - 1 的布尔型列表,用于标记从右上到左下的副对角线是否被皇后占据。同样,副对角线的数量也是 2 * n - 1 条,初始时所有副对角线都未被占据,元素都为 False
  • count 是一个整数变量,用于记录所有可行的放置方案的数量,初始值为 0。

这里解答一个疑问,对角线列表的元素为什么为2*n-1。这里的对角线其实指的就是每个以45度角平分正方形的每条线。不难得出,这么去切的时候,2*2的矩阵有三条线(分别是分割对角两个小正方形和分隔大正方形的最大对角线),以此类推便很容易理解。

3、深度优先搜索函数 dfs

    def dfs(row):if row == n:nonlocal countcount += 1return

参数 row 为当前正在处理的行号。当 row 等于 n 时,意味着已经成功地在每一行都放置了一个皇后,找到了一种可行的放置方案。此时,使用 nonlocal 关键字引用并修改外层函数的 count 变量,将其加 1,表示找到了一种新的方案,然后返回。

4、寻找n皇后的放置位置

        for col in range(n):if not (cols[col] or diag1[row + col] or diag2[row - col + n - 1]):cols[col] = diag1[row + col] = diag2[row - col + n - 1] = Truedfs(row + 1)cols[col] = diag1[row + col] = diag2[row - col + n - 1] = False
  • 对于当前行 row,遍历每一列 col

  • cols[col] 用于检查第 col 列是否已经被占据;diag1[row + col] 用于检查当前位置所在的主对角线是否已经被占据;diag2[row - col + n - 1] 用于检查当前位置所在的副对角线是否已经被占据。如果这三个条件都不满足,说明当前位置可以放置皇后。(这里如何表达对角线上的位置需要格外注意)

  • 如果当前位置可以放置皇后,将 cols[col]diag1[row + col] 和 diag2[row - col + n - 1] 都标记为 True,表示该列和对应的对角线已经被占据。

  • 递归调用 dfs(row + 1),继续处理下一行。

  • 回溯操作:当递归返回时,将 cols[col]diag1[row + col] 和 diag2[row - col + n - 1] 都标记为 False,表示撤销当前位置的皇后放置,以便尝试其他可能的放置方案。(不回溯就没有办法继续寻找其他方案)

5、调用dfs

    dfs(0)return count
  • 从第 0 行开始调用 dfs 函数进行深度优先搜索。

  • 最后返回 count,即所有可行的放置方案的数量。


四、常见错误提醒

  1. 忘记回溯:例如八皇后问题中修改queens后没恢复状态。

  2. 递归终止条件错误:导致无限递归(如二叉树遍历忘记判断if not root)。

  3. 剪枝不彻底:在排列问题中未去重,导致重复解。


五、自查清单

  • 能独立写出DFS模板?

  • 能解释八皇后问题的剪枝逻辑?--即什么情况下跳过分支(三个冲突)

  • 能手动模拟二叉树DFS的递归栈?

关键字:日本室内设计网站推荐_深圳高端网站定制_中国免费网站服务器主机域名_seo自学网官方

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: