[数据结构与算法]算法竞赛入门到进阶 读书笔记（6）

贪心法是将整个问题分解成多个步骤，在每个步骤都选取当前步骤的最优方案，直到所有步骤结束的方法。但它是求得局部最优解的方法，对于某些问题不一定能得到最优解。
贪心法的基本问题有区间重合，区间覆盖，性价比等问题，这就不过多叙述了，这次主要写一些贪心和其他思想结合的算法。

一、Huffman编码
Huffman编码是贪心和二叉树结合的算法，是"前缀"最优编码。
数据在计算机中都是用二进制码来表示的，一般的编码方式是把每个字符都用相同长度的二进制数来表示，这样并不是节省空间的最优方法，通过二叉树进行编码能够实现空间的优化。
具体是在每个二叉树分支上将左支设为0，右支设为1，把编码放在结点上。出现频次最高的字符放在最上面，频次最低的字符放在二叉树最深处，使频次越高的编码尽量越短来完成压缩。
例 poj 1521： 8bit
样例：AAAAABCD
首先先拿样例来说，A出现了五次，B\C\D各出现一次，A必须放在二叉树最深处，其余编码随意分配即可，这样便可得到：
A：0 B：10 C：110 D：111 因此通过二叉树长度压缩为了5+2+3+3=13 而原普通编码为8*8=64 完成了压缩
因为要计算并且排列相同字符，用优先队列比较好，首先要计算出各个字符的数量，核心思想为：

  for(int i=1;i<s.length();i++)
{ if(s[i]!=s[i-1]; { q.push(t); t=1;}
else t++;}
q.push(t);

这样就将每个字符的个数计算了出来，接下来在计算编码的总长度即可

while(q.size()>1)
{ int a=q.top();  q.pop();
int b=q.top(); q.pop();
q.push(a+b); 
ans +=a+b ;}  // 通过二叉树原理列出计算编码长度的式子

二、模拟退火
模拟退火算法是贪心思想和概率的结合，也是一种有着固定概念和套路的算法。
模拟退火算法基于温度越高的物体降温的概率越大这一原理随机选择下一状态，通过概率的方式使程序有机会摆脱局部最优解到达全局最优。
（1） 设置初始温度
（2） 温度下降，状态转移，并记下新的状态
（3） 温度下降到设定温度下界，程序停止
例： hdu 2899
计算函数F(x)=6x^7 +8x^6+ 7x^3+ 5x^2-yx的最小值
构建计算函数值的函数，使用pow即可计算次方，接下来就要按模板建立退火函数

  double solve()
{ double T=100;   //初始温度
 double delta=0.98; //降温系数
 double x=50.0; //初始值
 double now=plan(x); //计算初始值
 double ans=now;
 while(T>eps){
 int f[2]={1,-1}; //x增加、减少的两种情况
 double new=x+f[rand()%2]*T; //按照温度高低随机加减
 if(new>=0&&new<=100){ double next=plan(new);
 ans=min(ans,next);   //计算局部最优解
 if(now-next>eps){ x=new; now=next;}  //保留状态
 }
 T*=delta;  //退火降温
 } return ans;}

三、分治法
分治算法就是将原问题分成k个子问题，再对这些小问题分别求解，但这些子问题是相互独立的，不同于动态规划。
归并排序和快速排序是很经典的例子，二者都用到了折半查找的思想，不同的是归并排序只是将其分成了两半，而快速排序使得左边元素全都小于右边，因此快速排序在分解的过程中就已经是有序的了，它不需要合并，而归并排序的核心则是合并。
sort()函数就是基于快速排序算法并做了优化，这里就先不深挖这些排序方法的细节了。