《算法设计与分析输油管道问题实验报告借鉴文章》由会员分享，可在线阅读，更多相关《算法设计与分析输油管道问题实验报告借鉴文章（20页珍藏版）》请在金锄头文库上搜索。
1、题目: 输油管道问题学 号0091313000913133学生姓名张一楠朱玉婷专业（班级）09计本1班设计题目 输油管道问题 设计技术参数系统平台：windows 7开发工具：Microsoft Visual C+ 6.0设计要求1. 掌握问题分析的方法与步骤，选择合适的方法解决问题。2. 选择合适的算法编写程序。工作计划1：熟悉题目并理解，及找寻相关资料。2：根据题目设计并分析算法。3：使用Visual C+实现。4：完成设计报告参考资料吕国英.算法设计与分析.北京:清华大学出版社,2009摘 要本实验，我们通过综合应用算法解决了实际生活中的输油管道问题，通过比较各种算法的时间复杂度以及解决
2、效率，采用了算法中以分治法为基础的随机划分来解决问题，利用随机选择方法找到各个油井的中位数，通过讨论论证了中位数即最优管道位置。 信息奥赛中一个问题有多个算法解决，通过比较不同算法解决问题的效率，选择最高效的一个。在输油管道问题这个实验中得到运用。关键词：算法设计，分治法，随机划分，随机选择，中位数目录1 需求分析41.1 实验内容41.2 系统的基本逻辑模型41.3 确定目标系统的功能.52 总体设计52.1问题分析52.2解题思路62.3解题方法.72.3.1算法思想.72.3.2算法分析.73 详细设计93.1 具体描述93.2 程序分析113.2.1程序代码.113.2.2程序结果.1
3、44 总结164.1 设计体会164.2 反思总结 16参考文献.17绿茶红a1. 需求分析1.1.实验内容某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x坐标（东西向）和y坐标（南北向）,应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道的最优位置。给定n口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。1.2.系统的基本逻辑模型设给定的n口油井的位置坐标为：（x0,y0),(x1,y1),(x
4、2,y2),(xn-1,yn-1)。由于平面上的距离满足三角不等式，故每个油井到主管道的最短距离就是该油井到主管道的垂直距离。由此可知，所述问题可表述为求平面上的一条直线到若干点的最短路径，通过总体设计中的解题思路我们论证得出只要该条直线处在所有点的中间位置就能保证最后的距离最短。根据题意，给定了n个油井的位置，因此首先从文件读取每个油井的坐标，再在这个基础上对各个油井的y坐标进行排序，通过随机选择算法找到它们的中位数，即可得到求出最短距离。 求出最短距离求取中位数随机划分 油田位置1.3.确定目标系统的功能通过本实验的设计，我们可以找到一个到各个油井之间的长度总和最小的输油管道，确定出输油管
5、道的位置，并且计算出长度之和。在实际生活中，本实验的程序设计，可以节省工程的耗资，并且也可以省去人工计算的繁琐。2. 总体设计系统设计一般分为总体设计和详细设计。经过需求分析阶段的工作，已经清楚系统必须完成的工作，下面的工作就应该是决定“如何做”的问题，总体设计的基本目的的就是“概要地说系统应该如何实现？”。2.1.问题分析实际上就是对输入的数据,找出与这些数据的差绝对值的和最小的数.基本的思路就是找出中位数.2.2.解题思路如何确定主管道的最优位置？由于主管道是由东向西，显然，主管道的铺设位置只和各油井位置的y坐标有关，设各个油井的y坐标为：yi ，主管道的y坐标为：dy,各油井到主管道之间
6、的输油管道长度总和应是：sum ，要使这个值最小，主管道的位置y坐标应是各个油井y坐标的中位数（一组数据按从小到大的顺序依次排列，处在中间位置的一个数（或最中间两个数据的平均数）。证明(反证法)：油井数目为奇数：假设主管道的最优位置坐标值为y_val,不是各个油井位置坐标的中位数y_median，我们可以假设y_valy_median(不失一般性)，坐标小于y_val的油井数目为m,坐标大于y_val的油井数目为n，显然有mn。当我们将主管道位置下移距离x时(假设此时仍满足y_val=y_median)，各油井到主管道之间的输油管道长度总和应增加nx-mx，显然nx-mxn)，即存在一个比y_
7、val更优的位置使得各油井到主管道之间的输油管道长度总和更小，这与假设矛盾。油井数目为偶数：证明情况同奇数情况。不同的是主管道的最优位置y坐标可以是各油井坐标的两个中位数之间的任一整数。2.3.解题方法通过我们对数据结构和算法设计的学习，为了求得中位数，我们先通过划分算法对所有油井y坐标进行排序，然后通过随机选择方法RandomizedSelect得到中位数。2.3.1算法思想分治算法的基本思想是将一个规模个为N的问题分解为K规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。2.3.2算法分析分治算法是很多高效算法的基础，如排序算法（快速排序、归并排序
8、）、傅立叶变换（快速傅立叶变换）。快速排序是由东尼霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要(n lg n)次比较。在最坏状况下则需要(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他(n lg n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实作出来，且在大部分真实世界的资料，可以决定设计的选择，减少所需时间的二次方项之可能性。在此题中，我们考虑到时间复杂度，对于中位数这类选择问题的解决，不一定要先排序然后遍历（事实上这是比较慢的做法，排序的时间复杂度决定了它不可能比O（nlgn）快。通常选择问题只是要求知道第i大/小的
9、元素，所以我们可以将本实验的问题当成排序算法的简化。我们就以上述的快速排序为例，我们以划分的区间判断，选择问题我们只追究可能出现问题解的一个区间，而快速排序要处理两个区间。由此，我们可以清晰的明白利用随机划分解决此问题可以缩短时间复杂度。利用数据结构教材中的随机选择算法RandomizedSelect计算出中位数median(y)，然后计算n 口油井到主管道的最小长度总和，则所需时间主要是随机选择算法RandomizedSelect用的时间，在平均情况下需要O(n)计算时间。3.详细设计3.1具体描述详细设计阶段的根本任务是确定应该怎样具体实现所要求的输油管道定位问题，也就是经过这个阶段的设计
10、工作，应该得出对输油管道问题的精确描述，从而在输油管道定位的实现阶段可以把这个描述直接翻译成用某种程序设计语言书写的程序。把经过总体设计得到的各个模块详细的加以描述。根据油井的y坐标求出中位数 打开文件从文件读取油田数目将各个油井的坐标赋给指针a根据中位数求出最短距离 3-1.总体结构图返回划分后基数的位置N将各个油井的y坐标按从大到小的顺序排列float i=p,j=r+1float x=apA+ix&ixi=jSwap(ai=aj)YYNNYAj=xReturn jap=ajfloat*a,float p,r 3-2.patition算法设计图获取划分后随机基数的位置如果基数在中间数的左边
11、则重复进行以上操作如果基数在中间数的右边则重复进行以上操作如果基数在中间则返回基数的值获取基数距第一个数的长度NYFloat*a, floatp,r,kprReturn api=randomizepatition(a,p,r)Floatj=i-p+1K=jReturn ajKsize;int *a=new intsize;int readcount=1,i=0;while(readcounttemp;if(readcount%2=0)ai+=temp;readcount+;input.close();/获取数据中位数，即为通道Y坐标int length=RandomizedSelect(a,0
12、,size-1,(size+1)/2); printf(最佳位置y=%dn,length); printf(最短距离已保存在文件中！);/将总的管道长度写入out.txt文件中write(outFileName,lengthOfPipeline(a,size,length);system(pause);return 0;Patition（划分）函数的作用：将一串数据由大到小进行排序，最后返回划分时所用基数的位置float Partition(float *a,float p,float r)float i = p, j = r + 1;float x = ap;/将x的元素交换到左边区域while(true)while(a+ix&ix);if(i
