精华内容
下载资源
问答
  • 给定两点最短路径
    2020-08-27 13:35:17

    该算法实现的主要思路是声明一个路径矩阵和一个距离矩阵,利用动态规划的思想,依次将所有顶点作为中转顶点进行遍历,计算出当前路径距离与上一次的结果进行比较,如果当前路径的距离更小则更新两个矩阵。最后只需要访问矩阵便可以得到结果。

    具体代码实现:

    #include<iostream>
    using namespace std;
    #define INF 10000	//定义无穷大 
    #define size 1001	//最大数据规模 
    
    int path[size][size]//存路劲 
    int dis[size][size];	//存距离 
    
    void init()//数组初始化函数 ,这是算法的必要前提 
    {
    	for(int i=0;i<size;i++)
    		for(int j=0;j<size;j++)
    		{
    			path[i][j]=-1;//初始化路径为-1 
    			if(i!=j)	//因为自己到自己的距离为0,所以矩阵的对角线始终为0,这步十分的关键 
    			{
    				dis[i][j]=INF;
    			}		
    		}
    		
    }
    
    void floyd(int n)//佛洛依德算法实现,n:顶点数目 
    {
    	for(int k=1;k<=n;k++)//k作为中转顶点 
    	{
    		for(int i=1;i<=n;i++)
    		{
    			for(int j=1;j<=n;j++)
    			{
    				if(dis[i][k]+dis[k][j]<dis[i][j])//递推公式,通过顶点k的路径距离更小则更新矩阵 
    				{
    					dis[i][j]=dis[i][k]+dis[k][j];//更新距离 
    					path[i][j]=k;//更新路径,i到j的中转顶点为k 
    				}
    			}
    		}
    	}
    }
    
    void print(int s,int e)//递归+回溯打印中间路径 
    {
    	if(path[s][e]==-1) return;//递归出口,路径中第一点与第二点之间的中转点为初始化值 
    	print(s,path[s][e]);
    	cout<<"->"<<path[s][e];
    }
    
    void print_path(int start,int end)//打印完整路径 start:起点,end:终点 
    {
    	cout<<start;
    	print(start,end);
    	cout<<"->"<<end; 
    }
    
    int main()
    {
    	init();//初始化矩阵 
    	int n,m;
    	cout<<"输入顶点数和边数(两个数之间用空格隔开):"<<endl; 
    	cin>>n>>m;
    	cout<<"请依次输入顶点编号和边长(格式:顶点 顶点 边长):"<<endl;
    	int a,b,d;
    	for(int i=0;i<m;i++)
    	{
    		cin>>a>>b>>d;
    		dis[a][b]=d;
    		//如果是有向图注释掉下面这条语句即可 
    		dis[b][a]=d;
    	}
    	floyd(n);
    	cout<<"输入要查询的起点和终点(空格隔开):"<<endl;
    	cin>>a>>b;
    	cout<<"距离:"<<dis[a][b]<<endl<<"路径:";
    	print_path(a,b);
    	return 0;
    }
    

    说明
    1、需要两个矩阵,一个路径矩阵,一个距离矩阵。路径矩阵存的是两点之间的中转顶点,例如 path[i][j]=k,表示顶点i到顶点j的中转顶点为顶点k。距离矩阵存的是两点之间当前的最短距离,例如 dis[i][j]=10,表示顶点i到顶点j的当前最短距离为10。
    2、算法实现的代码十分的简单明了,就是三重循环,几乎是固定模板,可以直接照抄。算法实现的成败关键在于两个矩阵的初始化处理,细节看代码注解。
    3、时间复杂度为O(N^3)。

    更多相关内容
  • NULL 博文链接:https://128kj.iteye.com/blog/1689015
  • 给定一个乡镇网络图,求取个乡镇的最短路径,并输出路径,以及路径距离的大小。
  • SHPATH - 避障的最短路径(版本 1.3) 给定一个由 0(对于开放空间)和 1(对于障碍物)组成的“地形”矩阵,该函数计算个指定点之间的最短路径,同时避开障碍物。 采用阶段解决方案。 在第一阶段,算法通过...
  • 求解两点最短路径的算法

    千次阅读 2020-07-19 23:42:40
    最短路径算法1.Dijkstra算法2.Bellman-Ford算法3.SPFA算法4.Floyd算法几种最短路径算法的对比Dijkstra算法、Bellman-Ford算法和SPFA算法的对比Dijkstra算法和Floyd算法的...多源最短路算法:求任意两点之间的最短路径.

    最短路径算法

    • 单源最短路算法:已知起点,求到达其他点的最短路径。
              常用算法:Dijkstra算法、Bellman-Ford算法、SPFA算法。
    • 多源最短路算法:求任意两点之间的最短路径。
              常用算法:Floyd算法。

    1.Dijkstra算法

            迪杰斯特拉算法(Dijkstra)是寻找从一个顶点到其余各顶点最短路径的算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。
            处理问题:单源、无负权、有向图、无向图最短路径。
            不能使用的情况:边中含有负权值(无法判断)。
            主要特点:以起始点为中心向外层层扩展,直到扩展到终点为止。
            算法过程:V为顶点集合,分为两组S和U。其中,S为已求出的顶点的集合(初始时只含有源点V0),U为尚未确定的顶点集合,源点到各个顶点最短路径的距离结果存在dist[]中。
                            1.初始化:S只包含源点,U包含除V中S以外的其他点;
                            2.选择:从U中选取一个距离源点最近的顶点u加入S;
                            3.更新:修改u的后继顶点的最短路径长度;
                            4.重复步骤2和3直到所有顶点都包含在S中。
           举例说明:图中有A、B、C、D、E五个顶点,其中A为源顶点,寻找A到其他各顶点的最短路径。
                            Step1:V包含A、B、C、D、E五个点,S只包含源点A,U包含V中除S以外的其他点,计算U中各点到源点的距离发现距源点最近的顶点是B;在这里插入图片描述                        Step2:将距源点最近的顶点B移入S中,S包含A、B,U包含C、D、E,再次计算U中各点到源点的距离发现距源点最近的顶点是C;在这里插入图片描述                        Step3:再次将距源点最近的顶点C移入S中,S包含A、B、C,U包含D、E,再次计算U中各点到源点的距离发现距源点最近的顶点是E;在这里插入图片描述                        Step4:再次将距源点最近的顶点E移入S中,S包含A、B、C、E,U包含D,再次计算U中各点到源点的距离发现距源点最近的顶点是D;在这里插入图片描述                        Step5:再次将距源点最近的顶点D移入S中,S包含A、B、C、E、D,U为空,算法结束,得到的dist[]中的结果就是A到其他各顶点的最短距离。在这里插入图片描述

    2.Bellman-Ford算法

           贝尔曼-福特算法(Bellman–Ford)是求解单源最短路径问题的一种算法,它的原理是对图进行次松弛操作,得到所有可能的最短路径。其算法可以进行若干种优化,提高了效率。
           基本思想: Bellman-Ford的思想和Dijkstra很像,其关键点都在于不断地对边进行松弛,而最大的区别就在于前者能作用于负边权的情况。其实现思路是在求出最短路径后,判断此刻是否还能对便进行松弛,如果还能进行松弛,便说明还有负边权的边。
           处理问题:单源、可有负权、有向图、无向图最短路径。
           算法过程:1.初始化:初始化所有的点,每一个点保存一个值,表示源点到这个点的距离其他点的值设为无穷大;
                            2.迭代求解:进行循环,从1到n-1,进行松弛计算;
                            3.检验负权回路:遍历所有边,如果的d[v]>d[u]+w(u,v)存在,则有从源点可达的权为负的回路。
           边的松弛操作:如下图所示,d[v]、d[u]是目前s到v、u的最短距离,关注边<u,v>能否改善d[v]的值。如果if(d[u]+w<d[v])成立,原有的d[v]路线将被s → \rightarrow u → \rightarrow v代替,这就是边<u,v>的松弛操作。在这里插入图片描述

    3.SPFA算法

           SPFA 算法是Bellman-Ford算法的队列优化算法的别称,通常用于求含负权边的单源最短路径,以及判负权环,它采用一系列的松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径。
           处理问题:单源、可有负权、有向图、无向图最短路径(自身其实无法处理负权)
           算法思想:设立一个队列用来保存待优化的点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对u点所指向的结点v进行松弛操作,如果v点的最短路径估计值有所调整,且v点不在当前的队列中,就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列空为止。

    4.Floyd算法

           弗洛伊德算法(Floyd)又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。Floyd算法适用于APSP(All Pairs Shortest Paths,多源最短路径),稠密图效果最佳,边权可正可负。此算法简单有效,由于三重循环结构紧凑,对于稠密图,效率要高于执行|V|次Dijkstra算法,也要高于执行|V|次SPFA算法。
           处理问题:多源、可有负权、有向图、无向图最短路径。
           优点:容易理解,可以算出任意两个节点之间的最短距离,代码编写简单。
           缺点:时间复杂度比较高,不适合计算大量数据。
           算法过程:1.从任意一条单边路径开始,所有两点之间的距离是边的权,用邻接矩阵G表示,如果两点之间没有边相连,则权为无穷大;
                            2.对于每一对顶点i和j,看看是否存在一个顶点k使得从i到k再到j比已知的路径更短。G[i][j] = min( G[i][j], G[i][k]+G[k][j] ),如果G[i][j]的值变小,定义一个矩阵D用来记录所插入点的信息,则D[i][j]=k。
                                           f o r k i n r a n g e ( s e l f . V ) : for{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}k{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}} in {_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}range(self.V): forkinrange(self.V):
                                                  f o r i i n r a n g e ( s e l f . V ) : for{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}i{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}} in {_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}range(self.V): foriinrange(self.V):
                                                         f o r j i n r a n g e ( s e l f . V ) : for{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}j{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}} in {_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}range(self.V): forjinrange(self.V):
                                                                i f s e l f . G [ i ] [ k ] + s e l f . G [ k ] [ j ] < s e l f . G [ i ] [ j ] : if{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}self.G[i][k]{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}+self.G[k][j]<self.G[i][j]: ifself.G[i][k]+self.G[k][j]<self.G[i][j]:
                                                                       s e l f . G [ i ] [ j ] = s e l f . G [ i ] [ k ] < s e l f . G [ k ] [ j ] self.G[i][j]{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}={_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}self.G[i][k]<self.G[k][j] self.G[i][j]=self.G[i][k]<self.G[k][j]
                                                                       s e l f . D [ i ] [ j ] = s e l f . D [ i ] [ k ] self.D[i][j]{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}={_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}self.D[i][k] self.D[i][j]=self.D[i][k]
           举例说明:图中有1、2、3、4、5五个顶点,寻找任意两点间的最短路径。矩阵G为任意两点间的权值邻接矩阵,矩阵D为用来记录所插入点的标号。
                            Step1:初始化矩阵G、D,G初始化为任意两点间的距离,若两点间没有直线相连则用无穷大表示;D初始化为任意两点间的终点标号。在这里插入图片描述                        Step2:更新矩阵G、D,看有没有任意两点经过0之后比原来的路径更短,有的话G中对应的元素更新为更小的值,D中对应的元素更新为同一行第0列的元素。在这里插入图片描述                        Step3:继续更新矩阵G、D,看有没有任意两点经过1之后比原来的路径更短,有的话G中对应的元素更新为更小的值,D中对应的元素更新为同一行第1列的元素。在这里插入图片描述                        Step4:继续更新矩阵G、D,看有没有任意两点经过2之后比原来的路径更短,有的话G中对应的元素更新为更小的值,D中对应的元素更新为同一行第2列的元素。在这里插入图片描述                        Step5:继续更新矩阵G、D,看有没有任意两点经过3之后比原来的路径更短,有的话G中对应的元素更新为更小的值,D中对应的元素更新为同一行第3列的元素。在这里插入图片描述                        Step6:继续更新矩阵G、D,看有没有任意两点经过4之后比原来的路径更短,有的话G中对应的元素更新为更小的值,D中对应的元素更新为同一行第4列的元素。算法结束,得到的 G 4 {G_{4}} G4为任意两点间的最短距离, D 4 {D_{4}} D4为任意两点间最短路径间的信息。在这里插入图片描述

    几种最短路径算法的对比

    Dijkstra算法、Bellman-Ford算法和SPFA算法的对比

    • Dijkstra算法无法判断含负权边的图的最短路径,Bellman-Ford算法优于Dijkstra算法的方面是边的权值可以为负数、实现简单,缺点是时间复杂度过高。
    • SPFA算法在负边权图上可以完全取代Bellman-Ford算法,另外在稀疏图中也表现良好。但是在非负边权图中,为了避免最坏情况的出现,通常使用效率更加稳定的Dijkstra算法,以及它的使用堆优化的版本。
    • 与Dijkstra算法与Bellman-Ford算法都不同,SPFA的算法时间效率是不稳定的,即它对于不同的图所需要的时间有很大的差别。

    Dijkstra算法和Floyd算法的对比

    • Dijkstra算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。
    • Floyd算法是多源最短路径算法,用于计算任意两点间的最短路径。
    • Dijkstra算法是基于贪心算法的思想,从起点出发逐步找到通向终点的最短距离;而Floyd算法是基于动态规划的思路,通过循环迭代的方法同时找出任意两个顶点间的最短距离。
    展开全文
  • 主要为大家详细介绍了java使用Dijkstra算法实现单源最短路径,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大,这也是所谓的初始化工作; 对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。 以下图为...

    算法描述:

    1. 从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大,这也是所谓的初始化工作;
    2. 对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

    以下图为例,对Floyd 算法进行演示。
    在这里插入图片描述
    图片转自https://blog.csdn.net/fengchi863/article/details/80036586

    以下为c++版代码:

    //
    
    #include "stdafx.h"
    #include<iostream>
    #include<string>
    #include<vector>
    using namespace std;
    const int N = 10;
    const int INF = INT_MAX;
    vector<int>v;
    int mEdgNum;        // 边的数量
    string mVexs[N];       // 顶点集合
    int mMatrix[N][N];    // 邻接矩阵
    int amount_path[N][N];
    
    void floyd(string path[N][N], int dist[N][N], int length) {
    
    	// 初始化
    	for (int i = 0; i < length; i++) {
    		for (int j = 0; j < length; j++) {
    			dist[i][j] = mMatrix[i][j];    // "顶点i"到"顶点j"的路径长度为"i到j的权值"。
    			if (dist[i][j] != INF)
    			{
    				path[i][j] = mVexs[i] + mVexs[j];
    				amount_path[i][j] = 1;
    			}
    			else
    				path[i][j] = "";            // "顶点i"到"顶点j"的最短路径是经过顶点j。
    		}
    	}
    
    	// 计算最短路径
    	for (int k = 0; k < length; k++) {
    		for (int i = 0; i < length; i++) {
    			for (int j = 0; j < length; j++) {
    				// 如果经过下标为k顶点路径比原两点间路径更短,则更新dist[i][j]和path[i][j]
    				int tmp = (dist[i][k] == INF || dist[k][j] == INF) ? INF : (dist[i][k] + dist[k][j]);
    				int f = dist[i][j];
    				if (tmp < dist[i][j]) 
    				{
    					// "i到j最短路径"对应的值设,为更小的一个(即经过k)
    					dist[i][j] = tmp;
    					// "i到j最短路径"对应的路径,经过k
    					path[i][j] = path[i][k] + path[k][j];
    					amount_path[i][j] = 1;
    				}
    				else if (tmp == f&&k!=i&&k!=j)amount_path[i][j]++;
    			}
    		}
    	}
    	for (int i = 0; i < length; i++) {
    		for (int j = 0; j < length; j++)
    		if (i != j)
    		{
    			cout << "顶点" << i << "到顶点" << j << "的最短路径长度为" << dist[i][j] << endl;
    			cout << "路径为";
    			for (int k = 0; k < path[i][j].size() - 1; k++)
    			{
    				if (k == 0 && path[i][j][k] != path[i][j][k + 1])
    					cout << path[i][j][k]<<path[i][j][k+1];
    				else if (path[i][j][k] != path[i][j][k + 1])
    					cout << path[i][j][k+1];
    			}
    			cout <<endl;
    			cout << "最短路径条数为" << amount_path[i][j]<<endl;
    		}
    	}
    }
    int main()
    {
    	int amount_vex, M;//M代表存在的路径数;
    	scanf_s("%d %d", &amount_vex, &M);
    	for (int i = 0; i < amount_vex; i++)//把每个点按数字由小到大编号
    	{
    		mVexs[i] = 48 + i;
    	}
    	string path[N][N];
    	int dist[N][N];
    	fill(amount_path[0],amount_path[0]+amount_vex*amount_vex, 0);
    	for (int i = 0; i < amount_vex; i++)//初始化
    	{
    		for (int j = 0; j < amount_vex; j++)
    		{
    			if (i == j)mMatrix[i][j] = 0;
    			else mMatrix[i][j] = INF;
    			path[i][j] = "";
    		}
    	}
    	for (int i = 0; i < M; i++)
    	{
    		int m1, m2;
    		scanf_s("%d %d", &m1, &m2);
    		scanf_s("%d", &mMatrix[m1][m2]);
    		mMatrix[m2][m1] = mMatrix[m1][m2];
    	}
    	
    	floyd(path, dist, amount_vex);
    
    }
    
    

    运行结果:
    顶点0到顶点1的最短路径长度为1
    路径为01
    最短路径条数为1
    顶点0到顶点2的最短路径长度为2
    路径为02
    最短路径条数为1
    顶点0到顶点3的最短路径长度为3
    路径为03
    最短路径条数为2
    顶点1到顶点0的最短路径长度为1
    路径为10
    最短路径条数为1
    顶点1到顶点2的最短路径长度为3
    路径为102
    最短路径条数为1
    顶点1到顶点3的最短路径长度为2
    路径为13
    最短路径条数为1
    顶点2到顶点0的最短路径长度为2
    路径为20
    最短路径条数为1
    顶点2到顶点1的最短路径长度为3
    路径为201
    最短路径条数为1
    顶点2到顶点3的最短路径长度为2
    路径为23
    最短路径条数为1
    顶点3到顶点0的最短路径长度为3
    路径为30
    最短路径条数为2
    顶点3到顶点1的最短路径长度为2
    路径为31
    最短路径条数为1
    顶点3到顶点2的最短路径长度为2
    路径为32
    最短路径条数为1
    请按任意键继续. . .

    dp版本:
    在这里插入图片描述

    展开全文
  • 1.关于旅行商(TSP)问题及衍化...旅行商问题(TSP)又译为旅行推销员问题、货郎担问题,简称为TSP问题,是最基本的路线问题,该问题是在寻求单一旅行者由起点出发,通过所有给定的需求之后,最后再回到原点的最小路径...

    1.关于旅行商(TSP)问题及衍化

      旅行商问题(Traveling Saleman Problem,TSP)是车辆路径调度问题(VRP)的特例,由于数学家已证明TSP问题是NP难题,因此,VRP也属于NP难题。旅行商问题(TSP)又译为旅行推销员问题、货郎担问题,简称为TSP问题,是最基本的路线问题,该问题是在寻求单一旅行者由起点出发,通过所有给定的需求点之后,最后再回到原点的最小路径成本。——旅行商问题百科

      很明显,当节点数很少时,大多数人都会想到,问题很简单,直接穷举就OK了,但实际问题中,节点数往往很大,变得不可能。例如:对于一个仅有16个城市的旅行商问题,如果用穷举法来求问题的最优解,需比较的可行解有:15!/2=653,837,184,000个。在1993年,使用当时的工作站用穷举法求解此问题需时92小时。即使现在计算机速度快,但是面对复杂的问题,仍然不够。这就是所谓的“组合爆炸”,指数级的增长,所以科学家逐步寻找近似算法或者启发式算法,目的是在合理的时间范围内找到可接受的最优解。

      TSP问题解决算法的发展可以分为3个部分:

    1).经典精确算法:穷举法、线性规划算法、动态规划算法、分支定界算法等运筹学中的传统算法,这些算法复杂度一般都很大,只适用于求解小规模问题。

    2).近似算法:当问题规模较大时,其所需的时间成级数增长,这是我们无法接受的,算法求解问题的规模受到了很大的限制,一个很自然的想法就是牺牲精确解法中的最优性,去寻找一个好的时间复杂度我们可以容忍的,同时解的质量我们可以接受的算法.基于这一思想所设计出的算法统称为近似算法。如插入算法,最邻近算法等。

    3).智能算法:随着科学技术和生产的不断发展,许多实际问题不可能在合理的时间范围内找到全局最优解,这就促使了近代最优化问题求解方法的产生。随着各种不同搜索机制的启发式算法相继出现,如禁忌搜索、遗传算法、模拟退火算法、人工神经网络、进化策略、进化编程、粒子群优化算法、蚁群优化算法和免疫计算等,掀起了研究启发式算法的高潮。

      具体每一种算法不再详细描述,大家可以针对性的寻找相应资料进行了解。

      TSP问题在实际的生产生活中,更加实际环境不同,有很多衍生的经典问题。车辆路径调度(VRP)扩展问题是经典VRP加入各种约束条件后而形成的。例如需求约束形成的需求随机的车辆路径问题(SVRP);加入时间约束得到的带时间窗的车辆路径题(VRPTW);加入距离约束的距离约束车辆路径问题(DVRP);根据其它条件的不同,还有多配送中心车辆路径问题(MDVRP)、可切分的车辆路径问题(SDVRP);先配送再收集车辆路径问题(VRPB)、配送收集车辆路径问题(VRPPD);信息不完全的模糊车辆路径问题(FVRP)[3]。

    回到目录

    2.群蚁算法基本原理

    2.1 算法综述

      对于VRP问题,求解算法大致可分为精确算法和人工智能算法两大类。精确性算法基于严格的数学手段,在可以求解的情况下,解的质量较好。但是由于算法严格,运算量大,特别是大规模的问题几乎无法求解。所以其应用只能是小规模的确定性问题,面对中小规模问题,人工智能算法在精度上不占优势。但规模变大时,人工智能方法基本能在可接受时间里,找到可接受的满意解,这是精确算法难以做到的。由于的实际问题,各种约束错综复杂,人工智能算法显示出了巨大的优越性,也正因为如此,实际应用中,人工智能算法要更广泛。求解车辆路径调度问题的精确算法有动态规划法、分枝定界法等。并开始寻求所得结果可接受的启发式算法,以处理大规模实际问题,一些其他学科的新一代优化算法相继出现,如禁忌搜索算法,遗传算法,人工神经网络算法,以及现在研究较多的蚁群算法等。

    2.2 群蚁算法的原理

      蚁群算法是受到对真实蚂蚁群觅食行为研究的启发而提出。生物学研究表明:一群相互协作的蚂蚁能够找到食物和巢穴之间的最短路径,而单只蚂蚁则不能。生物学家经过大量细致观察研究发现,蚂蚁个体之间的行为是相互作用相互影响的。蚂蚁在运动过程中,能够在它所经过的路径上留下一种称之为信息素的物质,而此物质恰恰是蚂蚁个体之间信息传递交流的载体。蚂蚁在运动时能够感知这种物质,并且习惯于追踪此物质爬行,当然爬行过程中还会释放信息素。一条路上的信息素踪迹越浓,其它蚂蚁将以越高的概率跟随爬行此路径,从而该路径上的信息素踪迹会被加强,因此,由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象。某一路径上走过的蚂蚁越多,则后来者选择该路径的可能性就越大。蚂蚁个体之间就是通过这种间接的通信机制实现协同搜索最短路径的目标的。我们举例简单说明蚂蚁觅食行为:

        

        如上图a,b,c的示意图:

        a图是原始状态,蚂蚁起始点为A,要到达E,中途有障碍物,要绕过才能到达。BC和BH是绕过障碍物的2条路径(假设只有2条)。各个路径的距离d已经标定。

        b图是t=0时刻蚂蚁状态,各个边上有相等的信息素浓度,假设为15;

        c图是t=1时刻蚂蚁经过后的状态,各个边的信息素浓度,有变化;因为大量蚂蚁的选择概率会不一样,而选择概率是和路径长度相关的。所以越短路径的浓度会越来越大,经过此短路径达到目的地的蚂蚁也会比其他路径多。这样大量的蚂蚁实践之后就找到了最短路径。所以这个过程本质可以概括为以下几点:

        1.路径概率选择机制信息素踪迹越浓的路径,被选中的概率越大

        2.信息素更新机制路径越短,路径上的信息素踪迹增长得越快

        3.协同工作机制蚂蚁个体通过信息素进行信息交流。

        从蚂蚁觅食的原理可见,单个个体的行为非常简单蚂蚁只知道跟踪信息素爬行并释放信息素,但组合后的群体智能又非常高蚂蚁群能在复杂的地理分布的清况下,轻松找到蚁穴与食物源之间的最短路径。这种特点恰恰与元启发算法的特点相一致,蚁群优化算法正是受到这种生态学现象的启发后加以模仿并改进而来,觅食的蚂蚁由人工蚁替代,蚂蚁释放的信息素变成了人工信息素,蚂蚁爬行和信息素的蒸发不再是连续不断的,而是在离散的时空中进行。

      上述例子如果不好理解,我在这里贴几张PPT,个人感觉非常不错,也是我找了很多资料觉得最好理解的【来源是大连理工大学谷俊峰】,点击这里提供下载:蚁群算法基本知识.rar

        从深层意义上来讲,蚁群算法作为优化的方法之一,属于人工群集智能领域。人工群集智能,大都受自然群集智能如昆虫群和动物群等的启发而来。除了具有独特的强有力的合作搜索能力外,还可以利用一系列的计算代理对问题进行分布式处理,从而大大提高搜索效率。

    回到目录

    3.群蚁算法的基本流程

      我们还是采用大连理工大学谷俊峰的PPT来说明问题,重要公式进行截图计算和解释,对PPT难以理解的地方进行单独解释:

    3.1 基本数学模型

      首先看看基本TSP问题的基本数学模型:

      问题其实很简单,目标函数就是各个走过路径的总长度,注意的就是距离矩阵根据实际的问题不一样,长度是不一样的。

    3.2 群蚁算法说明

      在说明群蚁算法流程之前,我们对算法原理和几个注意点进行描述:

    1.TSP问题的人工蚁群算法中,假设m只蚂蚁在图的相邻节点间移动,从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定:1. 信息素值也称信息素痕迹。2.可见度,即先验值。\ 2.信息素的更新方式有2种,一是挥发,也就是所有路径上的信息素以一定的比率进行减少,模拟自然蚁群的信息素随时间挥发的过程;二是增强,给评价值“好”(有蚂蚁走过)的边增加信息素。\ 3.蚂蚁向下一个目标的运动是通过一个随机原则来实现的,也就是运用当前所在节点存储的信息,计算出下一步可达节点的概率,并按此概率实现一步移动,逐此往复,越来越接近最优解。\ 4.蚂蚁在寻找过程中,或者找到一个解后,会评估该解或解的一部分的优化程度,并把评价信息保存在相关连接的信息素中。 

    3.3 群蚁算法核心步骤

      更加我们前面的原理和上述说明,群蚁算法的2个核心步骤是 路径构建 和 信息素更新。我们将重点对这2个步骤进行说明。

    3.3.1 路径构建

      每个蚂蚁都随机选择一个城市作为其出发城市,并维护一个路径记忆向量,用来存放该蚂蚁依次经过的城市。蚂蚁在构建路径的每一步中,按照一个随机比例规则选 择下一个要到达的城市。随机概率是按照下列公式来进行计算的:

      上述公式就是计算 当前点 到 每一个可能的下一个节点 的概率。分子是 信息素强度 和 能见度 的幂乘积,而分母则是所有 分子的和值。这个刚开始是很不容易理解的,我们在最后实例计算的时候,可以看得很清楚,再反过来理解公式。注意每次选择好节点后,就要从可用节点中移除选择的节点。

    3.3.2 信息素更新

      信息素更新是群蚁算法的核心。也是整个算法的核心所在。算法在初始期间有一个固定的浓度值,在每一次迭代完成之后,所有出去的蚂蚁回来后,会对所走过的路线进行计算,然后更新相应的边的信息素浓度。很明显,这个数值肯定是和蚂蚁所走的长度有关系的,经过一次次的迭代, 近距离的线路的浓度会很高,从而得到近似最优解。那我们看看信息素更新的过程。

      初始化信息素浓度C(0),如果太小,算法容易早熟,蚂蚁会很快集中到一条局部最优路径上来,因为可以想想,太小C值,使得和每次挥发和增强的值都差不多,那么 随机情况下,一些小概率的事件发生就会增加非最优路径的信息素浓度;如果C太大,信息素对搜索方向的指导性作用减低,影响算法性能。一般情况下,我们可以使用贪婪算法获取一个路径值Cnn,然后根据蚂蚁个数来计算C(0) = m/Cnn ,m为蚂蚁个数

      每一轮过后,问题空间中的所有路径上的信息素都会发生蒸发,然后,所有的蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素,公式如下: 

      信息素更新的作用:\ 1.信息素挥发(evaporation)信息素痕迹的挥发过程是每个连接上的 信息素痕迹的浓度自动逐渐减弱的过程,这个挥发过程主要用于避 免算法过快地向局部最优区域集中,有助于搜索区域的扩展。\ 2.信息素增强(reinforcement)增强过程是蚁群优化算法中可选的部 分,称为离线更新方式(还有在线更新方式)。这种方式可以实现 由单个蚂蚁无法实现的集中行动。基本蚁群算法的离线更新方式是 在蚁群中的m只蚂蚁全部完成n城市的访问后,统一对残留信息进行 更新处理。

    3.3.3 迭代与停止

      迭代停止的条件可以选择合适的迭代次数后停止,输出最优路径,也可以看是否满足指定最优条件,找到满足的解后停止。最重要的是,我刚开始理解这个算法的时候,以为每一只蚂蚁走一条边就是一次迭代,其实是错的。这里算法每一次迭代的意义是:每次迭代的m只蚂蚁都完成了自己的路径过程,回到原点后的整个过程。

    回到目录

    4.群蚁算法计算实例

      使用PPT中的一个案例,非常直观,对几个符号错误进行了修改,主要是计算概率的乘号,结果没有错误:

      过程总体还是比较简单的,注意理解公式,然后把公式和实例结合起来看,最好是拿笔自己手动画一画,容易理解。下面我们来看看如何编程实现TSP问题的群蚁算法代码。

    ``` % Ant main program

    clear all; close all; clc;

    tic; Ant=25;%蚂蚁数量 Ger=120;%迭代次数 firstaddress = [ 100,10 150,10 180,30 200,10 200,200 200,220 180,240 180,270 150,270 100,240 80,240 50,270 200,300 10,300 10,270 10,240 10,200 10,10 50,30 100,10 ];%firstaddress表示测试数据中的节点坐标

    SumOfCity = size(firstaddress,1);%节点个数 lengthaddress =10000.*ones(SumOfCity,SumOfCity);%lengthaddress表示两两节点间的距离,初始设定10000,可以设定无穷大,表示不相连 lengthaddress(1,2)=377;%表示节点1和节点2的距离 lengthaddress(2,4)=190; lengthaddress(2,3)=100; lengthaddress(3,4)=101; lengthaddress(4,5)=240; lengthaddress(5,17)=1932; lengthaddress(5,6)=70; lengthaddress(6,13)=200; lengthaddress(6,7)=63.1;

    lengthaddress(7,10)=377; lengthaddress(7,8)=87.5; lengthaddress(8,9)=100; lengthaddress(10,11)=8; lengthaddress(9,10)=170.8; lengthaddress(9,12)=332.9; lengthaddress(11,12)=168.8; lengthaddress(11,16)=375.2; length_address(12,15)=135.1;

    lengthaddress(13,14)=458; lengthaddress(14,15)=100; lengthaddress(15,16)=86.7; lengthaddress(16,17)=187.5; length_address(17,18)=639.8;

    lengthaddress(18,20)=510.5; lengthaddress(18,19)=200.1; lengthaddress(19,20)=246.8; for n=1:size(firstaddress) for m=1:size(firstaddress) if lengthaddress(n,m)~=10000 lengthaddress(m,n)=lengthaddress(n,m); %对称矩阵 end end end

    power=lengthaddress;%距离 [PM PN]=size(power);%距离矩阵大小,行列个数 % %% 画出节点分布图形 % figure(1); % grid on; % hold on; % scatter(firstaddress(:,1),firstaddress(:,2)); % for i=1:PN % for j=1:PN % if(lengthaddress(i,j)~=10000) % line([firstaddress(i,1),firstaddress(j,1)],[firstaddress(i,2),firstaddress(j,2)],'Color','g');%划线 % text((firstaddress(i,1)+firstaddress(j,1))/2,(firstaddress(i,2)+firstaddress(j,2))/2,num2str(length_address(i,j)));%标注线段距离 % end % end % end

    % 初始化蚂蚁位置 v=init_population(Ant,PN); v(:,1)=1;%起点 v(:,PN)=1;%终点

    fit=shortroadfun(v,power);%求每条路径的距离 T0 = max(fit)-fit;

    % 初始化 vmfit=[]; vx=[]; P0=0.2; % P0----全局转移选择因子 P=0.8; % P ----信息素蒸发系数 %C=[]; % 开始寻优 for iger=1:Ger lamda=1/iger; % 转移步长参数 [TBest(iger),BestIndex]=max(T0); for jg=1:Ant % 求取全局转移概率 r=T0(BestIndex)-T0(jg); Prob(iger,jg)=r/T0(BestIndex); end %对100只蚂蚁进行路径的转变 for jgtr=1:Ant %路径进行改变,该路径存放到temp变量,1表示经过该列所在的节点数 if Prob(iger,jgtr) g tr,:)-2.*(v(jg tr,:).*M)+M; else M=rand(1,PN) g tr,:)-2.*(v(jg tr,:).*M)+M; end temp(:,1)=1;%起点和终点必须有蚂蚁存在 temp(:,end)=1; %判转变后的临时路径距离是否小于原来的路径,是的话就将该蚂蚁的路径进行转换成temp中存放的路径 if shortroad fun(temp,power) road fun(v(jg tr,:),power) v(jg_tr,:)=temp; end end

    %信息素更新
    
       [sol,indb]=min(fit);
    v(1,:)=v(indb,:);%第一只蚂蚁的路径保存最小路径
    media=mean(fit);
    vx=[vx sol];%存放每一代最小的距离
    %     vmfit=[vmfit media];

    end

    % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %%%% 最后结果 % 显示最优解及最优值 % v(indb,:) disp(sprintf('Code of shortroad is: %s',num2str(v(indb,:)))); disp(sprintf('\n')); %空一行 disp(sprintf('Shortroad is: %s',num2str(find(v(indb,:))))); disp(sprintf('Mininum is: %d',sol)); route=find(v(indb,:)); % 画出节点分布图形 figure(2); grid on; hold on; for i=1:PN-1 plot(firstaddress(i,1),firstaddress(i,2),'bo','MarkerSize',10); str=num2str(i); text(firstaddress(i,1)-10,firstaddress(i,2)+10,str,'Color','red','FontSize',15); end m=length(route); for i=1:m plot(firstaddress(route(i),1),firstaddress(route(i),2),'MarkerSize',10,'MarkerEdgeColor','k','MarkerFaceColor',[0.5,0.5,0.5]) ; hold on; end for i=1:PN for j=1:PN if(lengthaddress(i,j)~=10000) line([firstaddress(i,1),firstaddress(j,1)],[firstaddress(i,2),firstaddress(j,2)],'Color','g','LineWidth',5);%划线 text((firstaddress(i,1)+firstaddress(j,1))/2,(firstaddress(i,2)+firstaddress(j,2))/2,num2str(lengthaddress(i,j)));%标注线段距离 end end end %% 最短路径 for p=1:m-1 if(route(p+1)~=20) line([firstaddress(route(p),1),firstaddress(route(p+1),1)],[firstaddress(route(p),2),firstaddress(route(p+1),2)],'Color','r','LineWidth',5);%划线 text((firstaddress(route(p),1)+firstaddress(route(p+1),1))/2,(firstaddress(route(p),2)+firstaddress(route(p+1),2))/2,num2str(lengthaddress(route(p),route(p+1))));%标注线段距离 else line([firstaddress(route(p),1),firstaddress(1,1)],[firstaddress(route(p),2),firstaddress(1,2)],'Color','r','LineWidth',5);%划线 text((firstaddress(route(p),1)+firstaddress(1,1))/2,(firstaddress(route(p),2)+firstaddress(1,2))/2,num2str(lengthaddress(route(p),route(p+1))));%标注线段距离 end end axis([0 250 0 400]) % 图形显示最优及平均函数值变化趋势 % figure(3); % plot(vx); % title('最优,平均函数值变化趋势'); % xlabel('Generations'); % ylabel('f(x)'); % hold on; % plot(vmfit,'r'); % hold off;

    runtime=toc ```

    展开全文
  • 用通俗的语言来描述的话,首先我们的目标是寻找从i到点j的最短路径。从动态规划的角度看问题,我们需要为这个目标重新做一个诠释(这个诠释正是动态规划最富创造力的精华所在)。 //Floyd算法求解任意个顶点的...
  • matlab程序,找出网络中确定两点间的所有最短路径。 注意:输入的矩阵为邻接矩阵。如果两点间没有相邻,请将参数设较大数,例如点i和点j间没有相邻,则将Aij设为999。
  • NULL 博文链接:https://touch-2011.iteye.com/blog/1076031
  • 算法设计与分析、Floyd算法、最短路径问题、任意两点之间的最短距离、
  • 给定两个顶点,给出两个顶点的最短路径(如果没有连通,请给出)。把图进行可视化展示(一个适当大小的图),同时把计算的结果可视化展示。 环境 操作系统: Windows 10 X64 IDE: visual studio 2017 语言:C# ...
  • C++ DijkStra最短路径(输出两点最短路径与线路)

    万次阅读 多人点赞 2018-07-03 21:22:51
    因为Dijkstra迪杰斯特拉算法每次都是从...(1)图算法之最短路径(Dijkstra) (2)DijkStra最短路径的C++实现与输出路径  (3) 柳诺-【最短路径】之Dijkstra算法 (4) DijkStra最短路径的C++实现与输出路径 ...
  • 这是使用BFS从(0,0)到(0,m-1)的矩阵中的最短路径的python实现 . 您可以将其更改为适合变量 .n,m,k1,k2=[int(i) for i in input().split()]arr=[[int(j) for j in input().split()] for i in range(n)]x=[[-1 for ...
  • 给定一个GeoJSON LineString网络,GeoJSON路径查找器将找到网络中两点之间的最短路径。 这对于在较小的网络中自动路由搜索可能很有用,在该网络中设置像OSRM这样的真实路由计划器需要太多工作,或者您只需要在...
  • 这题我在上个代码中已经写出来对应函数了,就在贴一遍吧。 题目 ...//记录对应的最小路径的前驱,例如p(1,3) = 2 说明顶点1到顶点3的最小路径要经过2 void createNewGraphList(struct graphLi
  • 迪杰斯特拉(Dijkstra)算法是最短路径算法,用于计算一个节点到其他节点的最短路径。 它的主要特点是以起始为中心一层一...注:如果还需要记录最短路径,集合S还得记录该路径经过的 操作步骤 ...
  • 地图最短路径算法

    2019-03-24 23:28:35
    最短路径算法,做了堆优化有测试用例,可以随机生成地图,地图中的数字代表的是该点的高度,高度差为两点的距离
  • Floyd算法(任意两点间的最短路径

    万次阅读 多人点赞 2017-11-10 11:42:14
    Floyd(弗洛伊德)算法是解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题,同时也被用于计算有向图的传递闭包。Floyd算法的时间复杂度为O(N3),空间复杂度为O(N2)。 算法思想:  ...
  • 最短路径-任意两点间最短距离-Floyd算法的matlab实现(详细教程) 目录 简介 核心思路 优缺点分析 算法过程 简介 Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的...
  • 问题描述:设计一个算法,计算出给定二叉树中任意2个结点之间的最短路径。编程任务:对于给定的二叉树,和二叉树中结点对,编程计算结点对之间的最短路径。数据输入:由文件input.txt给出输入数据。第1行有1...
  • 1.求两点之间的最短路径: (1)求从某个源点到其余各点的最短路径:Dijstra(迪杰斯特拉)算法; (2)求每一对顶点之间的最短路径:Floyd(弗洛伊德)算法。 2.Dijstra算法的基本思想:依据最短路径的长度递增...
  • 和Dijkstra算法一样,弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。 弗洛伊德算法...
  • ​ 重点:dijkstra算法按层计算其余到源点的最短距离,层层扩展。1. dijkstra算法求解目标:找到图中源点到其余最短距离,是单源点最短距离算法。整体思路:每一步都寻找到与源点最近的,层层扩展,是贪心...
  • 本程序是用matlab语言实现,Dijkstra算法主要用来寻找任意两点间的最短路径
  • 单源点最短路径  单源点最短路径问题:给定图G=(V,E),每条边(i,j)上都标有非负实数C[i][j]作为它的权;在图中指定一个顶点v作为源点,求从v到其他每个顶点的最短路径长度。单源最短路问题的进一步推广是求每对...
  • Day12:单源最短路径的C语言实现

    千次阅读 2022-03-17 12:26:45
    单源最短路径Dijkstra算法的思想与实现
  • //用于存储到各点最短路径的权值和 void ShortestPath_Floyd(MGraph G, Patharc P, ShortPathTable D) { int v, w, k; for (v = 0; v ; ++v) //初始化 { for (w = 0; w ; ++w) { D[v][w] = G.arc[v][w]; P[v][w] = ...
  • 最短路径问题,一个经典算法问题。本文粗略总结了一种常见的最短路径算法,...一、单源最短路径给定图G,求对s->t之间的最短路径,该问题使用经典的dijkstra算法即可解决,时间复杂度O(V^2)。基本思想:个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,179
精华内容 12,071
关键字:

给定两点最短路径

友情链接: Tcpchat.rar