广度优先搜索
每次将集合中的元素经过一些改动,分层生成当前状态的子状态(通常还删除父情况),添加到集合(队列)中,以实现遍历或搜索等目的的算法。
Pseudocode (用队列)
1 procedure(state)
2 for each possible next state from this one
3 enqueue next state
4 search()
5 enqueue initial state
6 while not empty(queue)
7 state->get state from queue
8 process(state)
基本思想
(1)建立一个空的状态队列SS;
(2)建立一个空的状态库SB;
(3)把初始状态S(0)存入队列SS中;
(4)若队列状态是目标状态,则搜索成功,算法运行中止。如该状态的形式为S(path),则解就是(path);
(5)若某种搜索极限已经达到(如空间用完等),则搜索失败,算法运行结束,没有解;
(6)按某种原则取一个可以应用于SS第一个状态S(path)并产生合适的新状态的规则Rn,产生新状态T(path,n),并将其置于SS的最后,转(4)。若扩展失败,即没有新状态产生,则将SS中第一个状态从SS中除去,送入SB中,执行下步;
(7)若SS成为空队列,则搜索失败,算法运行结束,没有解。否则转(5)。
------------------------------------------------------------------------------------------------------------------------------------------------------
BFS
Bryant Fullbody Slam
360度转体扣篮
以科比·布莱恩特命名的一种扣篮动作