第5章-回溯法教案资料.pptVIP

第5章-回溯法;问题的解空间复杂问题的求解复杂;问题的解向量：问题的解可以表示;问题的解空间问题的解空间由笛卡;两类典型的解空间两类典型的解空;子集树例1：集合A＝{a1,a;子集树例1：可以用一棵满二叉树;子集树例2：0-1背包问题分析;子集树可以用一棵满二叉树表示解;子集树子集树（SubsetT;子集树所以：解空间有2n个元素;排列树排列树（Permutat;排列树所以：解空间有n!个元素;排列树例：旅行商问题问题提出：;123433334444222;回溯法的基本思想回溯法回溯法是;回溯法的基本思想主要应用解决一;1.基本思想设问题的解可表示为;回溯法的基本思想2.求解过程求;回溯法的基本思想3.回溯法解题;例：排列与组合计算排列数如何;例：排列与组合计算组合数;例：排列与组合计算组合数：找;例：排列与组合分析：设（x1;算法的框架递归回溯的一般框架v;算法的框架一般来说，非递归回溯;算法的框架迭代回溯的一般框架v;小结回溯法解题的特征在深度优先;小结避免无效有哪些信誉好的足球投注网站的策略回溯法搜;5.2回溯法的典型用例几个应;应用专题一图问题中的回溯法例1;例1：n后问题问题描述：在n×;例1：n后问题例如：8×8棋;分析：解向量：(x1,x2,;例1：n后问题法1：4后问题;法2：4后问题的解空间（排列树;排列树的算法框架遍历排列树需要;例2：图的m着色问题问题描述：;例2：图的m着色问题分析：本题;例2：图的m着色问题数据结构:;例2：图的m着色问题例如：12;例2：图的m着色问题分析：解向;例3：TSP问题问题提出：分;例3：TSP问题分析： 解向;例3：TSP问题回溯法的求解;算法设计参考程序Travle.;应用专题二组合问题中的回溯法子;子集树的算法框架遍历子集树需O;例1：子集问题问题描述集合A＝;例2：0-1背包问题问题描述：;解空间：子集树可行性约束函数：;例如：n=3,c=30,w=(;例2：0-1背包问题参考程序;例如：n=3,c=30,w=(;问题：如何设计限界函数Boun;例3：符号三角形问题问题描述下;例3：符号三角形问题一般情况下;例3：符号三角形问题分析解向量;例3：符号三角形问题解空间由于;应用专题三其他应用例1：批处理;例1：批处理作业调度问题问题描;例1：批处理作业调度问题例如：;例1：批处理作业调度问题分析：;??2：工作安排问题问题描述设有;例2：工作安排问题分析：思路：;例3：整数的划分问题问题提出：;例3：整数的划分问题例如：整数;分析解向量x=(x1,x2;例4：棋盘覆盖问题问题描述：在;例如：554453342311;例4：棋盘覆盖问题考虑几个问题;例5：八数码难题问题描述：求解;无标题;例6：迷宫问题问题描述问题分析;例7：马踏棋盘问题问题描述在;例如：6×6132291871;例如：16×161182372;5.3回溯法效率分析影响回溯;解向量中分量排列顺序的影响重排;解空间：{(x1,x2,;5.3回溯法效率分析解空间树;本章小结本章小结回溯法的设计思;此课件下载可自行编辑修改，仅供