基于分治法的输油管道问题
温杰
摘要 本实验，我们通过综合应用算法解决了实际生活中的输油管道问题，通过比较各种算法的时间复杂度以及解决效率，采用了算法中以分治法为基础的随机划分来解决问题，利用随机选择方法找到各个油井的中位数，通过讨论论证了中位数即最优管道位置。 信息奥赛中一个问题有多个算法解决，通过比较不同算法解决问题的效率，选择最高效的一个。在输油管道问题这个实验中得到运用。
关键词 算法设计，分治法，随机划分，随机选择，中位数
1 实验内容
某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x坐标（东西向）和y坐标（南北向）,应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道的最优位置。
给定n口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。 2 解题思想
设给定的n口油井的位置坐标为：
x[0],y[0]),(x[1],y[1]),(x[2],y[2]),…(x[n-1],y[n-1])。
由于平面上的距离满足三角不等式，故每个油井到主管道的最短距离就是该油井到主管道的垂直距离。由此可知，所述问题可表述为求平面上的一条直线到若干点的最短路径，通过总体设计中的解题思路我们论证得出只要该条直线处在所有点的中间位置就能保证最后
的距离最短。
根据题意，给定了n个油井的位置，因此首先读取每个油井的坐标，再在这个基础上对各个油井的y坐标进行排序，通过随机选择算法找到它们的中位数，即可得到求出最短距离。 油田位置 随机划分 求取中位数 求出最短距离 3 问题分析
如何确定主管道的最优位置？
由于主管道是由东向西，显然，主管道的铺设位置只和各油井位置的y坐标有关，设各个油井的y坐标为：y[i] ，主管道的y坐标为：dy,各油井到主管道之间的输油管道长度总和应是：sum ，要使这个值最小，主管道的位置y坐标应是各个油井y坐标的中位数（一组数据按从小到大的顺序依次排列，处在中间位置的一个数（或最中间两个数据的平均数）。 证明(反证法)：
①油井数目为奇数：假设主管道的最优位置ｙ坐标值为y_val,不是各个油井位置ｙ坐标的中位数y_median，我们可以假设y_val>y_median(不失一般性)，ｙ坐标小于y_val的油井数目为m,ｙ坐标大于y_val的油井数目为n，显然有m>n。当我们将主管道位置下移距离x时(假设此时仍满足y_val>=y_median)，各油井到主管道之间的输油管道长度总和应增加nx-mx，显然nx-mx<0(m>n)，即存在一个比y_val更优的位置使得各油井到主管道之间的输油管道长度
总和更小，这与假设矛盾。
②油井数目为偶数：证明情况同奇数情况。不同的是主管道的最优位置y坐标可以是各油井ｙ坐标的两个中位数之间的任一整数。 4 算法思想
分治算法的基本思想是将一个规模个为N的问题分解为K规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。
分治算法是很多高效算法的基础，如排序算法（快速排序、归并排序）、傅立叶变换（快速傅立叶变换）。
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n lg n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n lg n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实作出来，且在大部分真实世界的资料，可以决定设计的选择，减少所需时间的二次方项之可能性。
在此题中，我们考虑到时间复杂度，对于中位数这类选择问题的解决，不一定要先排序然后遍历（事实上这是比较慢的做法，排序的时间复杂度决定了它不可能比O（nlgn）快。通常选择问题只是要求知道第i大/小的元素，所以我们可以将本实验的问题当成排序算法的简化。我们就以上述的快速排序为例，我们以划分的区间判断，选择问题我们只追究可能出现问题解的一个区间，而快速排序要处理两个区间。由此，我们可以清晰的明白利用随机划分解决此问题可以缩
短时间复杂度。
利用随机选择算法RandomizedSelect计算出中位数median(y)，然
后计算n 口油井到主管道的最小长度总和，则所需时间主要是随机选择算法RandomizedSelect用的时间，在平均情况下需要O(n)计算时间。 总体结构图如下：
根据输油管道修建的方向，将油井的横坐标或者纵坐标传给数组 输入油井的坐标、数目和选择输油管道的方向
根据数组中的数据求出中位数 将数组指针作为函数的参数传递
PARTITION算法设计图：
根据中位数求出最短距离 int x = arr[r]，int I = p-1 int arr[]，int p，int r int j = p j < r Y Arr[j] <= x Y ++i; int t = arr[i]; arr[i] = arr[j]; arr[j] = t; j++ int t = arr[i+1]; arr[i+1] = arr[r]; arr[r] = t; Return i+1
RANDOMIZED_SELECT算法设计图：
N