《算法输油管道问题代码及分析》由会员分享，可在线阅读，更多相关《算法输油管道问题代码及分析（8页珍藏版）》请在金锄头文库上搜索。
1、基于分治法的输油管道问题温杰摘要 本实验，我们通过综合应用算法解决了实际生活中的输油管道问题，通过比较 各种算法的时间复杂度以及解决效率，采用了算法中以分治法为基础的随机划分来解决问题 利用随机选择方法找到各个油井的中位数，通过讨论论证了中位数即最优管道位置。信息奥赛中一个问题有多个算法解决，通过比较不同算法解决问题的效率，选择最高效的 一个。在输油管道问题这个实验中得到运用。关键词 算法设计，分治法，随机划分，随机选择，中位数1 实验内容某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定 n
2、 口油井的位置,即它们的x坐标(东西向)和y坐标(南北向)，应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的 位置?证明可在线性时间内确定主管道的最优位置。给定 n 口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。2 解题思想设给定的 n 口油井的位置坐标为：x0,y0),(xl,yl),(x2,y2),(xn-l,yn-l)。由于平面上的距离满足三角不等式，故每个油井到主管道的最短 距离就是该油井到主管道的垂直距离。由此可知，所述问题可表述为 求平面上的一条直线到若干点的最短路径，通过总体设计中的解题思 路我们论证得出只要该条直线处在所有点的中间位置
3、就能保证最后 的距离最短。根据题意，给定了 n个油井的位置，因此首先读取每个油井的坐 标，再在这个基础上对各个油井的 y 坐标进行排序，通过随机选择算 法找到它们的中位数，即可得到求出最短距离。3 问题分析如何确定主管道的最优位置？由于主管道是由东向西，显然，主管道的铺设位置只和各油井位 置的y坐标有关，设各个油井的y坐标为:yi，主管道的y坐标为： dy,各油井到主管道之间的输油管道长度总和应是：sum，要使这个 值最小，主管道的位置y坐标应是各个油井y坐标的中位数（一组数 据按从小到大的顺序依次排列，处在中间位置的一个数（或最中间两 个数据的平均数）。证明（反证法）：油井数目为奇数：假设主
4、管道的最优位置y坐标值为y_val，不是各 个油井位置y坐标的中位数y_median，我们可以假设 y_valy_median（不失一般性），y坐标小于y_val的油井数目为m, y 坐标大于y_val的油井数目为n，显然有mn。当我们将主管道位置 下移距离x时（假设此时仍满足y_val=y_median），各油井到主管道 之间的输油管道长度总和应增加nx-mx，显然nx-mxn），即存 在一个比y_val更优的位置使得各油井到主管道之间的输油管道长度 总和更小，这与假设矛盾。油井数目为偶数：证明情况同奇数情况。不同的是主管道的最优位 置y坐标可以是各油井y坐标的两个中位数之间的任一整数。4
5、算法思想分治算法的基本思想是将一个规模个为N的问题分解为K规模 较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问 题的解，就可得到原问题的解。分治算法是很多高效算法的基础，如(、)、()。快速排序是由所发展的一种。在平均状况下，排序n个项目要 (n lg n)次比较。在最坏状况下则需要0 (n)次比较，但这种状况并 不常见。事实上，快速排序通常明显比其他0 (n lg n)算法更快， 因为它的内部循环(inner loop)可以在大部分的架构上很有效率地 被实作出来，且在大部分真实世界的资料，可以决定设计的选择，减 少所需时间的二次方项之可能性。在此题中，我们考虑到时间复杂度，对于
6、中位数这类选择问题的 解决，不一定要先排序然后遍历(事实上这是比较慢的做法，排序的 时间复杂度决定了它不可能比0 (nlgn)快。通常选择问题只是要求 知道第i大/小的元素，所以我们可以将本实验的问题当成排序算法 的简化。我们就以上述的快速排序为例，我们以划分的区间判断，选 择问题我们只追究可能出现问题解的一个区间，而快速排序要处理两 个区间。由此，我们可以清晰的明白利用随机划分解决此问题可以缩 短时间复杂度。利用随机选择算法RandomizedSelect计算出中位数median(y),然 后计算n 口油井到主管道的最小长度总和，则所需时间主要是随机选 择算法RandomizedSelec
7、t用的时间，在平均情况下需要0 (n)计算时间。总体结构图如下：PARTITIO N算法设计图:int arr, int p, int rint x = arrr, int I = p-1int j = p3 rRANDOMIZED_SELECT 算法设计图:Int arr，int p，int r，int i如果基数在中间数的右边则重复进行以上操作程序代码如下：int main()t C:U sersAdmini strato r Desktopeat exeCreated Ey wenjie mcxn/1Enter ynn choiceplease enter the oj.l tubing
8、 aLignnent1 NoFth and Sauth2 East and West2Ju lease enter the numbep of o 11 bearing5please enter the positj.on of oil bearingdesa than 5)o il bearing9J s X_ualue -4o il beaFing9J s V_ualue -4o il bearinglJ s X_ualue =5o?.l bearinglJ s _ualue =5o j.l beaping2J s X_ualue =2o11 bearing2J s ?_ualue =2o
9、 il bearing3J s X_ualue =7oil beaFing3J s _ualue =7oj.l beaping4J s X_ualue =7o il bearing4J s V_ualue =7?Iie o i.l tubing1 s posit ion is ! =5.00043S0The total is 8Process returned 理 execution time ； 12.144 s ?reas an9 tc continue.间需求(1) 如果使用快速排序算法Quicksort将n 口油井的y坐标排 序后，再计算出中位数median(y),则所需时间主要是排序
10、算法用 的时间，在平均情况下需要0(nlog(n)计算时间。(2) 如果用最坏情况下的线性时间选择算法 Select 计算出中 位数median(y),然后计算n 口油井到主管道的最小长度总和，则所 需时间主要是选择算法Select用的时间，在最坏情况下需要0 (n*n) 计算时间。(3) 如果用随机选择算法 RandomizedSelect 计算出中位数 median(y),然后计算n 口油井到主管道的最小长度总和，则所需时间 主要是随机选择算法 RandomizedSelect 用的时间，在平均情况下需 要0(n)计算时间。2.空间需求算法所需的空间明显是0 (n)。所以根据比较，此算法是求解此类问题的合理算法。
