[数据结构与算法]平面最佳坐标点

题目描述

竞赛题
C 平面最佳坐标点
Time Limit:3000MS Memory Limit:65535K
题型: 编程题 语言: 无限制
描述 在平面坐标上，给n个坐标点，现定义两个点（x1,y1）和（x2,y2）的“距离”为|x1-x2|3+|x1-x2|*|y1-y2|+|y1-y2|3 现要求编程找一个点，使得n个点到该点的距离累加和最小，精度去到小数点3位
输入格式
第一行一个数n(n<=1000)，
此后n行，每行两个浮点数为坐标点x y(0<=x,y<=1000)
输出格式
输出最佳位置坐标
输入样例
3
0 0
100 0
100 100
输出样例
58.648 41.352
Provider admin

解题思路及其过程

1.暴力法,直接暴力搜索答案(超时)

#include <iostream>
#include <cstdio>
#include <utility>
#include <vector>
#include <math.h>

using namespace std;

double cal(double x1,double y1,double x2,double y2){
    return fabs(x1-x2)*fabs(x1-x2)*fabs(x1-x2)+fabs(x1-x2)*fabs(y1-y2)+fabs(y1-y2)*fabs(y1-y2)*fabs(y1-y2);
}
const int M=1000+5;
pair<double,double> a[M];
int main(){
    int n;scanf("%d",&n);
    int N=n;
    int idx=0;
    while(N--){
        double x,y;scanf("%lf%lf",&x,&y);
        a[idx].first=x;
        a[idx++].second=y;
    }

    /*一.直接暴力搜索答案,从整数到小数(超时)*/
    //1.先精确到整数
    double minInt=0x3f3f3f3f;
    pair<int,int> index;
    for(int x=0;x<=1000;x++){
        for(int y=0;y<=1000;y++){
            //搜索每一个点
            double sumnow=0;
            for(int i=0;i<idx;i++){
                double x1=a[i].first,y1=a[i].second;
                sumnow+=cal(x,y,x1,y1);
            }
            if(sumnow<minInt){
                minInt=sumnow;
                index.first=x;
                index.second=y;
            }
        }
    }

    //2.在这个整数的-1和这个整数的+1范围内以0.001为步长搜索
    //(index.first-1) (index.second-1)
    pair<double,double> ans;
    for(double x=index.first-1;x<index.first;x+=0.001){
        for(double y=index.second-1;y<index.second;y+=0.001){
            double sumnow=0;
            for(int i=0;i<idx;i++){
                double x1=a[i].first,y1=a[i].second;
                sumnow+=cal(x,y,x1,y1);
            }
            if(sumnow<minInt){
                minInt=sumnow;
                ans.first=x;
                ans.second=y;
            }
        }
    }

    //(index.first-1) (index.second+1)
    for(double x=index.first-1;x<index.first;x+=0.001){
    for(double y=index.second+1;y>index.second;y-=0.001){
        double sumnow=0;
        for(int i=0;i<idx;i++){
            double x1=a[i].first,y1=a[i].second;
            sumnow+=cal(x,y,x1,y1);
        }
        if(sumnow<minInt){
            minInt=sumnow;
            ans.first=x;
            ans.second=y;
         }
       }
    }

    //(index.first+1) (index.second+1)

    for(double x=index.first+1;x>index.first;x-=0.001){
    for(double y=index.second+1;y>index.second;y-=0.001){
        double sumnow=0;
        for(int i=0;i<idx;i++){
            double x1=a[i].first,y1=a[i].second;
            sumnow+=cal(x,y,x1,y1);
        }
        if(sumnow<minInt){
            minInt=sumnow;
            ans.first=x;
            ans.second=y;
          }
       }
    }

    //(index.first+1) (index.second-1)

    for(double x=index.first+1;x>index.first;x-=0.001){
    for(double y=index.second-1;y<index.second;y+=0.001){
        double sumnow=0;
        for(int i=0;i<idx;i++){
            double x1=a[i].first,y1=a[i].second;
            sumnow+=cal(x,y,x1,y1);
        }
        if(sumnow<minInt){
            minInt=sumnow;
            ans.first=x;
            ans.second=y;
         }
     }
   }

    printf("%.3lf %.3lf",ans.first,ans.second);
}

2.三分极值法

三分极值法是一种可以用于查找凸函数极值点的办法，一般用在指定函数区间内只有一个凸点的情况，它实际上是二分查找思想的延续，二分查找也是逐渐压缩搜索区间，三分极值也是如此，只不过是找中点左右的三分点。以此来加快搜索速度，时间复杂度是O(logn)

AC代码(100ms左右)

#include <iostream>
#include <cstdio>
#include <utility>
#include <vector>
#include <math.h>

using namespace std;

const int M=1000+5;
const double eps=0.0001;
pair<double,double> a[M];
int n;

double cal(double x1,double y1,double x2,double y2){
    return fabs(x1-x2)*fabs(x1-x2)*fabs(x1-x2)+fabs(x1-x2)*fabs(y1-y2)+fabs(y1-y2)*fabs(y1-y2)*fabs(y1-y2);
}

double SumCal(double x,double y){
    double sumNow=0;
    for(int i=0;i<n;i++){
        sumNow+=cal(x,y,a[i].first,a[i].second);
    }
    return sumNow;
}

int main(){
    scanf("%d",&n);
    int N=n;
    int idx=0;
    while(N--){
        double x,y;scanf("%lf%lf",&x,&y);
        a[idx].first=x;
        a[idx++].second=y;
    }

    /*二:三分极值求凹函数极值*/
    //考察原函数,二元变量,则采用二重三分法
    //外层用来逐步逼近目标x，内层用来逐步逼近目标y：
    //当x固定在某值时，用普通三分法再确定y求得当前最小值是很容易做到的……
    //在这一系列最小值的集合再选最小值事实上又是一个二维图像(一元)求极值问题，
    //这可以从曲面的纵向剖物面看出，那么程序内外层就是依据这个思路编写的。

    //coding
    //1.设置基本变量
    double XL,XR,XM,XMM,Xt1,Xt2;
    double YL,YR,YM,YMM,Yt1,Yt2;
    XL=0,XR=1000;

    //2.二重三分法
    while(XR-XL >= eps){//外层对y未知,看作为常数,x看作为唯一变量推断最小值
        XM=(XL+XR)/2;
        XMM=(XM+XR)/2;//右三分点

        YL=0,YR=1000;//x迭代为XM后去内层推断Y的值

        while(YR-YL>=eps){//这时候x定为XM,看作为常数,Y看作为唯一变量推断最小值

            YM=(YL+YR)/2;
            YMM=(YM+YR)/2;

            //然后分别计算二分点和右三分点对应的和函数值,此时X为XM
            Yt1=SumCal(XM,YM);
            Yt2=SumCal(XM,YMM);

            //计算结束之后推断极值点的偏向
            //原理是哪个函数值更小,那么就证明哪个函数值所对应的Y值更逼近极小值
            if(Yt1<=Yt2){//这时候YM在更左边,YMM在更右边,但是更左边的更小,证明左边更接近极小值
                YR=YMM;
            }else{
                YL=YM;
            }
        }
        Xt1=SumCal(XM,YL);//任意YR,YL均可

        YL=0,YR=1000;
        while(YR-YL>=eps){
            YM=(YL+YR)/2;
            YMM=(YM+YR)/2;

            Yt1=SumCal(XMM,YM);
            Yt2=SumCal(XMM,YMM);

            if(Yt1<=Yt2){
                YR=YMM;
            }else{
                YL=YM;
            }
        }
        Xt2=SumCal(XMM,YL);

        if(Xt1<=Xt2){//XM对应的更小,压缩右
            XR=XMM;
        }else{
            XL=XM;
        }
    }

    printf("%.3lf %.3lf",XL,YR);
}

3.模拟退火算法

学习链接
算法步骤
1.初始化：起始温度，终止温度，温度变化率，最优路径顶点集 ，最短长度S
2.利用蒙特卡洛法得到一个比较好的初始解
3.当前温度大于终止温度时，利用两点交换法在当前最优路径基础上构造一条新路径，计算新路径的长度S1，差值dE= S1 - S
4.若 dE < 0，当前最优路径更新为新路径，最短长度更新为S1
否则，任意产生一个介于0~1的概率rt,并计算exp(-dE/T),T为当前温度；若exp(-dE/T) > rt, 当前最优路径更新为新路径，最短长度更新为S1，更新温度