回溯法递归回溯算法步骤符号约定-辽宁师范大学.ppt

0-1背包问题的描述 0-1背包问题的回溯解法(1) 0-1背包问题的回溯解法(2) 0-1背包问题的回溯解法(3) 最大团问题的描述 最大团问题的回溯算法(1) 最大团问题的回溯算法(3) 计算复杂度分析 计算最优解时需要O(n)的复杂度 解空间树共有O(2n)个叶结点 T(n)=O(n2n) 概述 装载问题 批处理作业调度 n后问题 0-1背包问题 最大团问题 图的着色问题 图的m着色问题的描述 问题描述 给定无向连通图G和m种不同的颜色,用这些颜色为图G的各顶点着色,每个顶点着一种颜色.是否有一种着色法使G中每条边的2个顶点着不同颜色.这个问题是图的m可着色判定问题 若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色,则称数m为该图的色数 求图的色数的问题称为图的m可着色优化问题 概述 装载问题 批处理作业调度 n后问题 0-1背包问题 最大团问题 图的着色问题 图的m着色问题的回溯算法(1) 符号约定 a表示无向连通图G的邻接矩阵 顶点i所着的颜色用x[i]表示 问题的解空间是一棵高度为n+1的完全m叉树 概述 装载问题 批处理作业调度 n后问题 0-1背包问题 最大团问题 图的着色问题 图的m着色问题的回溯算法(2) 算法步骤 概述 装载问题 批处理作业调度 n后问题 0-1背包问题 最大团问题 图的着色问题 图的m着色问题的回溯算法(3) 计算复杂度分析 解空间树共有mn个叶结点 检查每个结点的颜色可用性需要O(n)的复杂度 T(n)=O(nmn) 概述 装载问题 批处理作业调度 n后问题 0-1背包问题 最大团问题 图的着色问题 辽宁师范大学计算机与信息技术学院 宋传鸣 《算法设计与分析》 回溯法 宋传鸣 算法设计与分析 辽宁师范大学计算机与信息技术学院 计算机科学与技术专业课程 chmsong@lnnu.edu.cn Algorithm Design and Analysis 回溯法,古来有之 诗经·秦风·蒹葭 概述 装载问题 批处理作业调度 n后问题 0-1背包问题 最大团问题 图的着色问题 回溯法,古来有之 诗经·秦风·蒹葭 概述 装载问题 批处理作业调度 n后问题 0-1背包问题 最大团问题 图的着色问题 回溯法的基本思想 在问题的解空间树中按深度优先策略,从根结点出发有哪些信誉好的足球投注网站解空间树.当遍历至某一结点时,先判断该结点是否包含问题的解 如果肯定不包含,则跳过对其子树的有哪些信誉好的足球投注网站,逐层向其祖先结点回溯 否则,继续以深度优先顺序遍历以该结点为根的子树 概述 装载问题 批处理作业调度 n后问题 0-1背包问题 最大团问题 图的着色问题 回溯法框架:以旅行售货员问题为例(1) 问题描述:某个售货员要到若干城市推销商品,已知各个城市之间的路程,他要选定一条从驻地出发,经过每个城市一遍,最后回到驻地的路线 目标:使总的路线最短 形式化描述:给定一个带权图G=(V,E),寻找G的一条包含V中所有顶点的回路,使其总代价最小 回溯法求解过程 定义解空间,并将其组织成树或图的形式 以深度优先方式有哪些信誉好的足球投注网站解空间,在有哪些信誉好的足球投注网站过程中用剪枝函数避免无效有哪些信誉好的足球投注网站 递归回溯 迭代回溯 概述 装载问题 批处理作业调度 n后问题 0-1背包问题 最大团问题 图的着色问题 回溯法框架:以旅行售货员问题为例(2) 递归回溯:用递归函数实现回溯 f(n,t)和g(n,t)表示在当前扩展结点处未有哪些信誉好的足球投注网站过的子树的起始和终止编号 h(i)表示在当前扩展结点处x[i]的第i个可选值 Constraint(t)表示约束函数 Bound(t)表示限界函数 概述 装载问题 批处理作业调度 n后问题 0-1背包问题 最大团问题 图的着色问题 回溯法框架:以旅行售货员问题为例(3) 迭代回溯:用树的非递归深度优先遍历实现回溯 概述 装载问题 批处理作业调度 n后问题 0-1背包问题 最大团问题 图的着色问题 回溯法框架:以旅行售货员问题为例(4) 具体算法 bestx表示当前最优解,bestc表示当前最优值,cc表示当前费用,x表示当前解 概述 装载问题 批处理作业调度 n后问题 0-1背包问题 最大团问题 图的着色问题 回溯法框架:以旅行售货员问题为例(5) 计算复杂度分析 若解空间树的高度为n,则树叶结点的数目有(n-1)! 若采用全有哪些信誉好的足球投注网站,T(n)=O((n-1)!) 概述 装载问题 批处理作业调度 n后问题 0-1背包问题 最大团问题 图的着色问题 装载问题的描述 问题描述 有一批n个集装箱要装上2艘载重量为c1和c2的轮船,其中集装箱i的重量为wi,且 目标:确定一个合理的方案,将n个集装箱装上2艘船 形式化描述 给定