算法设计与分析第五章回溯法.ppt

第5章 回溯法;;回溯法;问题的解空间;生成问题状态的基本方法;回溯法的基本思想;递归回溯;迭代回溯;子集树与排列树;0-1背包问题;01背包问题：n=3，w=[20，30,10]，p=[100，120，60]且C=50.;回溯法解决01背包问题;0-1背包问题;装载问题;装载问题;批处理作业调度;批处理作业调度;符号三角形问题;符号三角形问题;n后问题;解向量：(x1, x2, … , xn) 显约束：xi=1,2, … ,n 隐约束： 1)不同列：xi?xj 2)不处于同一正、反对角线：|i-j|?|xi-xj|;*;1 2 3 4 9 8 15 14 5 请按任意键继续. . . 1 2 3 4 9 14 15 8 5 请按任意键继续. . . 1 2 3 4 15 8 9 14 5 请按任意键继续. . . 1 2 3 4 15 14 9 8 5 ;*;找数? 【题目叙述】键盘输入n个正整数（互不相等），找出其中和等于m的数的组合。? 【输入输出样例】输入：5（m的值）?1?2?3?4?5? ???输出：1?4? ????????????????2?3? ?????????????????5? ;液晶数字问题?;最大团问题;最大团问题（Maximum Clique Problem, MCP）;*;*;*;*;;最大团问题;进一步改进算法的建议;图的m着色问题;解向量：(x1, x2, … , xn)表示顶点i所着颜色x[i] 可行性约束函数：顶点i与已着色的相邻顶点颜色不重复。;旅行售货员问题;旅行售货员问题;旅行售货员问题;旅行售货员问题;旅行售货员问题;圆排列问题;圆排列问题;连续邮资问题;连续邮资问题;回溯法效率分析;重排原理;课堂练习