清华大学出版社 回溯法的基本思想 1)针对所给问题,定义问题的解空间 (2)确定易于搜索的解空间结构 (3)以深度优先方式搜索解空间,并在搜索过程中 用剪枝函数避免无效搜索 常用剪枝函数: 用约束函数在扩展结点处剪去不满足约束的子树 用限界函数剪去得不到最优解的子树。 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的 解空间。在任何时刻,算法只保存从根结点到当前扩展结点的 路径。如果解空间树中从根结点到叶结点的最长路径的长度为 h(η),则回溯法所需的计算空间通常为O(h(η)。而显式地存储 整个解空间则需要○(2m)或O(h(η))内存空间。5 回溯法的基本思想 (1)针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构； (3)以深度优先方式搜索解空间，并在搜索过程中 用剪枝函数避免无效搜索。 常用剪枝函数： 用约束函数在扩展结点处剪去不满足约束的子树； 用限界函数剪去得不到最优解的子树。 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的 解空间。在任何时刻，算法只保存从根结点到当前扩展结点的 路径。如果解空间树中从根结点到叶结点的最长路径的长度为 h(n)，则回溯法所需的计算空间通常为O(h(n))。而显式地存储 整个解空间则需要O(2h(n))或O(h(n)!)内存空间