扫雪问题的数学模型.doc

扫雪问题摘 要本问题是一个寻求最佳路线的问题，通过分析，根据图论中的E图和H图的算法，以及改良圈的算法，把每个公交路线看做节点，根据路线图可构造一个赋权图G=,其中扫雪路线应是一条经过G的每条边至少一次的回路。若G是Euler图，则任何一条Euler回路是最短投递路线,都满足条件，针对这种情况，Fleury提出一种算法，能够在Euler图中找出Euler路径，解决了扫雪问题；若G 不是Euler图，则扫雪路线将重复经过某些街道，最优扫雪路线应使得重复经过的街道的总长度最短。这就需要根据改良圈的算法解决这个问题，从而解决最佳路线的问题。一、问题重述 由于马里兰州威考密科县中路线的错综复杂，而延伸出了扫雪问题地图中的实线表示马里兰州威考密科县中扫雪区域中的二车道马路，虚线表示州属高速公路。一场雪后，从位于地图标记地点以西英里的二处车库派出二辆扫雪车。求用二辆车扫清马路上的雪的有效方法，扫雪车可以利用高速公路进出扫雪区。（假设扫雪车既不会发生故障也不停顿，在交叉路口不需特别的扫雪方二、问题的分析本问题是一个寻求最佳路线的问题，通过分析，根据图论中的E图和H图的算法，以及改良圈的算法，把每个公交路线看做节点，根据路线图可构造一个赋权图G=,其中扫雪路线应是一条经过G的每条边至少一次的回路。若G是Euler图，则任何一条Euler回路是最短投递路线,都满足条件，针对这种情况，Fleury提出一种算法，能够在Euler图中找出Euler路径，解决了扫雪问题；若G 不是Euler图，则扫雪路线将重复经过某些街道，最优扫雪路线应使得重复经过的街道的总长度最短。这就需要根据改良圈的算法解决这个问题，从而解决最佳路线的问题。三、模型的假设与符号说明1. 模型的假设（1）假设在扫雪过程中不考虑天气，故障因素的影响（2）假设扫雪车既不会发生故障也不停顿，在交叉路口不需特别的扫雪方（3）两辆扫雪车的性能一样，且在扫雪过程中不会出现任何的耽搁.2. 符号说明V：代表公路的边即边集E;代表各个公路的交叉点即顶点集U：代表顶点集合四、模型的准备 因为派出了两辆车去扫雪，所以必须考虑两辆车的分配工作，只有合理的分配这两辆车，才能使资源得到合理的配置，下面我们来考虑这两辆车的分配问题，如果能把道路分成俩部分，使得两部分都是联通的，又第一部分的总长度，与第二部分的总长度相等，两辆车都在各自分得的那部分单车进行扫雪，但是对一般的路往往是不行的，比如本道题的道路是星形的道路，所以根据路的具体情况，我们把路分为南片和北片俩个分别连通的，切使俩片的工作量相等，如果部相等，我们可以根据需要在边界线处稍作调整，从而使工作量相等，观察此具体形势，从A车出发点向东行，粗实线以北归A车扫，以南归B车五、模型的建立（和求解）地图是Euler图的情形这种情况，只需求出地图相应的图上的一条Euler回路，且按寻找这条Euler回路时边的出现顺序来安排扫雪的工作顺序即可（设寻Euler回路）时从高速公路上一路口开始，把路口（例如十字路口，丁字路口）是为图的顶点，地图上的道路段是为边）在Euler图上求取Euler回路，可用下面的Fleury算法Fleury算法（1）function T =Fleuf1(d)n=length(d);b=d;b(b=inf)=0;b(b=0)=1;m=0;a=sum(b);eds=sum(a)/2;ed=zeros(2,eds);vexs=zeros(1,eds+1);matr=b;for i=1:n if mod(a(i),2)=1 m=m+1; endendif m=0 fprintf(there is not exist Euler path.n); T=0; c=0;endif m=0 vet=1; flag=0; t1=find(matr(vet,:)=1); for ii=1:length(t1) ed(:,1)=vet;t1(ii); vexs(1,1)=vet; vexs(1,2)=t1(ii); matr(vexs(1,2),vexs(1,1)=0; flagg=1; tem=1; while flagg flagg,ed=edf(matr,eds,vexs,ed,tem); tem=tem+1; if ed(1,eds)=0 & ed(2,eds)=0 T=ed; T(2,eds)=1; c=0; for g=1:eds c=c+d(T(1,g),T(2,g); end flagg=0; break; end end endend Tc 若图中的扫雪街道不是E图则扫雪路线将重复经过某些街道，最优扫雪路线应使得重复经过的街道的总长度最短，与最短路问题相反，我们试图寻找一个比较好的方法，但不一定是最优解；首先给出近似最优的改良后的最邻近算法，称为改良圈算法，改良圈算法是一种近似算法，给出的结果不一定是最优的，但是有理由认为它常常是比较好的，这就是类似哈密顿图的解决方法function d1=glf(d)n=size(d,2);c=linspace(1,n,n) 1;c1=c;if n3 for v=4:n+1 for i=1:(v-3) for j=(i+2):(v-1) if(d(c(i),c(j)+d(c(i+1),c(j+1)d(c(i),c(i+1)+d(c(j),c(j+1) c1(1:i)=c(1:i); for k=(i+1):j c1(k)=c(j+i+1-k); end c1(j+1):v)=c(j+1):v); end end end endelseif n=3 if n=2 fprintf(It does not exist hamilton cicle.); else fprintf(Any circle is the right answer.); endendc=c1;d1=0;for i=1:n d1=d1+d(c(i),c(i+1);endcd1我们也可以根据最小生成树的Prim算法的=思想来解决这一问题从连通图G=的某一顶点V出发选择与其关联的具有最小权的边（，V）将其顶点加入到生成树的顶点集合U中，以后每一步从一个顶点在U中而另一顶点不在U中的各条边中选择权值最小的边（U,V）把它的顶点加入到集合U中，如此下去，直到图中的所有顶点都加入到生成树顶点集合U中诶之，这时得到一棵最小生成树该算法的matlab程序为：function T =primf(a)l=length(a);a(a=0)=inf;k=1:l;listV(k)=0;listV(1)=1;e=1;while(ea(i,j) min=a(i,j); b=a(i,j); s=i; d=j; end end end end listV(d)=1; distance(e)=b; source(e)=s; destination(e)=d; e=e+1;endT=source; destination;for g=1:e-1 c(g)=a(T(1,g),T(2,g);endTc 六、模型的推广与改进方向该模型解决了现实生活中因为道路的错综复杂而产生的扫雪盲目以及困难等问题，避免了不必要的扫雪劳动，该模型也可以推广应用于邮递员送信等的邮递问题，避免了跑过多的冤枉路，也可以应用与旅游推销等，以及鞋带的多种缠绕方法。该模型可以向多辆车的扫雪问题方面进行改进等。七、模型的优缺点