分治算法:循环赛日程/最近点对

实验一 递归与分治

【实验学时】
5学时
【实验目的】
(1)深刻理解并掌握“分治算法”的设计思想;
(2)提高应用“分治算法”设计技能;
(3)理解这样一个观点:用递归方法编写的问题解决程序具有结构清晰,可读性强等优点,且递归算法的设计比非递归算法的设计往往要容易一些,所以当问题本身是递归定义的,或者问题所涉及到的数据结构是递归定义的,或者是问题的解决方法是递归形式的时候,往往采用递归算法来解决。
【实验内容】
(1)利用分治算法,编程实现循环赛日程表安排问题,并进行时间复杂性分析;
(2)利用分治算法、蛮力法,编程实现最近点对问题,并进行时间复杂性分析。

利用分治算法,编程实现循环赛日程表安排问题,并进行时间复杂性分析

分治算法的基本思想

将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。即一种分目标完成程序算法,简单问题可用二分法完成。

分治法的求解过程

一般来说,分治法的求解过程由以下三个阶段组成:
1.划分:既然是分治,当然需要把规模为n的原问题划分为k个规模较小的子问题,并尽量使这k个子问题的规模大致相同。
2.求解子问题:各子问题的解法与原问题的解法通常是相同的,可以用递归的方法求解各个子问题,有时递归处理也可以用循环来实现。
3.合并:把各个子问题的解合并起来,合并的代价因情况不同有很大差异,分治算法的有效性很大程度上依赖于合并的实现。

循环赛日程表安排问题

设有n = 2的k次方个运动员要进行网球循环赛,现要设计一个满足以下要求的比赛日程表:
1.每个选手必须与其他n-1个选手各赛一次;
2.每个选手一天只能参赛一次;
3.循环赛在n-1天内结束;
要求设计成n行和n列的表,第i行,j列代表第i个选手在第j天遇到的对手,   其中1<=i<=n,1<=j<=n-1;

按此要求,可将比赛日程表设计成一个 n 行n-1列的二维表,其中,第 i 行第 j 列表示和第 i 个选手在第 j 天比赛的选手。

过程

按分治策略,将所有的选手分为两半,n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割,直到只剩下2个选手时,比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。
或者可以从k=1开始推理
只有两个选手(k=1)

1|2
2|1

四个选手 (k=2)

1|2|3|4
2|1|4|3
3|4|1|2
4|3|2|1

八个选手
A2

则是一个自底向上迭代的过程,可以将 2^k结果表从中分为四部分
– 左上角:2^{k-1} 结果表
– 左下角:左下角为另2k-1个选手在前半程的比赛日程,由左上角加2k-1得到
– 右上角:左下角的复制
– 右下角:左上角的赋值

左下角的推理比较难想

代码实现

#include <iostream>
#include<math.h>
using namespace std;
#include<vector>
int main()
{
    int k;
    cin >> k;
    if (k <= 32) 
    {
        int n = pow(2,k);
        cout << n << endl;
        vector<vector<int>> vec(n,vector<int>(n));//建立二维数组v
        vec[0][0] = 1;
        vec[0][1] = 2;
        vec[1][0] = 2; 
        vec[1][1] = 1;


        if (k > 1||k<32)
        {
            for (int i = 2; i <= k; i++)
            {
                int half = pow(2, i - 1);
                //左下角的子表中项为左上角子表对应项加half=2^(i-1)
                for (int row = 0; row < half; row++)
                {
                    for (int col = 0; col < half; col++)
                    {
                        vec[row + half][col] = vec[row][col] + half;
                    }
                }
                //右上角的子表等于左下角子表
                for (int row = 0; row < half; row++)
                {
                    for (int col = 0; col < half; col++)
                    {
                        vec[row][col + half] = vec[row + half][col];
                    }
                }
                //右下角的子表等于左上角子表
                for (int row = 0; row < half; row++)
                {
                    for (int col = 0; col < half; col++)
                    {
                        vec[row + half][col + half] = vec[row][col];
                    }
                }
            }

            for (auto &row : vec)
            {
                for (auto elem : row)
                    cout << elem << " ";
                cout << endl;
            }
        }
    }

}

O(n): 2^k*2^k

利用分治算法、蛮力法,编程实现最近点对问题,并进行时间复杂性分析。

最近点对问题Closest pair of points problem

​ n个点在公共空间中,求出所有点对的欧几里得距离最小的点对。n个点在公共空间中,求出所有点对的欧几里得距离最小的点对。

分析

一:暴力法,计算所有点对的距离并比较

对两个点p_i(x_i,y_i),p_j(x_jy_j)的欧几里得距离比较

  • 为了避免重复运算,只计算i<j的点对(p_i,p_j)
  • 在求距离时先无需开方,最后得出结果再进行开方计算距离

二:分治法

  • 划分

    将点集S分为S1和S2,设S的最近点对是p_iq_i

    则有如下情况

    • p_i \in S1,q_i\in S1
    • p_i \in S2,q_i\in S2
    • p_i \in S1,q_i\in S2
  • 求解子问题
    • 最近点对在一个集合:递归求解

    • 不在一个集合:选x=m作为分割线(m是x_i的中值),分为S1和S2,对S1和S2分别求最近点对问题,得S1中最近距离d_1和S2中最近距离d_2,令d=min{d_1d_2},若,S的最近点对直接距离小于d,则最近点对在:

    x=m为中心,宽2d的矩形中,且由鸽笼原理知:从区域内必然不多于八个点,将区域内的点的y坐标按序排列,按序处理这些点的距离,并与d比较

  • 合并

输入:n个点的集合S

输出:最近点对的距离

1.如果n=2,直接输出两点的距离

2.mid=x坐标的中位数,分S1,S2

3.S1,S2递归求解出d1 d2 d=min(d1,d2)

4.考察集合中的点,if(x<=x_{mid}&&x>x_{mid}-d),x入集合P1

​ if(x>x_{mid}&&x<=x_{mid}+d),x入集合P2

5.P1,P2按y坐标升序排列

6.对P1和P2中每个点x,在y坐标区间[y,y+d]中最多找8个点,算出d3与d比较,取二者最小并返回

暴力法实现

//暴力法 最近点对
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int main()
{
    vector<double> x;//x存储横坐标
    vector<double> y;//y存储纵坐标
    int n;//点的个数
    double mindis=10^300;//最近点对的距离
    int minx,miny;//最近点对
    cin>>n; //输入点的个数n
    for (int i=0;i<n;++i)  //输入各个点的坐标
    {
        int a,b;
        cin>>a;
        cin>>b;
        x.push_back(a);
        y.push_back(b);
    }
    for (int i=0;i<n;++i) //遍历i<j的点并求其距离d
    {
        for(int j=i+1;j<n;++j)
        {
            double d=((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
            if(mindis>d)
            {
                mindis=d;
                minx=i;
                miny=j;
            }
        }
    }
    cout<<x[minx]<<','<<x[miny]<<';'<<y[minx]<<','<<y[miny]<<endl<<sqrt(mindis);
}

分治法实现

代码参考自https://blog.csdn.net/sinat_35678407/article/details/82874216

用vector的存储,构造函数使得可以pop入vector,对left和right的二次使用,对P1P2的处理(课本上为直接遍历,未体现鸽笼思想)

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
struct point   //结构体point,存储一个点的x,y坐标
{
    double x, y;
    point() {};
    point(double x, double y) :x(x), y(y) {}//构造函数
};

bool cmpx(point a, point b)  //比较x的坐标,返回其x大小的升序排列
{
    return a.x < b.x;
}
bool cmpy(point a, point b)  //比较y的坐标,返回其y大小的升序排列
{
    return a.y < b.y;
}

double distance(point  A, point  B) //dis函数
{
    return (pow(A.x - B.x, 2) + pow(A.y - B.y, 2));
}
double closeset(vector<point> & points)
{
    if (points.size() == 2) return  distance(points[0], points[1]); //当只有两个点,直接返回
    int mid = (points.size()) / 2 - 1; //此时x有序,直接取mid中位
    double d1, d2, d; //对应S1,S2,
    vector<point> left(mid + 1);//S1 大小mid+1
    vector<point> right(points.size() - mid - 1);//S2
    copy(points.begin(), points.begin() + mid + 1, left.begin());  //从S赋值给S1
    copy(points.begin() + mid + 1, points.end(), right.begin());   //从S赋值给s2
    d1 = closeset(left);
    d2 = closeset(right);
    d = min(d1, d2);

    left.clear(); //清除,作P1
    right.clear();//清除,作P2
    for (int i = 0; i < points.size(); ++i)  //于S中找点x放p
    {
        if (points[i].x - points[mid].x <= 0 && points[i].x - points[mid].x > d)
            left.push_back(points[i]);
        else if (points[i].x - points[mid].x > 0 && points[i].x - points[mid].x < d)
            right.push_back(points[i]);
    }
    sort(right.begin(), right.end(), cmpy);
    for (int i = 0, index; i < left.size(); ++i)  // 遍历左边的点集合,与右边符合条件的点计算距离
    {
        for (index = 0; index < right.size() && left[i].y < right[index].y; ++index); //计算index
        for (int j = 0; j < 7 && index + j < right.size(); ++j)  // 遍历右边坐标上界的8个点
        {
            if (distance(left[i], right[j + index]) < d)
                d = distance(left[i], right[j + index]);
        }
    }
    return d;
}

int main()
{

    int n;//点的个数
    vector<point> points;  //S
    //double mindis;
    cin >> n; //输入点的个数n
    for (int i = 0; i < n; ++i) //写入S
    {
        double x, y;
        cin >> x >> y;
        point p(x, y);
        points.push_back(p);
    }
    sort(points.begin(), points.end(), cmpx);//调用sort函数,用以x的排序

    cout << sqrt(closeset(points));
    return 0;
}

算法复杂度为O(nlog_nn)

发表评论