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