回溯法思想 o第一步:为问题定义一个状态空间 state space), 这个空间必须至少包含问题的一个解 ◇第步;组织状奩空间以便它能被容易地搜索。典 型的组织方法是图或树 ◇第三步:按深度优先的方法从开始结点进行搜索 开始结点是一个活结点(也是E结点: expansion node 如果能从当前的E结点移动到一个新结点,那么这个新 结点将变成一个活结点和新的E结点,旧的E结点仍是 个活结点。 如果不能移到一个新结点,当前的E结点就“死”了 即不再是一个活结点),那么便只能返回到最近被考 察的活结点(回溯),这个活结点变成了新的E结点。 当我们已绎找到了答案或者回溯尽了所有的活结点时, 搜索过程结束。回溯法思想 第一步：为问题定义一个状态空间(state space)， 这个空间必须至少包含问题的一个解 第二步：组织状态空间以便它能被容易地搜索。典 型的组织方法是图或树 第三步：按深度优先的方法从开始结点进行搜索 ◼ 开始结点是一个活结点（也是 E-结点：expansion node） ◼ 如果能从当前的E-结点移动到一个新结点，那么这个新 结点将变成一个活结点和新的E-结点，旧的E-结点仍是 一个活结点。 ◼ 如果不能移到一个新结点，当前的E-结点就“死”了 （即不再是一个活结点），那么便只能返回到最近被考 察的活结点（回溯），这个活结点变成了新的E-结点。 ◼ 当我们已经找到了答案或者回溯尽了所有的活结点时， 搜索过程结束