算法设计与分析_总结0

给出字符集和对应的频率，能够画出对应的哈夫曼树，并对给定的字符串进行哈夫曼编码。（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 2. const int N=5;

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）然后按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的限界函数的可能取值；