第五章 回溯法 2021/2/21 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 1 第五章 回溯法
用计算机求解问题 C间题空间、现实求解过程C实际 状态空 机器求解过程机内解 对象的定义算法与程序的设计 2021/221 计算机算法设计与分析 2
2021/2/21 计算机算法设计与分析 2 用计算机求解问题 问题空间 现实求解过程 实际 解 状态空间 对象的定义 机器求解过程 算法与程序的设计 机内解
计算机求解的过程 ■在状态空间寻找机内解可以看成是从初始状态 出发搜索目标状态(解所在的状态)的过程。 初始状态 搜索 目标状态 状态空间 ■搜索的过程可描述为:S→S1→…→Sn,其中 S0为初态,Sn为终态。或者说v(S0)且φ(Sn,这 里v称为初始条件,φ称为终止条件。 2021/221 计算机算法设计与分析 3
2021/2/21 计算机算法设计与分析 3 计算机求解的过程 ◼ 在状态空间寻找机内解可以看成是从初始状态 出发搜索目标状态(解所在的状态)的过程。 状态空间 初始状态 搜索 目标状态 ◼ 搜索的过程可描述为：S0S1…Sn，其中 S0为初态，Sn为终态。或者说ψ(S0 )且φ(Sn )，这 里ψ称为初始条件，φ称为终止条件
求解是状态空间的搜索 ■求解的过程可以描述为对状态空间的搜索 其中S0为初始状 态,不妨设Sn为 终止状态 于是问题的求解就是通过搜索寻找出一条从初 始状态S到终止状态Sn的路径。 2021/22 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 4 求解是状态空间的搜索 ◼ 求解的过程可以描述为对状态空间的搜索 S0 S11 S12 … S1k … … … … … … Sn1 …… Sni …… Snm 其中S0为初始状 态，不妨设Sni为 终止状态 S0 Sni ◼ 于是问题的求解就是通过搜索寻找出一条从初 始状态S0到终止状态Sni的路径
0-1背包问题的状态空间树 ■下面是第三章的0-1背包问题的状态空间树 0 010 对应第三章的例子中的终止状态为S01 2021/221 计算机算法设计与分析 5
2021/2/21 计算机算法设计与分析 5 0-1背包问题的状态空间树 ◼ 下面是第三章的0-1背包问题的状态空间树： SI 0 S0 1 S1 0 S00 1 S01 0 S10 1 S11 0 S000 1 S001 0 S010 1 S011 0 S100 1 S101 0 S110 1 S111 ◼ 对应第三章的例子中的终止状态为S011。 S0 S01 S011