四川理工学院算法剖析.pptx

第八章 分枝-限界法;分支限界法离不开对问题状态空间树的搜索基本搜索方法是先进先出FIFO搜索它类似BFS或者是后进先出LIFO搜索它类似于DFS FIFO搜索法与LIFO搜索法的定义如下对当前E-结点先从左至右地产生它的儿子用限界函数对这些儿子进行检查如果不是死结点就将它放入活结点表中然后从活结点表中依次取出一个结点作为E-结点在生成问题的状态的方法中需要一张活结点表对E-结点检索完毕之后检测以