求中位数,快速选择算法

2017年07月11日 11点热度 0人点赞 0条评论

实验五    输油管道问题的设计与实现

[实验目的]

1、掌握分治算法的基本原理

2、利用分治策略编程解决输油管道问题

[实验内容]

问题描述

某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n 口油井的位置,即它们的x 坐标(东西向)和y 坐标(南北向),应如何确定主管道的最优位置, 即使各油井到主管道之间的输油管道长度总和最小的位置?

1.请给出分析与解答;

2.给出代码和运行结果;

3.估算算法的时间复杂度。

关于确定主管道的最优位置:由于主管道是由东向西,则主管道的铺设位置只和各油井位置的y坐标有关,要求的最优主管道的位置y坐标应是各个油井y坐标的中位数。

反证法证明之:

油井数目为奇数:假设主管道的最优位置y坐标值为y_ave,不是各个油井位置y坐标的中位数y_mid,我们可以假设y_ave>y_mid,y坐标小于y_ave的油井数目为m,y坐标大于y_ave的油井数目为n,显然有m>n。当我们将主管道位置下移距离x时(假设此时仍满足y_ave>=y_mid),各油井到主管道之间的输油管道长度总和应增加nx-mx,显然nx-mx<0(m>n),即存在一个比_ave更优的位置使得各油井到主管道之间的输油管道长度总和更小,这与假设矛盾。当y_ave>y_mid时,同理可证。

油井数目为偶数时:同理可证 。

分析:于是此题就转化为了求中位数,关于求中位数,可以先排序,然后中间那个就是所求,但是为了体现分治的思想,同时追求更高的效率,于是本次用随机选择算法,随机选择算法和快速排序有点像。

随机选择算法求中位数:如果是奇数个点,就是中间那个,如果是偶数个点,下面代码求的是中间靠左的那个数,当然油田放在中间靠右的那个也可以,各油井到主管道之间的输油管道长度总和是一样的,随机选择算法和快排差不多,先让第一个数找到对应的位置,比它小的放左边,比它大的放它右边,然后如果被排序的位置是中位数,则返回之,如果中位数的位置小于这个位置,就对左区域进行随机选择算法,反之则对右区域进行随机选择算法。

源代码:

#include

#include

using namespace std;

struct point

{

    int x,y;//存储油田坐标信息

} a[1000];

int exquick(point *a,int left,int right,int n)

{

    int ll=left,rr=right,y=a[left].y;

    while(ll

    {

        while(ll=y) rr--;

        a[ll]=a[rr];

        while(ll

        a[rr]=a[ll];

    }

    if(ll==(n-1)/2) return y;//如果是中位数,则返回之

    if(ll>(n-1)/2) return exquick(a,left,ll-1,n);//如果中位数在它的左边,则在左区域寻找

    return exquick(a,ll+1,right,n); //反之,在右区域寻找

}

int main()

{

    int n,t,ans;//n为油田个数

    cout<<"请输入油田个数:";

    cin>>n;

    for(int i=0; i

    {

        cout<<"请输入油田坐标:";

        cin>>a[i].x>>a[i].y;

    }

    cout<<"最优位置为:y="<

    return 0;

}

测试数据1:

5

1 2

2 2

1 3

3 -2

3 3

运行结果截图:

求中位数,快速选择算法

测试数据2:

6
1 6
2 -2
1 3
3 -2
3 3
1 1

运行结果截图:

求中位数,快速选择算法

时杂度分析:算法的时间复杂度为O(n).

未经允许不得转载!求中位数,快速选择算法

update

纸上得来终觉浅, 绝知此事须躬行。