输油管道问题解答.docVIP

输油管道问题解答 输油管道问题解答（福州大学算法与数据结构课程组提供） 1 问题描述 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有 n口油井的油 田。从每口油井都要有一条输油管道沿最短路经 (或南或北 )与主管道相连。如果给定 n口油 井的位置，即它们的 x坐标（东西向）和 y坐标（南北向），应如何确定主管道的最优位置， 即使各油井到主管道之间的输油管道长度总和最小的位置？证明可在线性时间内确定主管 道的最优位置。 2 实验任务： 给定 n口油井的位置, 设计一个线性时间算法，计算各油井到主管道之间的输油管道最 小长度总和。 3 解题思路 设给定的 n口油井的位置坐标为： (x0, y0 ),(x1, y1),.,(xn-1, yn-1) 。 由于平面上的距离满足三角不等式，故每个油井到主输油管道的最短距离是该油井到主 输油管道的垂直距离。由此可知，所述问题可表述为求平面上的一条直线 y =c 使得， .(n) (1) (-) | yi . c | = min íì.(n) (1) (-) | yi . y |y . y.E i=0 .i =0 . 设 y0, y1,., yn-1 的中位数为 median( y)。通过进一步观察可知， median( y)是 min .(n) (1) (-) | yi . y | 的最优解。这个结论将在算法正确性分析中严格证明。 y.E i =0 4 算法实现 通过上面的分析易知，输油管道问题实质上就是求中位数的问题。 （1）用教材中的快速排序算法 QuickSort将 n口油井的 y坐标排序后，容易计算出中 位数 median( y)，由此容易求得 n口油井到主管道的最小长度总和。具体算法可描述如下： void pipeline() { QuickSort(y,n); //y 坐标排序 int dy=y[n/2]; // 中位数 } for(int i=0;in;i++) dist+=abs(y[i]-dy); // 计算长度总和 1  （2）用教材中的最坏情况下的线性时间选择算法 Select计算出中位数 median( y)， 然后计算 n口油井到主管道的最小长度总和。具体算法描述如下： void pipeline() { int dy=Select(y,0,n-1,(n+1)/2); // y 坐标中位数 } for(int i=0;in;i++) dist+=abs(y[i]-dy); // 计算长度总和 （3）用教材中的随机选择算法 RandomizedSelect计算出中位数 median(x)和 median( y)，然后计算 n口油井到主管道的最小长度总和。具体算法描述如下： void pipeline() { int dy=RandomizedSelect(y,0,n-1,(n+1)/2); // y 坐标中位数 } for(int i=0;in;i++) dist+=abs(y[i]-dy); // 计算长度总和 5 算法正确性 算法的正确性由下面的定理保证。定理 1： median(x)是 min .(n) (1) (-) | xi . x | 的最优解。 x.E i=0 证明： 在下面的讨论中，不失一般性可设 x0 ≤ x1 ≤ .≤ xn-1 。 分别讨论 n为奇数和 n为偶数的情况。 （1）当 n为奇数时，设 n= 2k +1， median (x) ={xk }， sum=| xi . xk | 。.(n) (1) (-) i=0 对于任意 x .E ， .(n) (1) (-) | xi . x | =.(n) (1) (-) | xi . xk + xk . x | i=0 i=0 =.(-) (k) (1) | xi . xk + xk . x | +.(-) (n) (1) | xi . xk + xk . x |+ | xk . x | i=0 i=k +1 =.(-) (k) (1) | xi . xk | +.(-) (k) (1) (x -xk ) +.(-) (n) (1) | xi . xk | -.(k) (2) (x . xk )+ | xk . x | i=0 i=0 i=k +1 i=k +1  =.-(n) (1) | x . x |+ | x . x | ik k i=0 = sum + |x . xk |≥ sum 由此可见， xk为最优解， sum为最优值。 （2）当 n为偶数时，设 n =