怎么用lisp解决求到平面上n点距离和最小的点

aimisiyou · 发表于 2014-12-19 19:43:18

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

×

怎么用lisp解决求到平面上n点距离和最小的点？（更进一步，多维空间）

newer · 发表于 2014-12-19 19:45:53

这个具体可以做什么应用？

aimisiyou · 发表于 2014-12-19 19:59:40

newer 发表于 2014-12-19 19:45
这个具体可以做什么应用？

很多方面用到啊，比如已知n个村庄共用一水塔，求水塔位置设在何处使水塔到各村的距离和最小（即通水管道最小）？类似学校、基站等都属于取点问题，若数值求解要采取求导，麻烦，有些几何作图可省略求导过程，目的在于此。

newer · 发表于 2014-12-19 20:01:45

aimisiyou 发表于 2014-12-19 19:59
很多方面用到啊，比如已知n个村庄共用一水塔，求水塔位置设在何处使水塔到各村的距离和最小（即通水管道 ...

按你这么说，求点集的最小内切圆的圆心就是你要的点吧。

aimisiyou · 发表于 2014-12-19 20:05:02

比如到三角形三顶点距离和最小的点（即费马点），用几何作图很方便就可求出，但数值解法就相当麻烦了，对三个根号式的和求导。

aimisiyou · 发表于 2014-12-19 20:07:23

newer 发表于 2014-12-19 20:01
按你这么说，求点集的最小内切圆的圆心就是你要的点吧。

不是一个概念，是求满足到n个点距离和最小的点。

newer · 发表于 2014-12-19 20:08:48

aimisiyou 发表于 2014-12-19 20:07
不是一个概念，是求满足到n个点距离和最小的点。

那你有比较成熟的算法伪代码吗？

newer · 发表于 2014-12-19 20:13:35

转帖几个文献吧

请点击此处下载

查看状态：需购买或无权限

您的用户组是：游客

文件名称:(费马点)寻求连接同一平面有限给定点距离和最小的点和网络.pdf
下载次数:9 文件大小:541.35 KB
下载权限: 不限以上 [免费赚D豆]

aimisiyou · 发表于 2014-12-19 20:15:42

newer 发表于 2014-12-19 20:08
那你有比较成熟的算法伪代码吗？

就是没有啊，不过老早就想lisp能不能实现点循环，即此点不满足要求，next 下一个点，这个过渡怎么实现？

newer · 发表于 2014-12-19 20:17:52

请点击此处下载

查看状态：需购买或无权限

您的用户组是：游客

文件名称:费马点的应用举例.ppt
下载次数:1 文件大小:446.5 KB
下载权限: 不限以上 [免费赚D豆]

newer · 发表于 2014-12-19 20:19:06

aimisiyou 发表于 2014-12-19 20:15
就是没有啊，不过老早就想lisp能不能实现点循环，即此点不满足要求，next 下一个点，这个过渡怎么实现？

这个算法肯定能找到算法的，有算法就好实现了。

newer · 发表于 2014-12-19 20:23:48

费马点是指求到N个点距离和最小的点。通常要求的是简单多边形的费马点。

1、http://acm.hdu.edu.cn/showproblem.php?pid=2440 按照题意知道是一个简单的多边形即凸包，但给出的点并没有按照顺序的，所以需要自己先求出凸包，然后在用随机淬火求费马点。

[cpp] view plaincopy

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<algorithm>
#include<ctime>
using namespace std;
#define eps 1e-10
int Fabs(double d)
{
if(fabs(d)<eps) return 0;
else return d>0?1:-1;
}
struct point
{
double x,y;
}p[105],sta[105];
int oper[8][2]={0,1,0,-1,-1,0,1,0,1,1,1,-1,-1,1,-1,-1},top;
double x_multi(point p1,point p2,point p3)
{
return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}
double Dis(point p1,point p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
bool cmp(point a,point b)
{
if(Fabs(x_multi(p[0],a,b))>0) return 1;
if(Fabs(x_multi(p[0],a,b))<0) return 0;
if(Fabs(Dis(p[0],a)-Dis(p[0],b))<0)
return 1;
return 0;
}
void Graham(int n)
{
int i,k=0,tot;
for(i=1;i<n;i++)
if((p.y<p[k].y)||((p.y==p[k].y)&&(p.x<p[k].x)))
k=i;
swap(p[0],p[k]);
sort(p+1,p+n,cmp);
tot=1;
for(i=2;i<n;i++)
if(Fabs(x_multi(p,p[i-1],p[0])))
p[tot++]=p[i-1];
p[tot++]=p[n-1];
sta[0]=p[0],sta[1]=p[1];
i=top=1;
for(i=2;i<tot;i++)
{
while(top>=1&&Fabs(x_multi(p,sta[top],sta[top-1]))>=0)
{
if(top==0) break;
top--;
}
sta[++top]=p;
}
}
double allDis(int n,point f)
{
double sum=0.0;
int i;
for(i=0;i<n;i++)
sum+=Dis(sta,f);
return sum;
}
point fermat(int n) //求费马点
{
double step=0;
int i,j;
for(i=0;i<n;i++)
step+=fabs(sta.x)+fabs(sta.y);
point f;
f.x=0,f.y=0;
for(i=0;i<n;i++)
f.x+=sta.x,f.y+=sta.y;
f.x/=n,f.y/=n;
point t;
while(step>eps)
{
for(i=0;i<8;i++)
{
t.x=f.x+oper[0]*step;
t.y=f.y+oper[1]*step;
if(allDis(n,t)<allDis(n,f))
f=t;
}
step/=2;
}
return f;
}
int main()
{
int t,n,i;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%lf%lf",&p.x,&p.y);
Graham(n);
point ans=fermat(top+1);
printf("%.0lf\n",allDis(top+1,ans));
if(t>0) puts("");
}
return 0;
}

2、http://acm.hdu.edu.cn/showproblem.php?pid=3694 //求一个四边形的费马点，wrong了n次网上到处查才知道此题非常严谨，卡随机淬火算法。并且给出的四边形并不一定是凸四边形，所以需要讨论，如果是凸四边形，按照四边形的特性费马点就是对角线的交点，如果是凹的就是其中某一个顶点。

[cpp] view plaincopy

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<algorithm>
#include<ctime>
using namespace std;
#define eps 1e-8

int Fabs(double d)
{
if(fabs(d)<eps) return 0;
else return d>0?1:-1;
}

struct point
{
double x,y;
}p[10],sta[10];
int oper[8][2]={0,1,0,-1,-1,0,1,0,1,1,1,-1,-1,1,-1,-1},top;

double x_multi(point p1,point p2,point p3)
{
return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}

double Dis(point p1,point p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}

bool cmp(point a,point b)
{
if(Fabs(x_multi(p[0],a,b))>0) return 1;
if(Fabs(x_multi(p[0],a,b))<0) return 0;
if(Fabs(Dis(p[0],a)-Dis(p[0],b))<0)
 return 1;
return 0;
}

void Graham(int n)
{
int i,k=0,tot;
for(i=1;i<n;i++)
 if((p.y<p[k].y)||((p.y==p[k].y)&&(p.x<p[k].x)))
 k=i;
swap(p[0],p[k]);
sort(p+1,p+n,cmp);

/*tot=1;//下面直接用顶点个数判断是否为凸包，所以这里不去共线点
for(i=2;i<n;i++)
 if(Fabs(x_multi(p,p[i-1],p[0])))
 p[tot++]=p[i-1];
p[tot++]=p[n-1];*/

sta[0]=p[0],sta[1]=p[1];
i=top=1;
for(i=2;i<n;i++)
{
 while(top>=1&&Fabs(x_multi(p,sta[top],sta[top-1]))>=0)
 {
 if(top==0) break;
 top--;
 }
 sta[++top]=p;
}
}

/*double allDis(int n,point f)
{
double sum=0.0;
int i;
for(i=0;i<n;i++)
 sum+=Dis(p,f);
return sum;
}

point fermat(int n)
{
double step=0;
int i,j;
for(i=0;i<n;i++)
 step+=fabs(sta.x)+fabs(sta.y);
point f;
f.x=0,f.y=0;
for(i=0;i<n;i++)
 f.x+=sta.x,f.y+=sta.y;
f.x/=n,f.y/=n;
point t;
while(step>1e-10)
{
 for(i=0;i<8;i++)
 {
 t.x=f.x+oper[0]*step;
 t.y=f.y+oper[1]*step;
 if(allDis(n,t)<allDis(n,f))
 f=t;
 }
 step/=2;
}
return f;
}
*/
int main()
{
int i,j;
while(~scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&p[0].x,&p[0].y,&p[1].x,&p[1].y,&p[2].x,&p[2].y,&p[3].x,&p[3].y))
{
 if(p[0].x==-1&&p[0].y==-1&&p[1].x==-1&&p[1].y==-1&&p[2].x==-1&&p[2].y==-1&&p[3].x==-1&&p[3].y==-1)
 break;
 Graham(4);
 double ans;
 if(top==3)
 ans=Dis(sta[0],sta[2])+Dis(sta[1],sta[3]);//凸四边形就直接取对角线交点
 else
 {
 ans=1e50;
 double sum=0;
 for(i=0;i<4;i++)
 {
 sum=0.0;
 for(j=0;j<4;j++)
 if(i!=j)
 sum+=Dis(p,p[j]);
 ans=min(sum,ans);
 }
 }
 printf("%.4lf\n",ans);
}
return 0;
}
[/code]

newer · 发表于 2014-12-19 20:27:50

本帖最后由 newer 于 2014-12-19 20:29 编辑

Description

Luke wants to upgrade his home computer network from 10mbs to 100mbs. His existing network uses 10base2 (coaxial) cables that allow you to connect any number of computers together in a linear arrangement. Luke is particulary proud that he solved a nasty NP-complete problem in order to minimize the total cable length.
Unfortunately, Luke cannot use his existing cabling. The 100mbs system uses 100baseT (twisted pair) cables. Each 100baseT cable connects only two devices: either two network cards or a network card and a hub. (A hub is an electronic device that interconnects several cables.) Luke has a choice: He can buy 2N-2 network cards and connect his N computers together by inserting one or more cards into each computer and connecting them all together. Or he can buy N network cards and a hub and connect each of his N computers to the hub. The first approach would require that Luke configure his operating system to forward network traffic. However, with the installation of Winux 2007.2, Luke discovered that network forwarding no longer worked. He couldn't figure out how to re-enable forwarding, and he had never heard of Prim or Kruskal, so he settled on the second approach: N network cards and a hub.

Luke lives in a loft and so is prepared to run the cables and place the hub anywhere. But he won't move his computers. He wants to minimize the total length of cable he must buy.

Input

The first line of input contains a positive integer N <= 100, the number of computers. N lines follow; each gives the (x,y) coordinates (in mm.) of a computer within the room. All coordinates are integers between 0 and 10,000.

Output

Output consists of one number, the total length of the cable segments, rounded to the nearest mm.

Sample Input

40 00 1000010000 1000010000 0

Sample Output

28284

Source

Waterloo Local 2002.01.26

题目大意：

求n边形的费马点，即找到一个点使得这个点到n个点的距离之和最小。

解题思路：

三角形也有费马点，三角形费马点是这样定义的：寻找三角形内的一个点，使得三个顶点到该点的距离之和最小。
三角形费马点的做法是：
（1）若有一个角大于120度，那么这个角所在的点就是费马点。
（2）若不存在，那么对于三角形ABC，任取两条边（假设AB、AC），向外做等边三角形得到C' 和 A' ，那么AA' 和CC' 的交点就是费马点。

那么对于这题n多边形，我采取的策略完全不同，采用了模拟退火的做法，这种做法相对比较简单，也可以用在求三角形费马点之中。
模拟退火算法就跟数值算法里面的自适应算法相同的道理
（1）定义好步长
（2）寻找一个起点，往8个方向的按这个步长搜索。
（3）如果找到比答案更小的点，那么以这个新的点为起点，重复（2）
（4）如果找不到比答案更小的点，那么步长减半，再尝试（2）
（5）直到步长小于要求的答案的精度就停止。

解题代码：

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
const int offx[]={1,1,0,-1,-1,-1,0,1};
const int offy[]={0,1,1,1,0,-1,-1,-1};
const int maxn=110;
const double eps=1e-2;
struct point{
double x,y;
point(double x0=0,double y0=0){x=x0;y=y0;}
double getdis(point p){
return sqrt( (x-p.x)*(x-p.x)+(y-p.y)*(y-p.y) );
}
}p[maxn];
int n;
double getsum(point p0){
double sum=0;
for(int i=0;i<n;i++) sum+=p0.getdis(p);
return sum;
}
void solve(){
for(int i=0;i<n;i++) scanf("%lf%lf",&p.x,&p.y);
double ans=getsum(p[0]),step=100;
point s=p[0],d;
while(step>eps){
bool flag=false;
for(int i=0;i<8;i++){
d=point(s.x+step*offx,s.y+step*offy);
double tmp=getsum(d);
if(tmp<ans){
s=d;
ans=tmp;
flag=true;
}
}
if(!flag) step/=2;
}
printf("%.0f\n",ans);
}
int main(){
while(scanf("%d",&n)!=EOF){
solve();
}
return 0;
}

#include <iostream> 
#include <cmath> 
#include <cstdio> 
using namespace std; 
 
const int offx[]={1,1,0,-1,-1,-1,0,1}; 
const int offy[]={0,1,1,1,0,-1,-1,-1}; 
const int maxn=110; 
const double eps=1e-2; 
 
struct point{ 
        double x,y; 
        point(double x0=0,double y0=0){x=x0;y=y0;} 
        double getdis(point p){ 
                return sqrt( (x-p.x)*(x-p.x)+(y-p.y)*(y-p.y) ); 
        } 
}p[maxn]; 
 
int n; 
 
double getsum(point p0){ 
        double sum=0; 
        for(int i=0;i<n;i++) sum+=p0.getdis(p); 
        return sum; 
} 
 
void solve(){ 
        for(int i=0;i<n;i++) scanf("%lf%lf",&p.x,&p.y); 
        double ans=getsum(p[0]),step=100; 
        point s=p[0],d; 
        while(step>eps){ 
                bool flag=false; 
                for(int i=0;i<8;i++){ 
                        d=point(s.x+step*offx,s.y+step*offy); 
                        double tmp=getsum(d); 
                        if(tmp<ans){ 
                                s=d; 
                                ans=tmp; 
                                flag=true; 
                        } 
                } 
                if(!flag) step/=2; 
        } 
        printf("%.0f\n",ans); 
} 
 
int main(){ 
        while(scanf("%d",&n)!=EOF){ 
                solve(); 
        } 
        return 0; 
}

newer · 发表于 2014-12-19 20:44:04

aimisiyou 发表于 2014-12-19 20:15
就是没有啊，不过老早就想lisp能不能实现点循环，即此点不满足要求，next 下一个点，这个过渡怎么实现？

搜索了网络，大都是讨论多边形的费马点的，也就是凸包的费马点，你的意思是求所有点的？所有点的这个有点难吧？有唯一解吗?

aimisiyou · 发表于 2014-12-19 20:50:07

newer 发表于 2014-12-19 20:27
DescriptionLuke wants to upgrade his home computer network from 10mbs to 100mbs. His existing networ ...

原来是采用八方向键啊，我初步想法是四方向键，方向越多运算量越大，但方向少了又不精确。

账号		自动登录	找回密码
密码			立即注册

[研讨] 怎么用lisp解决求到平面上n点距离和最小的点

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

相关帖子

点评

点评

点评

点评

点评

点评

点评

点评

点评