知识卡片

普通读书笔记卡 · 5654.d.1.f.4.f · 生成模型:未记录

广度优先搜索按层发现顶点

理解等级:中级

从源点入队并标记,反复取出队首并将尚未发现的邻接点标记、记录前驱和距离后入队。这样每个顶点首次发现时的距离是源点到它的最少边数;前驱构成可达区域的最短路径树。不可达顶点保持无穷距离或其他明确标记。

这个结论适用于无权图或各边具有相同正权重的情况;不同权值下最少边数不一定是最小总代价。邻接表下时间 O(V+E),队列及状态空间 O(V)。

155指出dist[v]是边数最短距离,pred[v]是前驱;源点和不可达点都可能有pred=−1,因此应结合距离或访问状态判断可达。

156强调队列的空间开销,最坏可达 O(V);最短指经过边数最少,适用有向或无向图。

157正文称在栈中存储状态,但03290实际使用 queue:取front,处理邻点后pop,新顶点在push前标灰。该先进先出顺序对分层和最少边数保证至关重要;示例没有显式检查源点索引。

158分析每个顶点至多入队一次,扫描所有可达顶点的邻接项;加上全图初始化,在邻接表与常数时间队列操作下为 O(V+E)。邻接矩阵通常需要 O(V²) 扫描。

188把BFS应用于状态空间;在有限分支、每步相同代价且状态去重正确时,首次发现目标得到最少步数。开放集和闭合集都需要考虑重复状态;图03335的伪代码只查closed,开放集中仍可能存在重复项。

189将BFS输出称作开销最小;这需要每步相同代价,否则最少步数不一定最小成本,可考虑统一代价搜索等方法。

190提醒逐层搜索可能耗费大量时间和空间;可否寻找多个路径取决于是否保留多个前驱和具体目标,而非队列结构本身。

191图03338–03339只在出队后加入closed且生成时只检查closed,同一状态可能多次进入open;可在首次入队时记录已发现状态以避免重复,并保存该次最短前驱。

192强调队列空间;队列操作、状态复制、哈希和相等比较分别有成本,不能仅依据入队出队常数就忽略其他开销。

193以分支因子b和解深度d估计BFS边界可达 O(b^d),纯深度优先路径栈可为 O(bd);但若DFS维护全局闭合集,其总空间可能随已访问状态数增长,不能一概写 O(bd)。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 11 处

    • · 查看原书依据

      广度优先搜索 广度优先搜索(图6-11)使用了和深度优先搜索一种不同的方法来搜索图。广度优先搜索系统地在图中搜索顶点,在搜索离源点s的距离为k+1条边的顶点之前,所有的离源点s距离为k条边的顶点都已经被访问。广度优先搜索不会访问图中那些源点不可达的顶点。 广度优先搜索不会进行任何回溯。我们可以通过查

    • · 查看原书依据

      dist[v]是从s到v的最短路径上的边数。pred[v]是在广度优先搜索中v的前驱顶点。根据pred[]的值,我们可以得到广度优先树,如果原始图是非连通的,那么对于所有源点不可达的顶点w,其pred[w]值是-1。 假设 此算法适用于有向图和无向图。

    • · 查看原书依据

      存储器空间。广度优先搜索保证能够为图中的顶点寻找到最短路径。事实上,广度优先树中的所有路都是从源点s的最短路径(以边数来说)。

    • · 查看原书依据

      C++实现。广度优先搜索在栈中存储其状态,因此不需要任何的递归调用。 例6-2:广度优先搜索实现

    • · 查看原书依据

      O(V+E)。

    • · 查看原书依据

      最短路径。广度优先搜索保证如果存在一条到目标状态的路径,那么找到的肯定是最短路径。 图 7-8 广度优先搜索详解 事实上,深度优先搜索和广度优先搜索的唯一不同就是广度优先搜索使用队列来保存开放集,而深度优先搜索使用栈。每次迭代时,广度优先搜索从队列头拿出一个未访问的状态,然后从这个状态开始,计算后继

    • · 查看原书依据

      开销最小的路径(或者只是输出是否存在一个解)。

    • · 查看原书依据

      所需时间会非常长。而且,这个算法可能不适合寻找从初始状态到目标状态的多条路径(例如我们并不需要寻找绝对最短路径)。

    • · 查看原书依据

      闭合集用散列表结构存储。每个棋面状态都有一个回链,叫做过渡(Transition),这个链接记录的是得到当前棋面状态的走法以及前一个状态的引用。广度优先搜索多次复制一个棋面状态,用来尝试各种走法。 例7-4:广度优先搜索实现

    • · 查看原书依据

      规模很大的开放集。不过,让我们感到宽心的是,由于使用的队列来存储开放集合,所以插入和删除操作能够在常数时间完成。

    • · 查看原书依据

      开放集合的规模上有不同。广度优先搜索需要在开放集合中顺序存储bd个棋面状态,b是棋面状态的分支因子,d是找到的解的深度。开放集合的规模比深度优先搜索大得多,深度优先搜索的开放集合只需要存储b×d个棋面状态,即深度d时候的候选棋面状态数量。不过广度优先搜索能够保证找到一个解,从初始状态开始到目标状态,

    参考来源

    - 位置:《算法技术手册》第6章《广度优先搜索》(spine1570;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1533.html;u154-ch06-007)。 - 结论依据:154全文、03288伪代码和03289状态图实读。 - 原始内容:广度优先搜索 广度优先搜索(图6-11)使用了和深度优先搜索一种不同的方法来搜索图。广度优先搜索系统地在图中搜索顶点,在搜索离源点s的距离为k+1条边的顶点之前,所有的离源点s距离为k条边的顶点都已经被访问。广度优先搜索不会访问图中那些源点不可达的顶点。 广度优先搜索不会进行任何回溯。我们可以通过查 - 位置:《算法技术手册》第6章《输入/输出》(spine1570;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1533.html;u155-ch06-007)。 - 结论依据:155指出dist[v]是边数最短距离,pred[v]是前驱;源点和不可达点都可能有pred=−1,因此应结合距离或访问状态判断可达。 - 原始内容:dist[v]是从s到v的最短路径上的边数。pred[v]是在广度优先搜索中v的前驱顶点。根据pred[]的值,我们可以得到广度优先树,如果原始图是非连通的,那么对于所有源点不可达的顶点w,其pred[w]值是-1。 假设 此算法适用于有向图和无向图。 - 位置:《算法技术手册》第6章《使用环境》(spine1571;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1534.html;u156-ch06-007)。 - 结论依据:156强调队列的空间开销,最坏可达 O(V);最短指经过边数最少,适用有向或无向图。 - 原始内容:存储器空间。广度优先搜索保证能够为图中的顶点寻找到最短路径。事实上,广度优先树中的所有路都是从源点s的最短路径(以边数来说)。 - 位置:《算法技术手册》第6章《解决方案》(spine1572;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1535.html;u157-ch06-007)。 - 结论依据:157正文称在栈中存储状态,但03290实际使用 queue:取front,处理邻点后pop,新顶点在push前标灰。该先进先出顺序对分层和最少边数保证至关重要;示例没有显式检查源点索引。 - 原始内容:C++实现。广度优先搜索在栈中存储其状态,因此不需要任何的递归调用。 例6-2:广度优先搜索实现 - 位置:《算法技术手册》第6章《分析》(spine1573;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1536.html;u158-ch06-007)。 - 结论依据:158分析每个顶点至多入队一次,扫描所有可达顶点的邻接项;加上全图初始化,在邻接表与常数时间队列操作下为 O(V+E)。邻接矩阵通常需要 O(V²) 扫描。 - 原始内容:O(V+E)。 - 位置:《算法技术手册》第7章《广度优先搜索》(spine1597;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1560.html;u188-ch06-007)。 - 结论依据:188把BFS应用于状态空间;在有限分支、每步相同代价且状态去重正确时,首次发现目标得到最少步数。开放集和闭合集都需要考虑重复状态;图03335的伪代码只查closed,开放集中仍可能存在重复项。 - 原始内容:最短路径。广度优先搜索保证如果存在一条到目标状态的路径,那么找到的肯定是最短路径。 图 7-8 广度优先搜索详解 事实上,深度优先搜索和广度优先搜索的唯一不同就是广度优先搜索使用队列来保存开放集,而深度优先搜索使用栈。每次迭代时,广度优先搜索从队列头拿出一个未访问的状态,然后从这个状态开始,计算后继 - 位置:《算法技术手册》第7章《输入/输出》(spine1597;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1560.html;u189-ch06-007)。 - 结论依据:189将BFS输出称作开销最小;这需要每步相同代价,否则最少步数不一定最小成本,可考虑统一代价搜索等方法。 - 原始内容:开销最小的路径(或者只是输出是否存在一个解)。 - 位置:《算法技术手册》第7章《使用环境》(spine1598;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1561.html;u190-ch06-007)。 - 结论依据:190提醒逐层搜索可能耗费大量时间和空间;可否寻找多个路径取决于是否保留多个前驱和具体目标,而非队列结构本身。 - 原始内容:所需时间会非常长。而且,这个算法可能不适合寻找从初始状态到目标状态的多条路径(例如我们并不需要寻找绝对最短路径)。 - 位置:《算法技术手册》第7章《解决方案》(spine1599;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1562.html;u191-ch06-007)。 - 结论依据:191图03338–03339只在出队后加入closed且生成时只检查closed,同一状态可能多次进入open;可在首次入队时记录已发现状态以避免重复,并保存该次最短前驱。 - 原始内容:闭合集用散列表结构存储。每个棋面状态都有一个回链,叫做过渡(Transition),这个链接记录的是得到当前棋面状态的走法以及前一个状态的引用。广度优先搜索多次复制一个棋面状态,用来尝试各种走法。 例7-4:广度优先搜索实现 - 位置:《算法技术手册》第7章《结论》(spine1600;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1563.html;u192-ch06-007)。 - 结论依据:192强调队列空间;队列操作、状态复制、哈希和相等比较分别有成本,不能仅依据入队出队常数就忽略其他开销。 - 原始内容:规模很大的开放集。不过,让我们感到宽心的是,由于使用的队列来存储开放集合,所以插入和删除操作能够在常数时间完成。 - 位置:《算法技术手册》第7章《分析》(spine1601;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1564.html;u193-ch06-007)。 - 结论依据:193以分支因子b和解深度d估计BFS边界可达 O(b^d),纯深度优先路径栈可为 O(bd);但若DFS维护全局闭合集,其总空间可能随已访问状态数增长,不能一概写 O(bd)。 - 原始内容:开放集合的规模上有不同。广度优先搜索需要在开放集合中顺序存储bd个棋面状态,b是棋面状态的分支因子,d是找到的解的深度。开放集合的规模比深度优先搜索大得多,深度优先搜索的开放集合只需要存储b×d个棋面状态,即深度d时候的候选棋面状态数量。不过广度优先搜索能够保证找到一个解,从初始状态开始到目标状态,