找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

只需一步,快速开始

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

查看: 5912| 评论: 0| 发布者: changlei

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

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

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

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[]就是从源到所有其他顶点之间的最短路径长度。

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


① 数据结构

设置地图的带权邻接矩阵为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号结点出发,求到其他各个结点的最短路径。

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


算法步骤如下。

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所示↓。

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


3.3 找最小

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

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


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

3.4 加入S战队

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

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


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所示。

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


3.6 找最小

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

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


找到最小值为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所示。

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


3.9 找最小

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

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


找到最小值为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所示。

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


3.12 找最小

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

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


找到最小值为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所示。

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


例如,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-

【免责声明】本文仅代表作者或发布者个人观点,不代表SEO研究协会网(www.seoxiehui.cn)及其所属公司官方发声,对文章观点有疑义请先联系作者或发布者本人修改,若内容涉及侵权或违法信息,请先联系发布者或作者删除,若需我们协助请联系平台管理员,邮箱cxb5918@163.com(本平台不支持其他投诉反馈渠道,谢谢合作)。若需要学习以上相关知识请到巨推学院观看视频教程,网址www.jutuiedu.com。

鸡蛋

鲜花

握手

雷人

路过
已有 0 人参与

会员评论

推荐阅读

更多推广问题,请加微信:jutui3

文章排行

TOP ARTICLES

返回顶部