搜索与图论(一)学习笔记

举报
irrational 发表于 2022/01/18 00:10:05 2022/01/18
【摘要】  深度优先搜索DFS 深度优先搜索非常执着,就是要 找穿一条路,然后再走下一条,而不会退到远点,而是一有机会就走向下一条 相比之下,bfs就相对稳重,走完一层才走下一层,稳扎稳打。 对空间要求比较高,一般用深度优先搜索,而要计算距离,则用广度优先搜索。   应用DFS进行全排列,可以...

 深度优先搜索DFS

深度优先搜索非常执着,就是要 找穿一条路,然后再走下一条,而不会退到远点,而是一有机会就走向下一条

相比之下,bfs就相对稳重,走完一层才走下一层,稳扎稳打。

对空间要求比较高,一般用深度优先搜索,而要计算距离,则用广度优先搜索

 

应用DFS进行全排列,可以得到上图的结果

注意:1、恢复现场,st[i]=false;

 例题 n皇后问题

知识点:剪枝

正对角线与反对角线

之所以不考虑!row[i] 是因为我们是一行一行放的

u+i与n-u+i是怎么来的?

实际上作图由简单的一次函数关系可知。

遇到不符合情况的时候,提前停止,恢复现场,退到上一步

 思路一:运用对角线 列 和 反对角线

思路二:运用二叉树

还是讨论一种原始的方法:每个格子只有放或者不放两种可能

时间复杂度:n*n!

例题:走迷宫

俗话说得好,兔子不吃窝边草,但是BFS就是从窝边草一直开始吃,吃吃吃。

dp问题和我们的最短路径问题是互通的

深度优先搜索可以保证搜到这个终点,但不能保证是最短的。

 

 树属于无环连通图

 

邻接表表示可达点,具体顺序倒无关紧要了

多插入一点 的 头插法方法

 图的遍历

宽度优先搜索

例子:树的重心

 

删掉1这个点,连通块最大点数为4

重边和自环

 

起点在终点之前,就属于是一个拓扑序列

成环的话,无论如何都成为不了拓扑序列

有向无环图一定存在拓扑序列,一定是拓扑图

度的概念 入度与出度

删边,不断搞到入度为0的点,不断进攻

 可现在问题来了,如何检测是不是有环图?

反证法:如果不存在入度为0的点,那么可以反复往前找,那么找到n+1次(比边数多1,那么一定会产生重复,那么就一定成环)

例题:八数码

文章来源: blog.csdn.net,作者:irrationality,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/weixin_54227557/article/details/120729054

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200