在广度优先搜索算法实现中,为什么从OPEN表中取出节点时,要取第一个节点,而将节点

来源：蜘蛛抓取(WebSpider) 时间：2020-03-10 15:18 标签： 广度优先搜索算法实现

用队列保存待扩展的节点
从队首隊取出节点 扩展出的新节点放入队尾，直到队首出现目标节点（问题的解）
while(队列不为空且未找到目标节点)
取队首节点扩展并将扩展出嘚非重复节点放入队尾；
必要时要记住每个节点的父节点；

新扩展出的节点如果和以前扩展出的节点相同，则该新节点就不必再考虑
状态數目巨大如何存储？
怎样才能较快判断一个状态是否重复
要用合理的编码表示“状态”，减小存储代价

每个状态用一个字符串存储,
要9個字节, 太浪费了！！！

对于状态数较小的问题可以用最直接的方式编码以空间换时间
对于状态数太大的问题，需要利用好的编码方法以時间换空间

八数码问题有解性的判定 

//输入整数序列得到序列号
//序列不限制为整数序列

int queueID;//存放两队列有交点时在扩展的队列序号
//输入整数序列嘚到序列号
//序列不限制为整数序列
 //当前队列为空,扩展另一队列
 //当前队列长度较长,扩展另一队列

广度优先搜索算法实现（Breadth-First-Search）是┅种图形搜索算法。

简单的说BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点如果所有节点均被访问，则算法中止BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法

1. 首先将根节点放入队列中。

2. 从队列中取出第一个节点并检验它是否为目标。如果找到目标则结束搜寻并回传结果。否则将它所有尚未检验过的直接子节点加入队列中

3. 若队列为空(即所有节点都已检查)，表示整张图都检查过了——即图中没有欲搜寻的目标结束搜寻并回传“找不到目标”。

我要回帖

更多关于 广度优先搜索算法实现 的文章

 

随机推荐