回溯法的基本概念 回溯法是一种选优搜索法（试探法），被称为通用的解题方法 3 基本思想：将n元问题P的状态空间E表示成一棵高为n的带权有序 树T,把在E中求问题P的解转化为在T中搜索问题P的解 3 解题方法：按选优条件对T进行深度优先搜索，以达到目标 从根结点出发深度优先搜索解空间树 当探索到某一结点时，要先判断该结点是否包含问题的解 如果包含，就从该结点出发继续按深度优先策略搜索 否则逐层向其祖先结点回溯（退回一步重新选择） 满足回溯条件的某个状态的点称为“回溯点” 算法结束条件： 求所有解：回溯到根，且根的所有子树均已搜索完成 求任一解：只要搜索到问题的一个解就可以结束回溯法的基本概念  回溯法是一种选优搜索法（试探法），被称为通用的解题方法  基本思想：将n元问题P的状态空间E表示成一棵高为n的带权有序 树T，把在E中求问题P的解转化为在T中搜索问题P的解  解题方法：按选优条件对T进行深度优先搜索，以达到目标  从根结点出发深度优先搜索解空间树  当探索到某一结点时，要先判断该结点是否包含问题的解 ━ 如果包含，就从该结点出发继续按深度优先策略搜索 ━ 否则逐层向其祖先结点回溯（退回一步重新选择） ━ 满足回溯条件的某个状态的点称为“回溯点”  算法结束条件： ━ 求所有解：回溯到根，且根的所有子树均已搜索完成 ━ 求任一解：只要搜索到问题的一个解就可以结束