void bfs{ while(front<=rear) { //当队列非空时做,其中front和rear分别为头指针和尾指针 if(//找到目标状态) //做相应处理(如推出循环输出解、输出当前解、比较解得优劣); else{ //拓展头结点 if(//拓展出的新结点没有出现过(bool)) { rear++; //将新节点插到队尾; } } front++;//取下一个点 } }
搜索时计算机程序设计中的一种基本算法、最常用的算法;
宽度优先所搜:
又称为广度优先搜索。
它是从初始结点开始,应用产生式规则和控制策略生成第一层结点,同时检查目标结点是否在这些生成的节点中。若没有,再用产生式规则将所有第一层结点进一步扩展,得到第二层结点,并逐一检查第二层结点是否包含目标结点。若没有再用产生式规则拓展第二层结点。如此依次拓展,检查下去,直至发现目标结点为止。
如果拓展完所有结点,都没有发现目标结点,则问题无解。
宽度优先搜索是一种盲目的搜索,所有结点的拓展都遵循“先进先出”的原则,所以采用“队列”来存储这些状态。宽度优先搜索的基本框架就如同上面的代码。
如果只求任意一个解,也可以写成以下程序:
void bfs2{ p=true; while p do{ if(//头结点是目标状态) p=false; else{ //拓展头结点; if(//拓展出的新节点没有出现过) { rear++; //将新节点插到队尾 } front++; if(front>rear)p=false; } } }