《算法设计与分析——输油管道问题试验报告.docx》由会员分享，可在线阅读，更多相关《算法设计与分析——输油管道问题试验报告.docx（19页珍藏版）》请在三一文库上搜索。
1、题目:输油管道问题学号00913130张一楠学生姓名亠-专业（班级）09计本1班00913133朱玉婷设计题目输油管道问题设计技术参数系统平台：wi ndows 7开发工具：Microsoft Visual C+ 6.0设 计 要 求1. 掌握冋题分析的方法与步骤，选择合适的方法解决冋题。2. 选择合适的算法编写程序。工 作 计 划1:熟悉题目并理解，及找寻相关资料。 2:根据题目设计并分析算法。3:使用 Visual C+实现。4：完成设计报告参 考 资 料吕国英算法设计与分析北京：清华大学出版社,200911摘要本实验，我们通过综合应用算法解决了实际生活中的输油管道问 题，通过比较各种算法
2、的时间复杂度以及解决效率， 采用了算法中以 分治法为基础的随机划分来解决问题， 利用随机选择方法找到各个油 井的中位数，通过讨论论证了中位数即最优管道位置。信息奥赛中一个问题有多个算法解决， 通过比较不同算法解决问题 的效率，选择最高效的一个。在输油管道问题这个实验中得到运用。关键词： 算法设计，分治法，随机划分，随机选择，中位数目录1 需求分析错. 误 !未定义书签1.1 实验内容错. 误 !未定义书签1.2 系统的基本逻辑模型错误 ! 未定义书签。1.3确定目标系统的功能 .52 总体设计错. 误 !未定义书签2.1 问题分析错. 误 !未定义书签2.2解题思路 6.2.3解题方法 .72
3、31算法思想72.3.2算法分析73 详细设计 9.3.1 具体描述 9.3.2 程序分析 1 13.2.1程序代码.113.2.2程序结果.144 总结1.6.4.1 设计体会 1.6.4.2反思总结 16参考文献 .错误!未定义书签。1需求分析1.1. 实验内容某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路 经(或南或北)与主管道相连。如果给定n 口油井的位置，即它们的x 坐标(东西向)和y坐标(南北向)，应如何确定主管道的最优位置， 即使各油井到主管道之间的输油管道长度总和最小的位置？证明可在线性时间内确定主管道的最优位
4、置。给定n 口油井的位置，编程计算各油井到主管道之间的输油管道最小长度总和。1.2. 系统的基本逻辑模型设给定的 n 口油井的位置坐标为：(x0,y0),(x1,y1),(x2,y2),(xn-1,yn-1)。由于平面上的距离 满足三角不等式，故每个油井到主管道的最短距离就是该油井到主管 道的垂直距离。由此可知，所述问题可表述为求平面上的一条直线到 若干点的最短路径，通过总体设计中的解题思路我们论证得出只要该 条直线处在所有点的中间位置就能保证最后的距离最短。根据题意，给定了 n个油井的位置，因此首先从文件读取每个油 井的坐标，再在这个基础上对各个油井的y坐标进行排序，通过随机 选择算法找到它
5、们的中位数，即可得到求出最短距离。油田位置1.3. 确定目标系统的功能通过本实验的设计， 我们可以找到一个到各个油井之间的长度总 和最小的输油管道，确定出输油管道的位置，并且计算出长度之和。 在实际生活中，本实验的程序设计，可以节省工程的耗资，并且也可 以省去人工计算的繁琐。2. 总体设计系统设计一般分为总体设计和详细设计。经过需求分析阶段的 工作，已经清楚系统必须完成的工作，下面的工作就应该是决定“如 何做”的问题， 总体设计的基本目的的就是“概要地说系统应该如何 实现？”。2.1. 问题分析实际上就是对输入的数据 ,找出与这些数据的差绝对值的和最小 的数.基本的思路就是找出中位数 .2.2
6、. 解题思路如何确定主管道的最优位置？由于主管道是由东向西， 显然，主管道的铺设位置只和各油井位 置的y坐标有关，设各个油井的y坐标为：yi,主管道的y坐标为： dy,各油井到主管道之间的输油管道长度总和应是：sum，要使这个值最小，主管道的位置 y 坐标应是各个油井 y 坐标的中位数（一组数 据按从小到大的顺序依次排列， 处在中间位置的一个数 （或最中间两 个数据的平均数）。证明（反证法） ： 油井数目为奇数：假设主管道的最优位置y坐标值为y_val，不是各个油井位置y坐标的中位数y_median ,我们可以假设 y_val>y_median（不失一般性）,y坐标小于y_val的油井数
7、目为 m, y 坐标大于y_val的油井数目为n,显然有m>n。当我们将主管道位置 下移距离x时（假设此时仍满足y_val>=y_median）,各油井到主管道 之间的输油管道长度总和应增加 nx-mx，显然nx-mx<O（m>n），即存 在一个比 y_val 更优的位置使得各油井到主管道之间的输油管道长度 总和更小,这与假设矛盾。 油井数目为偶数： 证明情况同奇数情况。 不同的是主管道的最优位 置y坐标可以是各油井y坐标的两个中位数之间的任一整数。23解题方法通过我们对数据结构和算法设计的学习，为了求得中位数，我们先通过划分算法对所有油井y坐标进行排序，然后通过随机选
8、择方法 Ran domizedSelec得到中位数。2.3.1算法思想分治算法的基本思想是将一个规模个为 N的问题分解为K规模 较小的子问题，这些子问题相互独立且与原问题性质相同。 求出子问 题的解，就可得到原问题的解。2.3.2算法分析分治算法是很多高效算法的基础，如排序算法(快速排序、归并 排序)、傅立叶变换(快速傅立叶变换)。快速排序是由东尼霍尔所发展的一种排序算法。在平均状况下， 排序n个项目要O(n lg n)次比较。在最坏状况下则需要O (n2)次 比较，但这种状况并不常见。事实上，快速排序通常明显比其他O(nlg n)算法更快，因为它的内部循环(inner loop )可以在大部
9、分的 架构上很有效率地被实作出来，且在大部分真实世界的资料，可以决 定设计的选择，减少所需时间的二次方项之可能性。在此题中，我们考虑到时间复杂度，对于中位数这类选择问题的 解决，不一定要先排序然后遍历(事实上这是比较慢的做法，排序的 时间复杂度决定了它不可能比 0(nlgn )快。通常选择问题只是要求 知道第i大/小的元素，所以我们可以将本实验的问题当成排序算法 的简化。我们就以上述的快速排序为例，我们以划分的区间判断，选择问题我们只追究可能出现问题解的一个区间，而快速排序要处理两个区间。由此，我们可以清晰的明白利用随机划分解决此问题可以缩 短时间复杂度。利用数据结构教材中的随机选择算法 Ra
10、 ndomizedSelect计算 出中位数median(y)，然后计算n 口油井到主管道的最小长度总和， 则所需时间主要是随机选择算法 RandomizedSelect用的时间，在平均 情况下需要0( n)计算时间。3. 详细设计3.1具体描述详细设计阶段的根本任务是确定应该怎样具体实现所要求的输油管道定位问题，也就是经过这个阶段的设计工作， 应该得出对输油 管道问题的精确描述，从而在输油管道定位的实现阶段可以把这个描 述直接翻译成用某种程序设计语言书写的程序。 把经过总体设计得到 的各个模块详细的加以描述。3-1.总体结构图float*a,float p,r3-2.patition算法设计
11、图如果基数在中间数的左边则重复进行以上操作3-3. RandomizedSelec算法设计图ii3.2 程序分析3.2.1程序代码主函数的作用： 首先初始化油井的坐标数组， 由用户从键盘输入各 个油井的总数，然后再输入各个油井的坐标，并且会显示出来。 int main()int size=0;char *inFileName="D:in.txt"char *outFileName="D:out.txt"ifstream input(inFileName,ios:in);/ 从文件读取数据input>>size;int *a=new intsi
12、ze;int readcount=1,i=0;while(readcount<=(size*2)int temp=0;input>>temp;if(readcount%2=0)ai+=temp;readcount+;input.close();/获取数据中位数，即为通道 丫坐标int length=RandomizedSelect(a,0,size-1,(size+1)/2);printf(" 最佳位置 y=%dn",length);printf(" 最短距离已保存在文件中！ ");/ 将总的管道长度写入 out.txt 文件中 wri
13、te(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;/将vx的元素交换到右边区域/将X的元素交换到左边区域while(true)while(a+ivx&&ivr); while(a-j>x); if(i>=
14、j)break;swap(ai,aj);ap=aj;aj=x;return j; / 获取划分后基数的位置 RandomizedPartition （随机划分优化算法）函数的作用：在所有坐 标中随机选择一个， 并以此作为基数进行划分， 最后返回该基数的位float RandomizedPartition(float *a,float p,float r)float i= Random(p,r); / 产生随机数 swap(ai,ap); / 交换基数和第一个数 return Partition(a,p,r); / 返回划分后基数的位置 RandomizedSelect (随机选择)函数的作用：
15、找到排序后数据的中位 数float RandomizedSelect(float *a,float p,float r,float k)if(p>=r)return ap;float i = RandomizedPartition(a,p,r); / 将随机基数的为位置赋给 ifloat j = i-p+1;/ 获取基数距第一个数的长度if (k = j) return ai;/如果基数在中间则返回基数的值if(k<j)return RandomizedSelect(a,p,i-1,k);/如果基数在中间数的右边则重复进行以上操作Elsereturn RandomizedSelec
16、t(a,i+1,r,k-j);/如果基数在中间数的左边则重复进行以上操作/此函数就是当基数处在油井的中间时返回该值3.2.2程序结果194. 总结4.1 设计体会通过该课程设计， 全面系统的理解了算法设计与分析的一般原理 和基本实现方法。 把死板的课本知识变得生动有趣， 激发了学习的积 极性。把学过的算法知识强化， 能够把课堂上学的知识通过自己设计 的程序表示出来， 加深了对理论知识的理解。 以前对与算法的认识是 模糊的，现在通过自己动手做实验，从实践上应用了算法，了解了算 法在一个程序中是如何起作用的，并且学会比较各种算法的优劣。通过对本实验的分析， 对于输油管道实质上就是求解中位数的问 题
17、，经过讨论和总结我们得到三种解法： (1)用教材中的快速排序算 法 quicksort 将 n 口油井的 y 坐标排序后，容易计算出中位数 median(y), 由此容易求得 n 口油井到主管道的最小长度之和； (2)用 教材中最坏情况下的线性时间选择算法 select 计算出中位数 median(y), 然后计算 n 口油井到主管道的最小长度之和； ( 3)用教材 中的随机选择算法 randomizedselect 计算出中位数 median(y), 然后 计算 n 口油井到主管道的最小长度之和。 下面我们比较一下它们算法 计算复杂性。1. 时间需求(1)如果用教材中的快速排序算法 Quic
18、kSort 将 n 口油井的 y 坐标排序后，再计算出中位数 median(y) ，则所需时间主要是排序 算法用的时间，在平均情况下需要 O(nlog(n) 计算时间。( 2)如果用教材中的最坏情况下的线性时间选择算法 Select 计 算出中位数 median(y), 然后计算 n 口油井到主管道的最小长度总和， 则所需时间主要是选择算法 Select 用的时间，在最坏情况下需要 O (n*n )计算时间。(3) 如果用教材中的随机选择算法 RandomizedSelect 计算出中位数 median(y), 然后计算 n 口油井到主管道的最小长度总和， 则所需时间 主要是随机选择算法 RandomizedSelect 用的时间，在平均情况下需 要 O(n) 计算时间。2. 空间需求算法所需的空间明显是 O(n) 。通过比较这三种算法的优劣，我们找到了本题的最优算法 randomizedselect.4.2. 反思总结 本实验设计原本采用从键盘输入各个油井的坐标， 倘若油井数量 比较庞大就会十分繁琐， 如果可以将油井坐标事前储存在文件中， 从 文件中读取这便可以提高效率， 经过回顾学习， 我们将程序的读取修 改成从文件读取，将结果也保存在文件中。参考文献1 吕国英. 算法设计与分析 .北京:清华大学出版社 ,2009