【算法复习二】传统基本算法（贪心、动态规划、回溯和分支限界）

一，贪心算法的设计思想

•从问题的某一个初始解出发逐步逼近给定的目标，每一步都作一个不可回溯的决策,尽可能地求得最好的解。当达到某算法中的某一步不需要再继续前进时，算法停止。

二，贪心算法的基本性质

1）贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心法与动态规划法的主要区别。

2）最优子结构性质

该问题解的整体最优性依赖于其局部子问题解的最优性。这种性质是可以采用贪心算法解决问题的关键特征。例如，活动安排问题，在选择了一项活动后，它必须是最优的，否则不能得到全局的最优。

三，贪心算法的适用性

•贪心算法对问题只需考虑当前局部信息就要做出决策，也就是说使用贪心算法的前提是“局部最优策略能导致产生全局最优解”。

•该算法的适用范围较小,若应用不当,不能保证求得问题的最佳解。更准确的方法是通过数学方法证明问题对贪心策略的选用性。

四，绝对贪心问题

例一：Dijkstra单源最短路径问题(有向图)

(Dijkstra)算法思想

　　按路径长度递增次序产生最短路径算法：

　　把V分成两组：

　　（1）S：已求出最短路径的顶点的集合

　　（2）V-S=T：尚未确定最短路径的顶点集合

　　 将T中顶点按最短路径递增的次序加入到S中

　　 保证：1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度

　　 2）每个顶点对应一个距离值

　　S中顶点：从V0到此顶点的最短路径长度

　 T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度

　　依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和

　

　　求最短路径步骤

　　算法步骤如下：

　　1. 初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值

　　若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值

　　若不存在<V0,Vi>，d(V0,Vi)为∝

　　2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S

　　3. 对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值

　　重复上述步骤2、3，直到S中包含所有顶点，即S=T为止

辅助数组：dist[ ] 存放V0到T中点距离

path[ ]存放已经加入S中点到V0最短路径

例二：Kruskal最小生成树问题(每次选权值最小边，直到生成一个最小生成树)

算法的运行时间为O(nlogn)。

源码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_NAME 5
#define MAX_VERTEX_NUM 20 
typedef char Vertex[MAX_NAME];/*顶点名字串*/
typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接距阵*/
struct MGraph/*定义图*/
{
 Vertex vexs[MAX_VERTEX_NUM]; 
 AdjMatrix arcs; 
 int vexnum,arcnum; 
};

typedef struct
{ 
  Vertex adjvex; /*当前点*/
  int lowcost;    /*代价*/
}minside[MAX_VERTEX_NUM];

int LocateVex(MGraph G,Vertex u)//定位
{ 
  int i;
  for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vexs[i])==0)return i;
  return -1;
}

void CreateGraph(MGraph &G)
{
  int i,j,k,w;
  Vertex va,vb;
  printf("请输入无向网G的顶点数和边数(以空格为分隔)\n");
  scanf("%d %d",&G.vexnum,&G.arcnum);
  printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME);
  for(i=0;i<G.vexnum;++i) /* 构造顶点集*/
    scanf("%s",G.vexs[i]);
  for(i=0;i<G.vexnum;++i) /*初始化邻接矩阵*/
    for(j=0;j<G.vexnum;++j)
      G.arcs[i][j]=0x7fffffff; 
  printf("请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): \n",G.arcnum);
  for(k=0;k<G.arcnum;++k)
  {
    scanf("%s%s%d%*c",va,vb,&w); 
    i=LocateVex(G,va);
    j=LocateVex(G,vb);
    G.arcs[i][j]=G.arcs[j][i]=w; /*对称*/
  }
}
 void kruskal(MGraph G)
 {
   int set[MAX_VERTEX_NUM],i,j;
   int k=0,a=0,b=0,min=G.arcs[a][b];
   for(i=0;i<G.vexnum;i++)
     set[i]=i;
   printf("最小代价生成树的各条边为:\n");
   while(k<G.vexnum-1) 
   { 
     for(i=0;i<G.vexnum;++i)
       for(j=i+1;j<G.vexnum;++j)
       if(G.arcs[i][j]<min)
       {
         min=G.arcs[i][j]; 
         a=i; 
         b=j; 
       }
     min=G.arcs[a][b]=0x7fffffff; 
     if(set[a]!=set[b])
     {
       printf("%s-%s\n",G.vexs[a],G.vexs[b]); 
       k++; 
       for(i=0;i<G.vexnum;i++)
         if(set[i]==set[b]) 
           set[i]=set[a];
     }
   }
 }

int main()
 {
   MGraph g;
   CreateGraph(g); 
   kruskal(g); 
   system("PAUSE");
   return 0;
 }
/*结果如下
请输入无向网G的顶点数和边数(以空格为分隔)
6 10
请输入6个顶点的值(<5个字符):
v1
v2
v3
v4
v5
v6
请输入10条边的顶点1 顶点2 权值(以空格作为间隔):
v1 v2 6
v1 v3 1
v1 v4 5
v2 v3 5
v2 v5 3
v4 v3 5
v4 v6 2
v3 v5 6
v3 v6 4
v5 v6 6
最小代价生成树的各条边为:
v1-v3
v4-v6
v2-v5
v3-v6
v2-v3
请按任意键继续. . .
*/

五，相对贪心问题

例一，取数游戏。

•问题描述

有2个人轮流取2n个数中的n个数，取数之和大者为胜。设计算法，让先取数者获胜，模拟取数过程。

•问题分析

这个游戏一般假设取数者只能看到2n个数中两边的数（第一次取时，能看到6,5则取6）,用贪心算法的情况:

•例如

若一组数据为：6,16,27,6,12,9,2,11,6,5

用贪心策略每次两人都取两边的数中较大的一个数,先取者胜.以A先取为例：

取数结果为：

A6,27,12,5,11=61胜

B16,6,9,6,2=39

•但若选另一组数据：16,27,7,12,9,2,11,6

仍都用贪心算法，先取者A败。

取数结果为：

A16,7,9,11=43

B 27,12,6,2=47胜

其实，若我们只能看到两边的数据，则此题无论先取还是后取都无必胜的策略。这时一般的策略是用近似贪心算法。

但若取数者能看到全部2n个数，则此问题可有一些简单的方法，有的虽不能保证所取数的和是最大，但确是一个先取者必胜的策略。

六，动态规划（各个问题包含公共子问题）

1）最优决策原理：要求问题具有最优子结构（即最优解包含子问题的最优解），是一种自底向上的求解思路，与递归正好相反，每次求解到一个阶段时，该阶段求解所依赖的子问题已经完全求解完毕，因此每一步的求解都是在直到全部所需信息的情况下进行的，因此可以得到全局最优解。

2）动态规划的决策过程：最优决策是在最后阶段形成的，然后向前倒推，直到初始阶段；而决策的具体结果及所产生的状态转移，却是由初始阶段开始进行计算的，然后向后递归或迭代，直到最终结果。

3）适用条件

　　 任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。

　　 1.最优化原理（最优子结构性质） 最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

　　 2.无后效性：将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。

　　 3.子问题的重叠性：动态规划将原来具有指数级复杂度的搜索算法改进成了具有多项式时间的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。 动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法

例题：著名的货郎担（旅行售货商）问题

详细解答参见博文------货郎担（旅行售货商）

七，回溯

1）设计思想

回溯与分支限界技术实际上都是基于穷举方法的，即按照一定规律，把问题所有可能的解组织成某种树结构，形成可能的解空间树或状态空间树。然后按照具体问题的约束条件，通过各种搜索策略，遍历可能的解空间树。从而得到满足问题条件的解或最优解。两种算法设计思路相近、本质一致。

2）回溯与分支限界法解决实际问题，大致可分为四个环节：

（1）确定问题的可能解空间，相当于找出进行穷举的搜索范围。

（2）以一种便于搜索的方式组织所有的可能解，一般是生成可能解空间树。

（3）以某种方式搜索可能的解空间树，有两种基本搜索方式。即：深度优先搜索方式和，这就是回溯技术；广度优先搜索，就是分支限界技术。

（4）在搜索过程中利用判定函数，也称为限界函数，通过“剪枝”来加速搜索过程。

3）回溯法的设计原理

按照深度优先搜索的方式，从根结点出发搜索状态空间树。

• 每搜索到达状态空间树的一个扩展结点，总是先判断以该结点为根的子树是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的进一步搜索，该结点成为一个死结点，同时应向上层回溯至最近的一个活动结点。再以该活动结点作为当前新的扩展结点。以这种方式递归地在解空间中搜索，直至找到问题的解，或者解空间中已无活动结点为止，即此问题无解。

• 在回溯法中，为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数来处死那些实际上不可能产生所需解的活动结点，以减少问题的计算量。所以，回溯法应是具有限界函数的深度优先搜索法。

用回溯法解题时，常遇到两类典型的解空间树，子集树与排列树。

例题：著名的八皇后问题

详细解答参见博文------八皇后问题

八，分支限界（求问题在某种意义下的最优解）

1）分支限界法的设计原理

分支限界法类似于回溯法，也是一种在问题的状态空间树上搜索解的算法。但是，分支限界法与回溯法有不同的求解目标。回溯法的求解目标是找出状态空间树中的所有回答结点或任一回答结点，分支限界法的求解目标则是找出使得某一目标函数达到极小或极大的一个问题结点。

2）分支限界法与回溯法有两点不同：

（1）求解目标不同。回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解或最优解。

（2）搜索方式不同。回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

3）常见的两种分支限界法

（1）队列式(FIFO)分支限界法
按照队列先进先出（FIFO）原则选取下一个结点为扩展结点。
（2）优先队列式分支限界法
按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。
4）常见问题

装箱问题、布线问题、单源最短路径问题、最大团问题、0-1背包问题、旅行售货问题