第5章 节 回溯法 算法设计与分析电子教案.ppt

第5章 回溯法;回溯法;问题的解空间;生成问题状态的基本方法;回溯法的基本思想;子集树与排列树;装载问题;装载问题;批处理作业调度;批处理作业调度;符号三角形问题;符号三角形问题;n后问题;解向量：(x1, x2, … , xn) 显约束：xi=1,2, … ,n 隐约束： 1)不同列：xi?xj 2)不处于同一正、反对角线：|i-j|?|xi-xj|;0-1背包问题;最大团问题;最大团问题;进一步改进算法的建议;图的m着色问题;解向量：(x1, x2, … , xn)表示顶点i所着颜色x[i] 可行性约束函数：顶点i与已着色的相邻顶点颜色不重复。;旅行售货员问题;圆排列问题;圆排列问题;连续邮资问题;连续邮资问题;回溯法效率分析;重排原理