模拟退火求二维费马点

  1. 云栖社区>
  2. 博客>
  3. 正文

模拟退火求二维费马点

哈沙给 2013-08-12 13:42:00 浏览1312
展开阅读全文

一.概念引入

        AC过后,突然想起费马点和最小覆盖圆的圆心有关系吗?答案是没关系,如下图:费马点肯定在等腰梯形内,不是在圆心。

image

        模拟退火算法与初始值无关,算法求得的解与初始解状态S(是算法迭代的起点)无关;模拟退火算法具有渐近收敛性,已在理论上被证明是一种以概率收敛于全局最优解的全局优化算法;模拟退火算法具有并行性。

        三角形费马点:如果三角形ABC中有一个角的角度大于等于120, 那么该角的顶点就是费马点;如果三角形ABC的三个角的角度都小于120, 那么该三角形的费马点P为满足条件angle APB=angle BPC=angle CPA ,所以三角形的费马点也称为三角形的等角中心。

        牛顿迭代:令f(x,y)=Sigma( sqrt((x-xi)^2 + (y-yi)^2) ),本题要求f(x,y)的最小值,此函数是凸的。可验证极小值唯一,且当p0,p1..pn-1不在一条线上时,极小值点唯一,于是只需求得f'x=f'y=0的点即可。用牛顿迭代法解此二元方程组。

        塞瓦定理:设O是△ABC内任意一点,AO、BO、CO分别交对边于D、E、F,则 BD/DC*CE/EA*AF/FB=1。

        三角形内角平分线定理:今天给大二孩子将计算几何求内切圆圆心用到了。

image

二.算法实现

        以POJ2420为例,直接去AC吧。

        模拟退火(Simulated Annealing),题目:就是求多边形的费马点,输出最小的距离。讨论群里有人说应该说牛顿迭代是……所有大学生应该想到的……枚举是……高中生想到的……顿时无语。


import java.util.Scanner;

public class POJ2420 {

  static Point[] p;
  static int n;
  
  public static void main(String[] args) {
    double x;
    double y;
    Scanner sc = new Scanner(System.in);
    while(sc.hasNext()) {
      n = sc.nextInt();
      p = new Point[n];
      for(int i=0; i<n; i++) {
        p[i] = new Point();
      }
      for(int i=0; i<n; i++) {
        x = sc.nextDouble();
        y = sc.nextDouble();
        p[i] = new Point(x,y);
      }
      double ans = solve();
      System.out.println((int)ans);
    }
  }

  private static double solve() {
    
    Point pre = new Point();
    Point cur = new Point();
    /*
     * 终于找到错了,发现"cur = pre"的话,cur和pre完全一样,
     * 调试里id都是34,内存一样,
     * 我把其他的赋值全部搞成属性赋值就AC了
     * 坑了一天
     */
    
    double dis = getAllDistance(cur);
    double step = 10000;
    double r = 0.5;
    double[][] d = {{0,1},{0,-1},{-1,0},{1,0}};
    Point node = new Point();
    while(Double.compare(step, 0.2)>0) {
      boolean ok = true;
      while(ok) {
        ok = false;
        /*
         * 下面的赋值是必须的
         * 因为如果下面的for循环没有更新node,
         * 那么for循环后的赋值就没法进行
         */
        node.x = cur.x;
        node.y = cur.y;
        for(int i=0; i<4; i++) {
          //四次循环中cur不能 变
          pre.x = d[i][0]*step + cur.x;
          pre.y = d[i][1]*step + cur.y;
          //由于坐标大于0,所以小于0的坐标定然不是最小值
          if(pre.x<0||pre.y<0) {
            continue;
          }
          double temp = getAllDistance(pre);
//          System.out.println("step:"+step +"  " + 
//          "dis:"+dis +"   "+"temp:"+temp+
//          " "+cur.x+"  "+cur.y+"---"+pre.x+"  "+pre.y);
          if(dis>temp) {
            dis = temp;
            node.x = pre.x;
            node.y = pre.y;
            ok = true;
          }
        }
        cur.x = node.x;
        cur.y = node.y;
      }
      step *= r;
    }
    return Math.floor(dis+0.5);
    //return dis;
  }

  private static double getAllDistance(Point cur) {
    double sum = 0;
    for(int i=0; i<n; i++) {
      sum += getDistance(cur,p[i]);
    }
    return sum;
  }

  private static double getDistance(Point a, Point b) {
    return Math.hypot(a.x-b.x, a.y-b.y);
  }

}

class Point {
  double x;
  double y;
  public Point() {
    this.x = 0;
    this.y = 0;
  }
  public Point(double x, double y) {
    super();
    this.x = x;
    this.y = y;
  }
}

网友评论

登录后评论
0/500
评论
哈沙给
+ 关注