资源描述：
《扫雪问题的数学模型》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、扫雪问题摘要本问题是一个寻求最佳路线的问题，通过分析，根据图论中的E图和H图的算法，以及改良圈的算法，把每个公交路线看做节点，根据路线图可构造一个赋权图G=,其中扫雪路线应是一条经过G的每条边至少一次的回路。若G是Euler图，则任何一条Euler回路是最短投递路线,都满足条件，针对这种情况，Fleury提出一种算法，能够在Euler图中找出Euler路径，解决了扫雪问题；若G不是Euler图，则扫雪路线将重复经过某些街道，最优扫雪路线应使得重复经过的街道的总长度最短。这就需要根据改良圈的算法解决这个问题，从而解决最佳路线的问题。一、问题重述由于马里兰州威考密科县中路线的错综复
2、杂，而延伸出了扫雪问题地图中的实线表示马里兰州威考密科县中扫雪区域中的二车道马路，虚线表示州属高速公路。一场雪后，从位于地图＊标记地点以西４英里的二处车库派出二辆扫雪车。求用二辆车扫清马路上的雪的有效方法，扫雪车可以利用高速公路进出扫雪区。（假设扫雪车既不会发生故障也不停顿，在交叉路口不需特别的扫雪方二、问题的分析本问题是一个寻求最佳路线的问题，通过分析，根据图论中的E图和H图的算法，以及改良圈的算法，把每个公交路线看做节点，根据路线图可构造一个赋权图G=,其中扫雪路线应是一条经过G的每条边至少一次的回路。若G是Euler图，则任何一条Euler回路是最短投递路线,都满足条件，
3、针对这种情况，Fleury提出一种算法，能够在Euler图中找出Euler路径，解决了扫雪问题；若G6不是Euler图，则扫雪路线将重复经过某些街道，最优扫雪路线应使得重复经过的街道的总长度最短。这就需要根据改良圈的算法解决这个问题，从而解决最佳路线的问题。三、模型的假设与符号说明1.模型的假设（1）假设在扫雪过程中不考虑天气，故障因素的影响（2）假设扫雪车既不会发生故障也不停顿，在交叉路口不需特别的扫雪方（3）两辆扫雪车的性能一样，且在扫雪过程中不会出现任何的耽搁.2.符号说明V：代表公路的边即边集E;代表各个公路的交叉点即顶点集U：代表顶点集合四、模型的准备因为派出了两辆车去扫雪，所以必
4、须考虑两辆车的分配工作，只有合理的分配这两辆车，才能使资源得到合理的配置，下面我们来考虑这两辆车的分配问题，如果能把道路分成俩部分，使得两部分都是联通的，又第一部分的总长度，与第二部分的总长度相等，两辆车都在各自分得的那部分单车进行扫雪，但是对一般的路往往是不行的，比如本道题的道路是星形的道路，所以根据路的具体情况，我们把路分为南片和北片俩个分别连通的，切使俩片的工作量相等，如果部相等，我们可以根据需要在边界线处稍作调整，从而使工作量相等，观察此具体形势，从A车出发点向东行，粗实线以北归A车扫，以南归B车五、模型的建立（和求解）地图是Euler图的情形这种情况，只需求出地图相应的图上的一条E
5、uler回路，且按寻找这条Euler回路时边的出现顺序来安排扫雪的工作顺序即可（设寻Euler回路）时从高速公路上一路口开始，把路口（例如十字路口，丁字路口）是为图的顶点，地图上的道路段是为边）在Euler图上求取Euler回路，可用下面的Fleury算法Fleury算法（1）functionT=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;6fori=1:nifmod(a(i),2)==1m=m+1;end
6、endifm~=0fprintf('thereisnotexistEulerpath.');T=0;c=0;endifm==0vet=1;flag=0;t1=find(matr(vet,:)==1);forii=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;whileflagg[flagg,ed]=edf(matr,eds,vexs,ed,tem);tem=tem+1;ifed(1,eds)~=0&ed(2,eds)~=0T
7、=ed;T(2,eds)=1;c=0;forg=1:edsc=c+d(T(1,g),T(2,g));endflagg=0;break;endendendendTc若图中的扫雪街道不是E图则扫雪路线将重复经过某些街道，最优扫雪路线应使得重复经过的街道的总长度最短，与最短路问题相反，我们试图寻找一个比较好的方法，但不一定是最优解；首先给出近似最优的改良后的最邻近算法，称为改良圈算法，改良圈算法是一种近似算法，给出
