中国邮递员问题matlab

中国邮递员问题的matlabchengxuclear;clc;M=inf;a(1,1)=0;a(1,36)=10.3;a(1,37)=5.9;a(1,38)=11.2; a(1,50)=6.0;a(2,2)=0;a(2,50)=9.2; a(2,5)=8.3;a(2,3)=4.8;a(3,3)=0;a(3,39)=8.2; a(3,38)=7.9;a(4,4)=0;a(4,39)=12.7; a(4,8)=20.4;a(5,5)=0;a(5,6)=9.7; a(5,39)=11.3; a(5,48)=11.4;a(6,6)=0;a(6,7)=7.3;a(6,47)=11.8; a(6,48)=9.5;a(7,7)=0;a(7,47)=14.5; a(7,40)=7.2; a(7,39)=15.1;a(8,8)=0;a(8,40)=8.0;a(9,9)=0;a(9,40)=7.8; a(9,41)=5.6;a(10,10)=0;a(10,41)=10.8;a(11,11)=0;a(11,42)=6.8; a(11,45)=13.2; a(11,40)=14.2;a(12,12)=0;a(12,43)=10.2; a(12,42)=7.8;a(12,41)=12.2;a(13,13)=0;a(13,45)=9.8;a(13,44)=16.4;a(13,42)=8.6; a(13,14)=8.6; a(14,14)=0;a(14,43)=9.9; a(14,15)=15.0;a(15,15)=0;a(15,44)=8.8;a(16,16)=0;a(16,17)=6.8;a(16,44)=11.8;a(17,17)=0;a(17,22)=6.7; a(17,46)=9.8;a(18,18)=0;a(18,46)=9.2; a(18,45)=8.2; a(18,44)=8.2;a(19,19)=0;a(19,20)=9.3; a(19,45)=8.1; a(19,47)=7.2;a(20,20)=0;a(20,21)=7.9;a(20,25)=6.5; a(20,47)=5.5;a(21,21)=0;a(21,23)=9.1;a(21,25)=7.8; a(21,46)=4.1;a(22,22)=0;a(22,23)=10.0; a(22,46)=10.1;a(23,23)=0;a(23,24)=8.9; a(23,49)=7.9;a(24,24)=0;a(24,27)=18.8; a(24,49)=13.2;a(25,25)=0;a(25,49)=8.8; a(25,48)=12.0;a(26,26)=0;a(26,27)=7.8; a(26,49)=10.5; a(26,51)=10.5;a(27,27)=0;a(27,28)=7.9;a(28,28)=0;a(28,52)=8.3; a(28,51)=12.1;a(29,29)=0;a(29,52)=7.2; a(29,51)=15.2; a(29,53)=7.9;a(30,30)=0;a(30,32)=10.3; a(30,52)=7.7;a(31,31)=0;a(31,33)=7.3;a(31,32)=8.1; a(31,53)=9.2;a(32,32)=0;a(32,33)=19;a(32,35)=14.9;a(33,33)=0;a(33,35)=20.3; a(33,36)=7.4;a(34,34)=0;a(34,35)=8.2; a(34,36)=11.5; a(34,37)=17.6;a(35,35)=0;a(36,36)=0;a(36,53)=8.8;a(36,37)=12.2;a(37,37)=0;a(37,38)=11.0;a(38,38)=0;a(38,50)=11.5;a(39,39)=0;a(41,41)=0;a(42,42)=0;a(43,43)=0;a(44,44)=0;a(44,45)=15.8;a(45,45)=0;a(46,46)=0;a(47,47)=0;a(48,48)=0;a(48,49)=14.2; a(48,50)=19.8;a(49,49)=0;a(50,50)=0;a(50,53)=12.9;a(50,51)=10.1;a(51,51)=0;a(52,52)=0;a(53,53)=0;% 用1、2 、3……35表示35个村：用36、37……53表示各乡镇。

§4.中国邮递员问题（Chinese Postman Problem）1．问题的提出例5. 一个邮递员从邮局出发投递信件, 然后再返回邮局, 如果他必须至少一次地走过他负责投递范围内的每条街道, 街道路线如下图所示, 问选择怎样的路线才能使所走的路为最短?5 6 78问题的图论表述：在赋权G=[V, E]上找一条经每条边至少一次的权最小的圈。

1960年山东师范学院管梅谷教授首先提出此问题，并设计了一个“奇偶点表上作业法”，后来发现此法不是多项式算法，1973年，Edmonds和Johnson给出一个多项式算法。

2．哥尼斯堡七桥问题18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥，将河中的两个岛和河岸连结，如下图所示。

城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。

3．Euler圈Euler圈：经图G的每条边的简单圈Euler图：具有Euler圈的图Euler图非Euler图下面讨论的图G允许有重边，且重边被认为是有区别的边。

伪Euler 圈：经图G 的每条边至少一次的圈点v 的次：与点V 关联的边的数目奇(偶)点：该点的次为奇(偶)数命题1：G 的奇点个数为偶数命题2：G 中有伪Euler 圈 ⇔ G 无奇点中国邮递员问题可表述为：在图G 中找一条权最小的伪Euler 圈。

对于邮递员来说，有些街道可能会重复走，原问题便转化为尽可能少走重复的 街道。

我们将这些重复的边组成的集合称可行集，即找最小的可行集。

命题3：E *是最小可行集 ⇔ωωμμμ()()()()*()*()e e e E E E e E E ≤∑∑∀μ∈∩∈∩\初等圈重复的边 非重复的边4．算法思路由命题1，简单图G 的奇点个数为偶数，可设为v 1 , v 2 , …, v 2k , 对每个1≤ i ≤k, 找v 2i − 1 至v 2i 的链p i ，将p i 的边重复一次。

生活中的趣味数学智慧树知到课后章节答案2023年下石河子大学第一章测试1.海王星的发现 , 又一次成功地证明了以运动定律和万有引力定律为基础的牛顿宇宙力学模型的合理性（）.A:错 B:对答案:对2.蝴蝶效应是谁发现的( ).A:奥古斯丁·路易斯·柯西 B:爱德华·诺顿·洛伦茨 C:约瑟夫·拉格朗日 D:约翰·卡尔·弗里德里希·高斯答案:爱德华·诺顿·洛伦茨3.SI模型实际上是（）模型.A:Logistic 模型 B:Malthus模型 C:Volterra模型答案:Logistic 模型4.用A表示进食而摄取的能量，B表示基础代谢消耗的能量，R表示活动而消耗的能量，那么（）表示由于能量的摄入而增加的体重。

A: B: C:答案:5.SI模型实际上是Volterra模型模型（）.A:对 B:错答案:错6.SIR模型建立的是传染病有免疫性——病人治愈后即移出感染系统（）。

A:错 B:对答案:对7.SIR模型建立的是传染病无免疫性——病人治愈成为健康人，健康人可再次被感染（）。

A:对 B:错答案:错8.减肥最好的方法是节食（）。

A:错 B:对答案:错9.减肥最重要的措施有（）。

A:服用肥药 B:多吃营养品 C:增加运动量 D:控制饮食量答案:增加运动量;控制饮食量10.下列哪些现象可以看成蝴蝶效应（）。

A:厄尔尼诺现象 B:美国发生的股市风暴 C:1997年金融危机答案:厄尔尼诺现象;美国发生的股市风暴;1997年金融危机第二章测试1.简单图指的是没有环的图（）.A:对 B:错答案:错2.下列哪些选项中的图可以一笔画（）A:恰有两个奇度点的图 B:都是偶度点的连通图 C:恰有一个奇度点的图 D:恰有两个奇度点的连通图答案:都是偶度点的连通图;恰有两个奇度点的连通图3.无圈的图就是树（）A:对 B:错答案:错4.本节渡河问题中的摆渡人经过( )次渡河可以将狼羊菜顺利运过河去.A:6 B:5C:8 D:7 答案:75.用先深搜索算法可以找到一个连通图的生成树（）.A:对 B:错答案:对6.下列哪个选项是正确的（）A:树一定有完备匹配 B:图G的最大匹配指的是图G的边数最多的匹配 C:完全图一定有完备匹配 D:完全二分图一定有完备匹配答案:图G的最大匹配指的是图G的边数最多的匹配7.关于四色猜想下列说法正确的是（）A:任何一个图，都可以用四种颜色来着色，使得任何两个相邻的面着不同的颜色。

【BZOJ5471】[FJOI2018]邮递员问题（动态规划）【BZOJ5471】[FJOI2018]邮递员问题（动态规划）题⾯给定平⾯上若⼲个点，保证这些点在两条平⾏线上，给定起点终点，求从起点出发，遍历所有点后到达终点的最短路径长度。

题解不会做，于是点开LOJ，点开除了std之外，照着打了⼀遍QwQ......然后再对着代码YY⼀遍就有了这篇东西。

强制令起点的位置是第0⾏(⽅便⽽已)。

在第0⾏枚举⼀个i，在第⼀⾏枚举⼀个j。

设f[j][0]表⽰第1⾏[j+1,n1]这些点已经⾛完，第0⾏[i,n0]已经⾛完，然后到达终点的最短路。

设f[j][1]表⽰第1⾏[j,n1]已经⾛完，第0⾏[i+1,n0]已经⾛完，然后达到终点的最短路。

把i按照从前往后或者从后往前的顺序枚举，到达起点就直接更新答案。

因为从起点出发可以向两个⽅向⾛，所以前后都要做⼀遍dp。

转移的话就是⼀堆讨论。

#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>using namespace std;#define MAX 10100inline int read(){int x=0;bool t=false;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=true,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return t?-x:x;}int n[2],ty[2],pos[2];double h,tx[2],x[2][MAX],f[MAX][2];double Dis(int i,int j){double d=fabs(x[0][i]-x[1][j]);return sqrt(d*d+h*h);}double ToEnd(int i,int j){double d=fabs(x[i][j]-tx[1]);return i==ty[1]?d:sqrt(h*h+d*d);}double Calc(){double ret=1e18;sort(&x[0][1],&x[0][n[0]+1]);sort(&x[1][1],&x[1][n[1]+1]);for(int i=n[0];i;--i){if(i==n[0])for(int j=n[1];j;--j){f[j][0]=j==n[1]?ToEnd(0,n[0]):min(f[j+1][1]+Dis(n[0],j+1),Dis(n[0],n[1])+x[1][n[1]]-x[1][j+1]+ToEnd(1,j+1));f[j][1]=j==n[1]?ToEnd(1,n[1]):f[j+1][1]+x[1][j+1]-x[1][j];}elsefor(int j=n[1];j;--j)if(j==n[1]){f[j][1]=min(f[j][0]+Dis(i+1,j),Dis(n[0],n[1])+x[0][n[0]]-x[0][i+1]+ToEnd(0,i+1)); f[j][0]+=x[0][i+1]-x[0][i];}else{f[j][1]=min(f[j][0]+Dis(i+1,j),f[j+1][1]+x[1][j+1]-x[1][j]);f[j][0]=min(f[j][0]+x[0][i+1]-x[0][i],f[j+1][1]+Dis(i,j+1));}ret=min(ret,x[0][i]-x[0][1]+tx[0]-x[0][1]+Dis(i,1)+f[1][1]);ret=min(ret,fabs(x[0][i]-tx[0])+x[0][i]-x[0][1]+Dis(1,1)+f[1][1]);if(x[0][i]<=tx[0]){ret=min(ret,tx[0]-x[0][1]+Dis(1,1)+f[1][1]);break;}}return ret;}int main(){scanf("%d%d%d%d%d%d%lf",&n[0],&n[1],&ty[0],&pos[0],&ty[1],&pos[1],&h); int r=0;if(ty[0])r=1,swap(n[0],n[1]),ty[0]^=1,ty[1]^=1;for(int t=0;t<=1;++t)for(int i=1;i<=n[t^r];++i)scanf("%lf",&x[t^r][i]);tx[0]=x[ty[0]][pos[0]];tx[1]=x[ty[1]][pos[1]];double ans=Calc();for(int t=0;t<=1;++t)for(int i=1;i<=n[t];++i)x[t][i]=20000-x[t][i];tx[0]=20000-tx[0];tx[1]=20000-tx[1];ans=min(ans,Calc());printf("%.2lf\n",ans);return 0;}Processing math: 100%。

中国邮递员问题matlab%中国邮递员问题：%step1；%求出奇点之间的距离；%求各个点之间的最短距离；%floyd算法；clear all; clc; A=zeros(9); A(1,2)=3; A(1,4)=1; A(2,4)=7; A(2,5)=4;A(2,6)=9;A(2,3)=2; A(3,6)=2 A(4,7)=2; A(4,8)=3;A(4,5)=5; A(5,6)=8; A(6,9)=1;A(6,8)=6; A(7,8)=2; A(8,9)=2; c=A+A’; c(find(c==0))=inf; m=length(c); Path=zeros(m); for k=1:m for i=1:m for j=1:m if c(i,j)>c(i,k)+c(k,j)c(i,j)=c(i,k)+c(k,j); Path(i,j)=k;end end end end c, Path h1=c(2,4); h2=c(2,6); h3=c(2,5); h4=c(4,6); h5=c(4,5); h6=c(6,5); h=[h1,h2,h3,h4,h5,h6]%step2;%找出以奇点为顶点的完全图的最优匹配；%算法函数Hung_function [Matching,Cost] = Hung_Al(Matrix) Matching = zeros(size(Matrix)); % 找出每行和每列相邻的点数num_y = sum(~isinf(Matrix),1);num_x = sum(~isinf(Matrix),2); % 找出每行和每列的孤立点数x_con = find(num_x~=0);y_con = find(num_y~=0); %将矩阵压缩、重组P_size = max(length(x_con),length(y_con));P_cond = zeros(P_size); P_cond(1:length(x_con),1:length(y_con)) = Matrix(x_con,y_con);if isempty(P_cond)Cost = 0;return end % 确保存在完美匹配，计算矩阵边集Edge = P_cond; Edge(P_cond~=Inf) = 0; cnum = min_line_cover(Edge); Pmax = max(max(P_cond(P_cond~=Inf)));P_size = length(P_cond)+cnum; P_cond = ones(P_size)*Pmax;P_cond(1:length(x_con),1:length(y_con)) = Matrix(x_con,y_con); %主函数程序,此处将每个步骤用switch命令进行控制调用步骤函数exit_flag = 1; stepnum = 1; while exit_flag switch stepnum case 1 [P_cond,stepnum] = step1(P_cond);case 2 [r_cov,c_cov,M,stepnum] = step2(P_cond); case 3 [c_cov,stepnum] = step3(M,P_size);case 4 [M,r_cov,c_cov,Z_r,Z_c,stepnum] = step4(P_cond,r_cov,c_cov,M);case 5 [M,r_cov,c_cov,stepnum] = step5(M,Z_r,Z_c,r_cov,c_cov);case 6 [P_cond,stepnum] = step6(P_cond,r_cov,c_cov); case 7 exit_flag = 0;end end Matching(x_con,y_con) = M(1:length(x_con),1:length(y_con)); Cost = sum(sum(Matrix(Matching==1))); %下面是6个步骤函数step1~step6 %步骤1：找到包含0最多的行，从该行减去最小值function [P_cond,stepnum] = step1(P_cond) P_size = length(P_cond); for ii = 1:P_size rmin = min(P_cond(ii,:)); P_cond(ii,:) = P_cond(ii,:)-rmin; end stepnum = 2; %步骤2：在P-cond中找一个0，并找出一个以该数0为星型的覆盖function [r_cov,c_cov,M,stepnum] = step2(P_cond) %定义变量r-cov，c-cov分别表示行或列是否被覆盖P_size = length(P_cond); r_cov = zeros(P_size,1);c_cov = zeros(P_size,1);M = zeros(P_size); for ii = 1:P_size for jj = 1:P_size if P_cond(ii,jj) == 0 && r_cov(ii) == 0 && c_cov(jj) == 0M(ii,jj) = 1; r_cov(ii) = 1;c_cov(jj) = 1;end end end % 重初始化变量r_cov = zeros(P_size,1);c_cov = zeros(P_size,1);stepnum = 3; %步骤3：每列都用一个0构成的星型覆盖，如果每列都存在这样的覆盖，则M为最大匹配function [c_cov,stepnum] = step3(M,P_size) c_cov = sum(M,1); if sum(c_cov) == P_size stepnum = 7; else stepnum = 4; end %步骤4：找一个未被覆盖的0且从这出发点搜寻星型0覆盖。