博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
关于bfs时间轴
阅读量:5150 次
发布时间:2019-06-13

本文共 497 字,大约阅读时间需要 1 分钟。

对于bfs,由于是通过不断将平行位置的元素加入到队列进行的,所以它在一定情况下淡化了与队列外部的  "时间"   联系观念,通过一个数组记录内部的 "时间"

这样的优点是将队列的平行位置的时间化为了统一,而不用纠结到底先遍历哪个

但也有缺点,这样做队列外部的时间将会不能与队列内部同步,也就是说在队列内部的进行一步(即放入一个所有的平行位置元素),外部可能已经进行了很多步了

解决这样的缺点

方法一是将队列的每一步都进行彻底,从而达到内部统一,并且与外部统一的效果

具体做法是 在对队列内部元素进行下一步的扩张时,必须要把队列所有的元素都进行扩张完全,也就是完成了扩张那一步之后再进行队列外部的操作

如下所示,就是利用一个变量  t 将之前的元素个数size统计起来,通过while()将该阶段所有元素都扩张完全,再执行队列外部的变化,此时内外时间轴就统一了

方法二是利用内部的记录变量的值与变化来引导外部的过程(即 如内部记录数组的值+1时,外部再进行),从而使外部时间轴与内部统一

 

转载于:https://www.cnblogs.com/MekakuCityActor/p/8206768.html

你可能感兴趣的文章
转:JUnit使用指南
查看>>
C++面试题整理(持续更新中)
查看>>
vs2017 git到oschina 方法
查看>>
对Vue为什么不支持IE8的解释之一
查看>>
使用easyUI 为datagrid冻结列
查看>>
开发 web 桌面类程序几个必须关注的细节
查看>>
bzoj 2784: [JLOI2012]时间流逝【树形期望dp】
查看>>
Myeclipse10.7添加本地插件方法
查看>>
Swift - 将字符串拆分成数组(把一个字符串分割成字符串数组)
查看>>
coredata 数据库升级
查看>>
NSRange,判断字符串的各种操作~
查看>>
Java基本数据类型之间赋值与运算归纳
查看>>
Facebook开源软件列表
查看>>
Swift版音乐播放器(简化版),swift音乐播放器
查看>>
iOS中AutoLayer自动布局流程及相关方法
查看>>
聊一聊 Android 6.0 的运行时权限
查看>>
递归+分治+贪心+动态规划
查看>>
使用Git工具下载android源码---带步骤
查看>>
内容版本SecureCRT脚本
查看>>
宋体光标vim高亮显示当前行,列
查看>>