灌溉问题.doc

灌溉问题下图是一个农田图，边表示田埂，周围是灌溉渠，问至少要挖开多少个田埂才能使每一块地都能灌上水？给出挖开田埂的一个方案。摘要：本文巧妙地解决了在相同的结果前提下，解决了即灌溉了所有的地，并且挖了最少的田埂的最优运行方案的问题。这属于一个典型的寻找最小路径问题，该问题解法众多，本文紧扣题目，合理假设，通过Dijkstra算法建立了模型，为较准确的分析和评价各种送货方案并确立最优方案提供了科学的依据。本文首先建立了将120个地都可以被灌溉渠锁灌溉到的分析和评价模型。文中使用最小生成树法的改进模型，采用单一目标规划问题，对路程进行优化，经过计算分析评价，结果显示：在把所有的地都灌溉到时，可以得到一个最优化挖开田埂方式。本文模型中只要考虑路线最短，即挖开最少的田埂。采用单一目标规划问题模型。得出如下结论：挖开的田埂最少，即实现了近似最优化。纵观全文，文章详细地对挖开田埂的方法进行了分析，使得确定了挖开田埂的最佳的路程方案。关键字：最佳路线 路程 Dijkstra算法 一问题重述1.1 问题背景现在农业效率越来越重要，灌溉是一种常见的农业方式，随之效率是第一生产力，要使得挖开最少的田埂使得每一块地都能灌上水，需要我们设计一个方案使其田埂最少的方案。题目中给出了一个实际的问题，并给出了地形示意图及各点连通图，且只能挖开这些联通田埂。我们需要综合起来上述问题，进行分析评估最优化。并对该实际问题给出合理的配置方案。现在的问题如下：已知有20块田地，要使得每块田到最后倒要被灌溉到。30个可以被挖开的田埂，田埂周围才有灌溉渠，挖开其余的路线没有办法进行灌溉。不考虑田埂挖不开的情况，不考虑灌溉渠是否能被使用的情况，不考虑挖开田埂后田没有办法被灌溉到的情况。设计最少路线与方式，标出需要挖开的田埂。二问题的假设对于上述实际问题，我们给了合理的假设：（1） 假定目前该农场所有的田埂均可以被顺利挖开，即不出现挖到一半无法进行下去的情况；（2） 所有的灌溉渠都可以正常使用，即挖开了田埂以后，灌溉渠可以成功的将田埂两端的天地灌溉；（3） 对于某些至少要经过两次以上的田地，认为第二次或第二次以上的灌溉不会对其造成影响；（4） 其他没有田埂的地方，认为没有灌溉渠，即，挖开了两块田地直接的道路依旧不会被灌溉到；（5） 在灌溉到了田地以后，不会因为其他原因造成影响。（6） 因为只需要考虑挖开最少的田埂，且图中田埂为两个相邻的田地之间的连接，所以可以假设两个相邻之间的田埂的长度相等三参数的假定Vi(i=1;2;3;420) 表示所有的田地表示每两个田地之间的田埂S表示挖开田埂的个数四模型的建立与求解将农田网图中，每个田地看作图中的一个节点，各田地之间的田埂看作图中对应节点间的边，各个田埂的长度看作对应边上的权，所给农田网就转化为加权网络图，问题就转化为在给定的加权网络图中寻找从给定点出发，行遍所有顶点，使得总权（路程或时间）最小，此即最佳灌溉问题.算法，可以引用著名的Dijkstra算法Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。 Dijkstra算法中设置了一顶点集S，从源点s到集合中的顶点的最终最短路径的全职均已经确定。算法反复选择具有最短路径的顶点x属于V-S，并将X加入S中，对u的所有出边进行松弛。这里描述的是从节点1开始到各点的dijkstra算法，其中Wa-b表示a-b的边的权值，d(i)即为最短路径值) 1 置集合S=2,3,.n, 数组d(1)=0, d(i)=W1-i(1,i之间存在边) or +无穷大(1.i之间不存在边) 2 在S中，令d(j)=mind(i),i属于S，令S=S-j，若S为空集则算法结束，否则转3 3 对全部i属于S,如果存在边j-i，那么置d(i)=mind(i), d(j)+Wj-i，转2Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将 加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度算法具体步骤 （1）初始时，S只包含源点，即S，v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或 ）（若u不是v的出边邻接点）。 （2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。 （3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。 （4）重复步骤（2）和（3）直到所有顶点都包含在S中。问题解答：1. 将最左边的点设做源点，即V1为源点，此时S=0,2. 然后将V2,V3，加入S中，,此时V2,V3为中间点.此时S=23. V2可以将V4，V7加入，V3可以将V5,V4加入，因为V4重复，所以此时V4,V5,V7为中间点。S=5。4. V4将V6加入，V5将V6,V8,V11加入，V7将V6,V9,V14加入，因为V6重复，所以此时V6,V8,V9,V11,V14为中间点。S=105. V6将V8加入，与第四步重复，所以不考虑。V8将V9，V10加入,V9与上一步重复，所以只讲V10加入。V9无法延伸。V11将V10，V18加入，V14将V10,V13,V17加入。舍去所有的重复。可以得到V10,V13,V17,V18为中间点。S=146. V10将V11，V14加入，舍去；V13将V12,V16加入，V17将V19,V20加入，V18将V19,V20加入。舍去所有的重复。可以得到V12,V16,V19,V20为中间点。S=187. V12将V15加入，V16将V15加入。V19,V20无法延伸。所以终点为V15。S=19.8. 将以上的田埂挖开后，所有的田地都会被灌溉。会发现有的农田会被重复灌溉。其中V6,V9,V10，V15,V16,V18,V19,V20被单一灌溉。9. V6和V4，V9和V7,v10和V8，V15和V12，V16和V13，V18和V11，V19和V17，V20和V17，之间相连接。10. 可以将第9步中的连接灌溉渠从图中合理排除11. 得到了剩下的图形中，使用第9步的方法，除去剩下的田埂。12. 这样就得到了。V1和V2,V3和V5，V4和V6，V7和V9，V8和V10，V12和V15，V14和V13和V16,V11和V18，V17和V19和V20。13. 得到结果为S=11四 模型检验 对于上述结果，比较符合模型假设；检验可通过。 所以上述方案可为最优解，我们假设顺利通过。 五模型的进一步讨论及推广（1）用上述方法可以解决农田的灌溉问题，符合在实际情况中的实践问题。（2）本题中每个田埂上面都可以弄个灌溉渠，如果只有一个灌溉渠，即田埂只能是一条不间断的线段，这时又该如何考虑。六模型的综合评价对于以上建立的多个模型，具有以下优缺点:优点：(1) 适用于同类可以用图论建模求解的农田灌溉问题，运用相应算法上机求解，易于推广到节点较少的情况(2) 运用上述最小生成树法可得到一个图表，可以一目了然的的确定大概路线。而在实际生活中，即需要这样的粗略路径来达到实际的目的。缺点：（1） 所求的最佳送货路线是近似最优解，而类似的近似最优解可以不止一个，未能在理论上证明本问题最优解得情况。（2） 本题采用Dijkstra算法，得出基本的路线图，得出具体情况 确实费了一番功夫，运算量相对也较大。参考文献 数学模型（第三版）姜启源 数学建模与数学实验 （第三版）赵 静#include #include using namespace std; const int MaxNum=1000000; /边权最大值 int n; /节点数目 int dist501; /到节点1的最短路径值 bool state501; /节点被搜索过状态指示 int data501501; /邻接矩阵 /查找权值最小的节点 int findmin() int minnode=0, min=MaxNum; for(int i=1; i=n; i+) if (disti n; for(int p=1; p=n; p+) for(int q=1; q datapq; if (datapq=0) datapq=MaxNum; /初始化 for(int i=1; i=n; i+) disti=data1i; state1=true; int done=1; while (donen) int node=findmin(); if (node!=0) done+; /找到的点的数目加1 statenode=true; /标记已经找到了从节点1到节点node的最短路径 for(int i=1; idistnode+datanodei) & (!statei) disti=distnode+datanodei; else break; for(int k=1; k=n; k+) if (distk=MaxNum) out-1; else outdistk; if (k=n) outendl; else out ; in.close(); out.close(); return 0; Pascalprogram dijkstra; var state:array1.100of boolean; data:array1.100,1.100of longint; n,i,j,k,min,node:longint; begin assign(input,dijkstra.in); assign(output,dijkstra.out); reset(input); rewrite(output); fillchar(data, sizeof(data), 0); fillchar(state,sizeof(state),0); readln(n); for i:=1 to n do for j:=1 to n do begin read(datai,j); if datai,j=0 then datai,j:=maxint; end; state1:=true; for k:=2 to n do begin min:=maxint; 查找权值最小的点为node node:=1; for i:=2 to n do if (data1,imin)and(statei=false) then begin min:=data1,i; node:=i; end; 更新其他各点的权值 stat