贪心算法
- 当具有最优子结构性质的时候，可以使用动态规划算法也可以使用贪心算法
- 最优子结构性质、贪心选择性质
- 虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况之下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
活动安排问题
选出最大的相容活动子集Q
1. 动态规划方法
步骤一 : 分析最优子解的结构性质
- 最有最有子结构性质：某活动X包含在Q中，则X之前、之后的活动都是最优的
- 子问题的最优解可以构造出原问题的最优解
步骤二 : 递归的定义最优解
- 动态规划的灵魂（我的理解）在于二维数组，定义I,j进行遍历
- 设c[i, j]为Sij中最大兼容子集中的活动数
- Xk在最有优解中被使用，k的取值有j-i-1种可能
2. 贪心算法
贪心策略：
- 对活动的完成时间进行非减序排列
- 每次选择最早完成时间的活动加入最优解子集
- 贪心的意义在于：使得剩余安排时间最大化
3. 注解
- 贪心算法依赖于以往所做的选择，不依赖于未来的选择，也不依赖于子问题的解。动态规划采用的是自底向上，而贪心算法则是自顶向下，以迭代的方式相继求解。
- 贪心策略认为：最早结束的活动一定在最优解中。这是解决问题的核心。
4. 证明贪心算法可以构成最优解：
设E = {1,2,3,...,n}为所给的活动集合。由于E中活动按结束时间的非递减序列排列，故活动1具有最早完成时间。
首先证明，活动安排问题有一个最优解以贪心选择开始，即该最优解中包含活动1.设A∈E是所给的活动安排问题的一个最优解，且A活动也按结束时间非减序排列，A中的第一个活动是活动k。
若k=1，则A就是一个以贪心选择开始的最优解。
若k>1，则设B=(A-{k})U{1}。由于f1<=fk，且A中活动是相容的，故B中活动也是相容的。
又B中的活动个数与A中的活动个数相等，且A是最优的，所以，B也是最优的。
也就是说，B是一个贪心选择的最优解。
所以，总存在贪心选择的最优解。（贪心选择的证明）
5. 代码
template<class Type>
/*
Input:
n:活动的总数目
s[]: 每个活动的开始时间
f[]: 每个活动的结束时间
Output:
A[]: 最终活动选择结果，要则为1，不要则为0
*/
void GreedySelector(int n, Type s[], Type f[], bool A[])
{
A[1] = true;
int j = 1;
for(int i=2; i<=n; i++)
{
if(s[i] > = f[i])
{
A[i] = true;
j = i;
}
else
A[i] = false;
}
}
最优装载
1. 简短说明
排序，每次选择重量较轻的先装入
2. 代码
template<class Type>
/*
Input:
w[]: 第i集装箱的重量
c: 轮船的载货量
n: 集装箱整体的数量
Output:
x[]: 对于第i个集装箱是否装入的表示，1/0
*/
void Loading(int x[], Type w[], Type c, int n)
{
int * t = new int[n+1];
Sort(w, t, n);
for(int i=1; i<=n; i++) x[i]=0;
for(int i=1; i<=n && w[t[i]]<=c; i++) {x[t[i]]=1; c-=w[t[i]]}
}
哈夫曼编码
1. 相关解释
- 前缀码：0/1为串，每个字符的代码都不是其他字符的前缀，前缀码长度不均
- 哈夫曼树：又称最优二叉树，是一种带权路径长度最短的二叉树
- 表示最优前缀码的二叉树一定总是一棵完全二叉树，也就说每个结点都有2个儿子。一般情况下，若C是编码字符集，表示其最优前缀码的二叉树中有 |C| 个叶子，每个叶子对应于字符集中一个字符，|C|-1 个内部结点
2. 霍夫曼编码的具体步骤
- 将信源符号的概率按减小的顺序排队。
- 把两个最小的概率相加，并继续这一步骤，始终将较高的概率分支放在右边，直到最后变成概率1。
- 画出由概率1处到每个信源符号的路径，顺序记下沿路径的0和1，所得就是该符号的霍夫曼码字。
- 将每对组合的左边一个指定为0，右边一个指定为1（或相反）。
3. 代码
/*
Huffman类的定义
*/
template<class Type>
class Huffman
{
friend BinaryTree<int> HuffmanTree(Tree[], int);
//如果类A中的函数要访问类B中的成员（例如：智能指针类的实现），那么类A中该函数要是类B的友元函数
public：
operator Type () const {return weight;}
private:
BinaryTree<int> tree;
Type weight;
}
/*
算法HuffmanTree
*/
template<class Type>
BinaryTree<int> HuffmanTree(Type f[], int n)
{
//生成单结点树
Huffman<Type> * w = new Huffman<Tree> [n+1];
BinaryTree<int> z,zero;
for(int i=1; i<=n; i++)
{
z.MakeTree(i,zero,zero);
w[i].weight=f[i];
w[i].tree=z;
}
//建立优先队列
MinHeap<Huffman<Type>> Q(1);
Q.Initialize(w,n,n);
//反复合并最小频率树
Huffman<Type> x,y;
for(int i=1;i<n;i++)
{
Q.DeleteMin(x);
Q.DeleteMin(y);
z.MakeTree(0,x.tree,y,tree);
x.weight+=y.weight; x.tree=z;
Q.Insert(x);
}
Q.DeleteMin(x);
Q.Deactivate();
delete [] w;
return x.tree;
}
单源最短路径
1. Dijkstra算法
其基本思想是，设置 顶点集合S 并不断地作贪心选择来扩充这个集合。
一个顶点属于集合S当且仅当 从源到该顶点的最短路径长度 已知。
初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并 用数组dist记录当前每个顶点所对应的最短特殊路径长度 。
Dijkstra算法每次 从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。
一旦S包含了所有V中定点， dist就记录了从源到所有其他顶点之间的最短路径长度
2. 代码
template<class Type>
/*
Input:
n：结点个数
v: 源点
dist[i]: 尚未被扩充的顶点i 与 目标顶点集合的最短距离
pre[i]: 记录的是从源到顶点i的最短路径上的前一个顶点，初始时，对所有i!=1,置pre[i]=v
Type **c: c[i][j]表示边(i,j)的权
*/
void Dijkstra(int n, int v, Type dist[], int pre[], Type **c)
{
bool s[maxint]; //用于记录那些点已经记录，那些点还未记录
for(int i=1; i<=n; i++)
{
dist[i] = c[v][i];
s[i]=false;
if(dist[i] == maxint) prev[i]=0;
else prev[i]=v;
}
dist[v]=0; s[v]=true; //将源处理下
//如下的循环开始迭代
for(int i=1; i<=n; i++)
{
int temp = maxint;
int u = v;
for(int j=1; j<=n; j++) //筛选出最小dist[j]
{
if((!s[j])&&(dist[j]<temp)) //!s[j]:结点j还未被记录
{
u=j;
temp=dist[j];
}
}
s[u]=true;
for (int j = 0; j < n; j++)
{
if((!s[j])&&(c[u][j]<maxint))
{
Type newdit = dist[u]+c[u][j];
if(newdist<dist[j])
{
dist[j]=newdist;
prev[j]=u;
}
}
}
}
}
最小生成树
1. 最小生成树MST性质
设G=(V,E)是连通带权图，U是V的真子集。如果(u,v)∈E，且u∈U，v∈V-U，且在所有这样的边中，(u,v)的权c[u][v]最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质有时也称为MST性质。
2. Prime算法
- 设G=(V,E)是连通带权图，V={1,2,…,n}
- 首先置S={1}
- 选取满足条件i∈S，j∈V-S，且c[i][j]最小的边，将顶点j添加到S中
- 不断执行上一步，扩充S，直至S=V
- 最后，在这个过程中选取到的所有边恰好构成G的一棵最小生成树
3. Prime算法实现
/*
@http://blog.csdn.net/jnu_simba/article/details/8869876
*/
/* Prim算法生成最小生成树 */
void MiniSpanTree_Prim(MGraph MG)
{
int min, i, j, k;
int adjvex[MAXVEX];/* 保存相关顶点下标 */
int lowcost[MAXVEX];/* 保存相关顶点间边的权值 */
lowcost[0] = 0;/* 初始化第一个权值为0，即v0加入生成树 */
/* lowcost的值为0，在这里就是此下标的顶点已经加入生成树 */
adjvex[0] = 0;/* 初始化第一个顶点下标为0 */
cout << "最小生成树的边为：" << endl;
for (i = 1; i < MG.numVertexes; i++)
{
lowcost[i] = MG.arc[0][i];/* 将v0顶点与之有边的权值存入数组 */
adjvex[i] = 0;/* 初始化都为v0的下标 */
}
for (i = 1; i < MG.numVertexes; i++)
{
min = INFINITY; /* 初始化最小权值为∞， */
j = 1;
k = 0;
while (j < MG.numVertexes)/* 循环全部顶点 */
{
if (lowcost[j] != 0 && lowcost[j] < min)/* 如果权值不为0且权值小于min */
{
min = lowcost[j];/* 则让当前权值成为最小值 */
k = j;/* 将当前最小值的下标存入k */
}
j++;
}
cout << "(" << adjvex[k] << ", " << k << ")" << " "; /* 打印当前顶点边中权值最小的边 */
lowcost[k] = 0;/* 将当前顶点的权值设置为0,表示此顶点已经完成任务 */
for (j = 1; j < MG.numVertexes; j++)/* 循环所有顶点 */
{
/* 如果下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 */
if (lowcost[j] != 0 && MG.arc[k][j] < lowcost[j])
{
lowcost[j] = MG.arc[k][j];/* 将较小的权值存入lowcost相应位置 */
adjvex[j] = k;/* 将下标为k的顶点存入adjvex */
}
}
}
cout << endl;
}
4. Kruskal算法
- 首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。
- 然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：
- 当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。
- 这个过程一直进行到只剩下一个连通分支时为止。
5. Kruskal算法实现
/*
@http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html
*/
typedef struct
{
char vertex[VertexNum]; //顶点表
int edges[VertexNum][VertexNum]; //邻接矩阵,可看做边表
int n,e; //图中当前的顶点数和边数
}MGraph;
typedef struct node
{
int u; //边的起始顶点
int v; //边的终止顶点
int w; //边的权值
}Edge;
void kruskal(MGraph G)
{
int i,j,u1,v1,sn1,sn2,k;
int vset[VertexNum]; //辅助数组，判定两个顶点是否连通
int E[EdgeNum]; //存放所有的边
k=0; //E数组的下标从0开始
for (i=0;i<G.n;i++)
{
for (j=0;j<G.n;j++)
{
if (G.edges[i][j]!=0 && G.edges[i][j]!=INF)
{
E[k].u=i;
E[k].v=j;
E[k].w=G.edges[i][j];
k++;
}
}
}
heapsort(E,k,sizeof(E[0])); //堆排序，按权值从小到大排列
for (i=0;i<G.n;i++) //初始化辅助数组
{
vset[i]=i;
}
k=1; //生成的边数，最后要刚好为总边数
j=0; //E中的下标
while (k<G.n)
{
sn1=vset[E[j].u];
sn2=vset[E[j].v]; //得到两顶点属于的集合编号
if (sn1!=sn2) //不在同一集合编号内的话，把边加入最小生成树
{
printf("%d ---> %d, %d",E[j].u,E[j].v,E[j].w);
k++;
for (i=0;i<G.n;i++)
{
if (vset[i]==sn2)
{
vset[i]=sn1;
}
}
}
j++;
}
}
