网站设计实训心得,做网站 租服务器,做设计素材在哪个网站,搜索引擎优化包括哪些方面目录 前言演示问题介绍思路代码复现尾言 前言 大家好#xff0c;我是Ericam_。 近些时间#xff0c;通过一个项目接触到了邮递员算法问题#xff0c;还是挺有意思的#xff08;虽然做起来经历了不少的困难#xff09;。最后勉强复现了吧#xff0c;写个文章就当记录一下。… 目录 前言演示问题介绍思路代码复现尾言 前言 大家好我是Ericam_。 近些时间通过一个项目接触到了邮递员算法问题还是挺有意思的虽然做起来经历了不少的困难。最后勉强复现了吧写个文章就当记录一下。 演示 问题介绍 1962年有管梅谷先生提出中国邮递员问题简称CPP。一个邮递员从邮局出发要走完他所管辖的每一条街道可重复走一条街道然后返回邮局。任何选择一条尽可能短的路线。 当邮递员可以每条道路仅走一次便返回起点那该路线一定是最短的。而欧拉回路恰巧满足这种条件。那什么才是欧拉回图呢
什么是欧拉回图 欧拉回图每个点的入度和出度必须相等起始点也一样也就是说每个节点的度应该是偶数个。 但在实际生活中基本上这种特殊情况是不存在的所以我们想要解决邮递员问题首要便是要构造欧拉回图只要能够花费最小的代价来构造欧拉回图那么邮递员问题便得到解决了。
所以首先我们要找到图中所有的奇度点奇度点个数一定是偶数个这里就不证明了当奇度点两两相连后找到耗费最少的一组组合即可。
思路 以下给出我个人的思路如有疏漏请多包涵~ 首先我们需要找到图中所有的奇度点接下来我们需要比较路径长度。由于图一定是连通图所以每两个点之间都会存在直接或间接的路径但两个点之间可能存在多条路径所以我们需要先求出点与点之间的最短路径。由于是多源最短路径求解所以需要使用Floyd算法来解决问题。接下来将奇度点两两分组计算路径长度然后挑选耗费最少的一个分组。构建欧拉回图解决问题~
代码复现 由于其他原因不会公开源代码。但可以分享关键操作~ 1.首先如何计算出奇度点 遍历邻接矩阵挑选出度数为奇数的点即可。用vector来存放顶点序号。2.Floyd最短路径求解
常规的Floyd算法求解利用path来存放中介点方便回溯路径。
//Floyd最短路径计算函数
void MGraph::Floyd(){//更新disfor(int i0;ithis-n;i)for(int j0;jthis-n;j)if(this-edges[i][j]!-1){this-dis[i][j] this-edges[i][j];this-path[i][j] -1;}for(int k0;kthis-n;k)for(int i0;ithis-n;i)for(int j0;jthis-n;j)if(this-dis[i][k]this-dis[k][j]this-dis[i][j]){this-dis[i][j] this-dis[i][k]this-dis[k][j];this-path[i][j] k;}
}3 . 通过DFS来分组寻找耗费最小的组合。难点
这里是我觉得最难的一点同样我的方法也不够好。之后想过很多改进但甚至不如原方法… 个人思路 利用vector v来存放点每次挑选两个点作为一组存入当v中点个数等于奇度点个数时一个组合便完成了计算v中每个组的两个点的路径长度并求和然后判断是否最小。 //组合(输出所有奇数点的排列组合)
void MGraph::DFS(vectorintv){//组合完成if(v.size()this-odd_vex.size()){float sum0.0;for(int i0;iv.size();i2){sum this-dis[v[i]][v[i1]];}if(sumthis-min_addDis){this-mindis_oddvex v;this-min_addDis sum;}return;}for(int i0;ithis-odd_vex.size()-1;i){//如果v中已存在节点iif(this-exists(v,this-odd_vex[i]))continue;for(int ji1;jthis-odd_vex.size();j){//如果v中已存在节点jif(this-exists(v,this-odd_vex[j]))continue;vectorintnew_v(v);new_v.push_back(this-odd_vex[i]);new_v.push_back(this-odd_vex[j]);this-DFS(new_v);}}
}4 .求邮递员行走路线
这里就如同迷宫问题一样往前走即可走过去便删除走过的边某些边可能存在多条。
//求欧拉路径
void MGraph::getEulerpath(int v){for(int i0;ithis-n;i){if(this-edges_num[v][i]0){this-edges_num[v][i]--;this-edges_num[i][v]--;this-euler_path.push(i);//当欧拉路径中顶点个数等于图总边数1(因为返回起点)寻找完成if(this-euler_path.size() this-e1){this-finish_eulerpath 1;return;}getEulerpath(i);if(this-finish_eulerpath)return;this-euler_path.pop();this-edges_num[v][i];this-edges_num[i][v];}}
}尾言
感谢您的阅读如有问题可私信有偿代写代码~ 最后如果本篇文章对您有帮助恳求一键三连/(ㄒoㄒ)/~~ 再不济点个赞吧 φ(*0)
