4
生成问题状态的基本方
法
扩展结点 : 一个正在产生儿子的结点称为扩展结点
活结点 : 一个自身已生成但其儿子还没有全部生成的节
点称做活结点
死结点 : 一个所有儿子已经产生的结点称做死结点
深度优先的问题状态生成法:如果对一个扩展结点 R ,
一旦产生了它的一个儿子 C ,就把 C 当做新的扩展结
点。在完成对子树 C (以 C 为根的子树)的穷尽搜索
之后,将 R 重新变成扩展结点,继续生成 R 的下一个
儿子(如果存在)
宽度优先的问题状态生成法:在一个扩展结点变成死结
点之前,它一直是扩展结点
回溯法:为了避免生成那些不可能产生最佳解的问题状
态,要不断地利用限界函数 (bounding function)
来处死那些实际上不可能产生所需解的活结点,以减少
问题的计算量。具有限界函数的深度优先生成法称为回
溯法
第 3 页 / 共 20 页