circlelayout.java

经典的货郎担问题解决办法

package com.well.www.user.xanthian.java.layouts;

import java.util.*;

import com.well.www.user.xanthian.java.structures.*;
import com.well.www.user.xanthian.java.tools.*;
import com.well.www.user.xanthian.java.ui.*;

public class CircleLayout
{
  public static void layout
  (
    double cities[][],
    int cityX,
    int cityY,
    double width,
    double height
  )
  {

    MersenneTwister mt = MersenneTwister.getTwister();
    double radius = Math.min ( height, width ) / 2.0D;

    int numCities = cities.length;

    int naturalProblemSize = numCities;

    double circumference = radius * 2.0D * Math.PI;

    double center_x = width / 2.0D;
    double center_y = height / 2.0D;

    IntDoublePairSortedOnDouble caac[] =
      new IntDoublePairSortedOnDouble[numCities]; 

    for (int i = 0; i < numCities; ++i)
    {
      double angle = mt.nextDouble() * 2.0 * Math.PI;

      caac[i] = new IntDoublePairSortedOnDouble( i, angle );

      cities[i][cityX] = center_x + (radius * Math.cos(angle));
      cities[i][cityY] = center_y + (radius * Math.sin(angle));
    }

    QuickSortAlgorithm.sort( caac );

    double exactSolution = 0.0D;

    exactSolution +=
      Math.sqrt
      (
        (
          (
            cities[caac[0].getInt()][cityX] -
            cities[caac[numCities - 1].getInt()][cityX]
          )
          *
          (
            cities[caac[0].getInt()][cityX] -
            cities[caac[numCities - 1].getInt()][cityX]
          )
        )
        +
        (
          (
            cities[caac[0].getInt()][cityY] -
            cities[caac[numCities - 1].getInt()][cityY]
          )
          *
          (
            cities[caac[0].getInt()][cityY] -
            cities[caac[numCities - 1].getInt()][cityY]
          )
        )
      );

    for (int i = 1; i < numCities; i++)
    {
      exactSolution +=
        Math.sqrt
        (
          (
            (
              cities[caac[i].getInt()][cityX] -
              cities[caac[i - 1].getInt()][cityX]
            )
            *
            (
              cities[caac[i].getInt()][cityX] -
              cities[caac[i - 1].getInt()][cityX]
            )
          )
          +
          (
            (
              cities[caac[i].getInt()][cityY] -
              cities[caac[i - 1].getInt()][cityY]
            )
            *
            (
              cities[caac[i].getInt()][cityY] -
              cities[caac[i - 1].getInt()][cityY]
            )
          )
        );

    }

    TravellerStatus.setExactSolution( exactSolution );
    TravellerStatus.setExactSolutionIsKnown( true );
    PerturbLayout.layout( cities, cityX, cityY, width, height );

    TravellerStatus.setCircumference( circumference );
  }
}