给出字符集和对应的频率，能够画出对应的哈夫曼树，并对给定的字符串进行哈夫曼编码。（P155-157）
第8章 回溯法
了解回溯法的设计思想
设计思想：从解空间树根结点出发，按照深度优先策略遍历解空间树，在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。直到搜索到叶子结点，则得到问题的一个可能解。 步骤：
确定解向量和分量的取值范围，构造解空间树； 确定剪枝函数；
对解空间树按深度优先搜索，搜索过程中剪枝；
从所有的可能解中确定最优解。
了解可以用回溯法解决的问题：
属于组合问题和排列问题中求最优解的问题都可以用回溯法解决，例如：图着色问题，哈密顿回路问题，八皇后问题（4皇后问题），批处理作业调度问题。
掌握m颜色图着色判定问题的回溯法算法，并能画出解空间树的搜索过程（P168-170），习题8-4
对图8.14使用回溯法求解图问题，画出生成的搜索空间。
解：图着色问题求解的是满足图着色要求的最小颜色数。对图8.14应该从1、2、3、4……种颜色依次尝试用回溯法判定是否满足M着色的要求。
经搜索，1种和2种颜色均不能满足图着色的要求，3种颜色可以满足图着色要求，搜索过程如下，所以图8.14的着色的最少颜色数应该为3 搜索空间为：
掌握n皇后问题的回溯法算法，并能画出解空间树的搜索过程（P173-174）, 自己看书
掌握0/1背包问题的回溯算法，并能画出解空间树的搜索过程（P163-164），习题8-5 自己看书
习题8-6，算法设计题。
给定一个正整数集合X={x1,x2,…, xn}和一个正整数y，设计回溯算法，求集合X的一个子集Y，使得Y中元素之和等于y。 解：
用回溯法求解问题分析： 该问题为求子集问题。
解分量的和小于y为剪枝函数。
当搜索到结点，并且解分量的和等于y时，找到问题的解。
1．X={x1,x2,x3……xn }，sum=0，Y={ }为解向量，初始化为全0; 2．flag=false; 3．k=1; 4．while (k>=1)
4.1 当(Sk取1、0)循环执行下列操作 4.1.1yk=Sk中的下一个元素; 4.1.2将yk加入Y; 4.1.3sum=+（yk?xk:0）;
4.1.4if (sum==y) flag=true; 转步骤5; 4.1.4else if (sum 1. #include 3. int f(int x[],int y[],int n) 4. { 5. //初始化y，y为所求的集合 6. for(inti=0;i 10. while(k>=0) 11. { 12. y[k]=y[k]-1; 13. if((y[k]==1||y[k]==0)&&k 17. if(sum 19. sum=sum-(y[k]?x[k]:0); 20. } 21. } 22. } 23. else{//回溯 24. // sum=sum-(y[k]?x[k]:0); 25. y[k]=2; 26. k--; 27. sum=sum-(y[k]?x[k]:0); 28. } 29. } 30. return k; 31. } 32. 33. void main() 34. { 35. int x[N]={2,1,3,4,2}; 36. int y[N]; //解向量 37. int n=12; //题目要求等于的和 38. int k=f(x,y,n);//k表示搜索到第几个元素 39. cout< 41. cout<<(y[i]==1?x[i]:0)< 第9章 分治限界法 了解分支限界法的设计思想 设计思想： 1）首先确定一个合理的限界函数，并根据限界函数确定目标函数的界[down, up] ，并确定限界函数； 2）然后按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的限界函数的可能取值；
相关推荐：
loading