典型算法思想与应用7｜贪心算法与最短路径问题

贪心法是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最优解。通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。

在对问题求解时，贪心法总是做出在当前看来是最好的选择。也就是说，暂时不从整体最优上加以考虑，当时所做出的仅是在某种意义上的局部最优解，然后把子问题的局部最优解合成原来问题的一个解，称为贪心法。

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关

1 总体思路

(1) 建立数学模型来描述问题。

(2) 把求解的问题分成若干个子问题。

(3) 对每一子问题求解，得到子问题的局部最优解。

(4) 把子问题的局部最优解合成原来问题的一个解。

2 贪心算法适用的问题

贪心策略适用的前提是：局部最优策略能导致产生全局最优解。实际上，贪心算法适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。

贪婪算法可解决的问题通常大部分都有如下的特性：

① 随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。

② 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。

③ 还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。

④ 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。

⑤ 最后，目标函数给出解的值。

为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪婪算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。

3 贪心算法的实现框架

从问题的某一初始解出发；while（能朝给定总目标前进一步）{ 利用可行的决策，求出可行解的一个解元素；}由所有解元素组合成问题的一个可行解；

4 贪心策略的选择

因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。

贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题 。

5 典型应用：最短路径问题

贪心算法有诸多典型应用，如马踏棋盘，求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。

Dijkstra 算法是解决单源最短路径问题的贪心算法，它先求出长度最短的一条路径，再参照该最短路径扩充和更新到其它各点的路径，直到求出从源点到其他各个顶点的最短路径。

Dijkstra算法的基本思想是首先假定源点为u，顶点集合V被划分为两部分：集合S和 V-S（用一个布尔数组表示）。初始时 S 中仅含有源点 u，其中 S 中的顶点到源点的最短路径已经确定。集合V-S中所包含的顶点到源点的最短路径的长度待定，称从源点出发只经过S中的点到达V-S中的点的路径为特殊路径，并用数组dist[]记录当前源点到每个顶点的最短路径长度。然后选择特殊路径长度最短的路径，将其连接的V-S中的顶点加入到集合S中，同时更新数组dist[]。一旦S包含了所有顶点，dist[]就是从源到所有其他顶点之间的最短路径长度。

① 数据结构

设置地图的带权邻接矩阵为map[][]，即如果从源点 u 到顶点 i 有边，就令 map[u][i] 等于 (u，i) 的权值，否则 map[u][i]=∞（无穷大）；采用一维数组 dist[i]来记录从源点 u 到 i 顶点的最短路径长度；采用一维数组p[i]来记录最短路径上 i 顶点的前驱。用布尔数组flag[]来表示集合V和V-S，如果flag[i]等于true，说明顶点i已经加入到集合S，否则顶点i属于集合V-S。

② 初始化

令集合S={u}，对于集合V-S中的所有顶点x，初始化dist[i]=map[u][i]，如果源点u到顶点i有边相连，初始化p[i]=u，否则p[i]= -1。

③ 找最小

在集合V-S中依照贪心策略来寻找使得dist[j]具有最小值的顶点 t，即dist[t]=min(dist[j] | j属于V-S集合)，则顶点 t 就是集合V-S中距离源点 u 最近的顶点。

④ 加入S战队

将顶点 t 加入集合S中，同时更新V-S。

⑤ 判断是否计算结束

如果集合V-S为空，算法结束，否则转⑥。

⑥ 借东风

在③中已经找到了源点到 t 的最短路径，那么对集合V-S中所有与顶点 t 相邻的顶点 j，都可以借助 t 走捷径。如果dist[j]>dist[t]+map[t][j]，则dist[j]=dist[t]+map[t][j]，记录顶点 j 的前驱为 t，有p[j]= t，转③。

由此，可求得从源点 u 到图G的其余各个顶点的最短路径及长度，也可通过数组 p[] 逆向找到最短路径上经过的城市。

3　完美图解

现在我们有一个景点地图，如图10所示↓，假设从1号结点出发，求到其他各个结点的最短路径。

算法步骤如下。

3.1 数据结构

设置地图的带权邻接矩阵为map[][]，即如果从顶点 i 到顶点 j 有边，则map[i][j]等于(i，j)的权值，否则map[i][j]=∞（无穷大），如图11所示↑。

3.2 初始化

令集合S={1}，V-S={2，3，4，5}，对于集合V-S中的所有顶点 x，初始化最短距离数组dist[i]=map[1][i]，dist[u]=0，如图12所示↓。如果源点1到顶点i有边相连，初始化前驱数组p[i]=1，否则p[i]= -1，如图13所示↓。

3.3 找最小

在集合V-S={2，3，4，5}中，依照贪心策略来寻找V-S集合中 dist[] 最小的顶点 t，如图14所示。

找到最小值为2，对应的结点 t=2。

3.4 加入S战队

将顶点t=2加入集合S中S={1，2}，同时更新V-S={3，4，5}，如图15所示。

3.5 借东风

刚刚找到了源点到 t=2 的最短路径，那么对集合V-S中所有 t 的邻接点 j，都可以借助 t 走捷径。我们从图或邻接矩阵都可以看出，2号结点的邻接点是 3 和 4 号结点，如图16所示↑。

先看3号结点能否借助2号走捷径：dist[2]+map[2][3]=2+2=4，而当前dist[3]=5>4，因此可以走捷径即2→3，更新dist[3]=4，记录顶点3的前驱为2，即p[3]= 2。

再看4号结点能否借助2号走捷径：如果dist[2]+map[2][4]=2+6=8，而当前dist[4]=∞>8，因此可以走捷径即2→4，更新dist[4]=8，记录顶点4的前驱为2，即p[4]= 2。

更新后如图17和图18所示。

3.6 找最小

在集合V-S={3，4，5}中，依照贪心策略来寻找dist[]具有最小值的顶点t，依照贪心策略来寻找V-S集合中dist[]最小的顶点t，如图19所示。

找到最小值为4，对应的结点t=3。

3.7 加入S战队

将顶点t=3加入集合S中S={1，2，3}，同时更新V-S={4，5}，如图20所示↑。

3.8 借东风

刚刚找到了源点到t =3的最短路径，那么对集合V-S中所有 t 的邻接点 j，都可以借助 t 走捷径。我们从图或邻接矩阵可以看出，3号结点的邻接点是4和5号结点。

先看4号结点能否借助3号走捷径：dist[3]+map[3][4]=4+7=11，而当前dist[4]=8<11，比当前路径还长，因此不更新。

再看5号结点能否借助3号走捷径：dist[3]+map[3][5]=4+1=5，而当前dist[5]=∞>5，因此可以走捷径即3—5，更新dist[5]=5，记录顶点5的前驱为3，即p[5]=3。

更新后如图21和图22所示。

3.9 找最小

在集合V-S={4，5}中，依照贪心策略来寻找V-S集合中dist[]最小的顶点t，如图23所示。

找到最小值为5，对应的结点t=5。

3.10 加入S战队

将顶点t=5加入集合S中S={1，2，3，5}，同时更新V-S={4}，如图24所示↑。

3.11 借东风

刚刚找到了源点到t =5的最短路径，那么对集合V-S中所有t的邻接点j，都可以借助t走捷径。我们从图或邻接矩阵可以看出，5号结点没有邻接点，因此不更新，如图25和图26所示。

3.12 找最小

在集合V-S={4}中，依照贪心策略来寻找dist[]最小的顶点 t，只有一个顶点，所以很容易找到，如图27所示。

找到最小值为8，对应的结点t=4。

3.13 加入S战队

将顶点t加入集合S中S={1，2，3，5，4}，同时更新V-S={ }，如图28所示↑。

3.14 算法结束

V-S={ }为空时，算法停止。

（上述的重复过程可以借助循环迭代完成）

由此，可求得从源点u到图G的其余各个顶点的最短路径及长度，也可通过前驱数组p[]逆向找到最短路径上经过的城市，如图29所示。

例如，p[5]=3，即5的前驱是3；p[3]=2，即3的前驱是2；p[2]=1，即2的前驱是1；p[1]= -1，1没有前驱，那么从源点1到5的最短路径为1→2→3→5。

#include <iostream>  // Dijkstra 迪杰斯特拉#include <stack>     // 输出最短路径using namespace std;//———————————————1 数据结构————————————————————const int N = 100;   // 城市的个数，用于初始化固定数组const int INF = 1e7; // 初始化无穷大为10000000，表示从一点到另一点不连通int map[N][N];       // 带权邻接矩阵，表示点的连通和距离int n,m;             // n表示城市的个数，m为城市间路线的条数，用于循环输入int dist[N];         // 表示从源点u到城市j的最短路径距离为dist[j]，中间值和输出int p[N];            // 表示从源点u到城市j的最短路径的前驱节点为p[j]，中间值和输出bool flag[N]; // 如果flag[i]等于true，说明顶点i已经加入到集合S;否则顶点i属于集合V-S              // 集合V表示全部顶点，集合S是按贪心策略已搜索的最短路径顶点void Dijkstra(int u){	int i,j;  // 循环变量//———————————————2 初始化—————————————————————    for(i=1; i<=n; i++)     // ①    {        dist[i] =map[u][i]; // 初始化源点u到其他各个顶点的最短路径长度        flag[i]=false;        if(dist[i]==INF)            p[i]=-1;        // 源点u到该顶点的路径长度为无穷大，说明顶点i与源点u不相邻        else            p[i]=u;         // 说明顶点i与源点u相邻，设置顶点i的前驱p[i]=u    }    dist[u] = 0;    flag[u]=true;           // 初始时，集合S中只有一个元素：源点u    for(i=1; i<=n; i++)     // ②    {//———————————————3 在集合V-S（!flag[j]）中找距离源点u最近的顶点t——            int temp = INF, t = u;        for(j=1; j<=n; j++)     // ③ 在集合V-S中寻找距离源点u最近的顶点t            if(!flag[j]&&dist[j]<temp)            {                t=j;                temp=dist[j];            }        if(t==u) return ;       // 找不到t（t未更新），跳出循环②        flag[t]= true;          // 否则，将t加入集合//———————————— 4 找到t点后，更新从源点u经t后到集合V-S中与t邻接的顶点的距离        for(j=1;j<=n;j++)                // ④ 更新集合V-S中与t邻接的顶点到源点u的距离            if(!flag[j]&& map[t][j]<INF) //    前者表示j在V-S中，后者表示t与j相邻                if(dist[j]>(dist[t]+map[t][j])) //源点到j vs 源点经t到j的路径                {                    dist[j]=dist[t]+map[t][j];  // 更新源点到j的最短距离                    p[j]=t;                     // 更新j的前驱                }    }}void findpath(int u)                // 源点到其它各顶点的最短路径{    int x;                          // 前驱    stack<int>s;                    // 利用库<stack>创建一个栈s    for(int i=1;i<=n;i++)    {        x=p[i];        while(x!=-1)        {            s.push(x);                // 将前驱依次压入栈中            x=p[x];        }        cout<<'源点'<<u<<'到顶点'<<i<<'的最短距离为：';        if(dist[i] == INF)            cout << 'sorry,无路可达'<<endl;        else        {            cout << dist[i];            cout<<'，\t路径为：';            while(!s.empty())            {                 cout<<s.top()<<'→';  // 输出栈顶元素                s.pop();              // 依次出栈            }            cout<<i<<endl;        }    }}void printmatrix(int n)               // 输出图的带权邻接矩阵{	int i,j;    cout <<'输出矩阵map：'<<endl;	cout<<'\t';    for(i=1;i<=n;++i)                 // 输出列标题        cout<<'\t'<<i;    cout<<endl;    for(i=1;i<=n;i++)    {        for(j=1;j<=n;j++)        {            if(j==1)                   // 输出行标题                cout << '\t' << i;            if(map[i][j]==INF)                 cout << '\t' << '∞';            else                 cout << '\t' << map[i][j];            if(j==n)                 cout<<endl;        }    }}               void initmatrix(int m,int n){    int u,v,w;    for(int i=1;i<=n;i++)                  // 初始化图的邻接矩阵        for(int j=1;j<=n;j++)            map[i][j]=INF;                 // 初始化邻接矩阵为无穷大    while(m--)    {        cin >> u >> v >> w;        map[u][v] = map[u][v]<w?map[u][v]:w;// 邻接矩阵储存，保留最小的距离    }}int main(){    cout << '请输入城市的个数：'<<endl;    cin >> n;    cout << '请输入城市之间的路线的个数：'<<endl;    cin >>m;    cout << '请输入城市之间的路线以及距离：'<<endl;    initmatrix(m,n);    int st;    cout<<'请输入小明所在的位置：'<<endl;    cin>>st;    printmatrix(n);    Dijkstra(st);    findpath(st);                        // st为源点    system('pause');    return 0;}/*演示时先复制下面内容581 2 21 3 52 3 22 4 63 4 74 3 23 5 14 5 41*//*output:请输入城市的个数：5请输入城市之间的路线的个数：8请输入城市之间的路线以及距离：1 2 21 3 52 3 22 4 63 4 74 3 23 5 14 5 4请输入小明所在的位置：1输出矩阵map：                1       2       3       4       5        1       ∞      2       5       ∞      ∞        2       ∞      ∞      2       6       ∞        3       ∞      ∞      ∞      7       1        4       ∞      ∞      2       ∞      4        5       ∞      ∞      ∞      ∞      ∞源点1到顶点1的最短距离为：0，路径为：1源点1到顶点2的最短距离为：2，路径为：1→2源点1到顶点3的最短距离为：4，路径为：1→2→3源点1到顶点4的最短距离为：8，路径为：1→2→4源点1到顶点5的最短距离为：5，路径为：1→2→3→5请按任意键继续. . .*/

－End－