宽度优先搜索

宽度优先搜索

宽度优先搜索就是把OPEN表中的结点按照搜索树种结点深度的递增顺序排序，深度最小
的结点排在最前面，深度相同的结点可以任意排列。这样的搜索方式称为宽度优先搜索。与
深度优先方式相比，对不同的具体问题，搜索的效率是不同的。但宽度优先搜索可以保证找
到一条最短长度的路径，只要这条路径是存在的。
集束搜索(beam search)是宽度优先搜索的一个变型。该方法对OPEN表中具有同一深度
的结点只扩展其中的W个，放弃其它的结点。这个方法比宽度优先方法缩小了搜索空间，因
此提高了效率。