randomlayout.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 RandomLayout
{
  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;
    TravellerStatus.setCircumference( 8.0D * radius );

    for (int i = 0; i < numCities; ++i)
    {
      cities[i][cityX] = mt.nextDouble( 0.0D, width );
      cities[i][cityY] = mt.nextDouble ( 0.0D, height );
    }

/*
** It is fairly pointless in this case to perturb already random cities,
** but this allows for side effects that might someday be put into the
** perturbCities routine, as for example to force perturbation prior to
** a Delaunay triangulation to reduce colinearity and cocircularity
** problems (which again wouldn't be needed here, but, belt and
** suspenders rules in programming as elsewhere).
*/
    TravellerStatus.setExactSolutionIsKnown( false );
    TravellerStatus.setExactSolution( -1.0D );
    PerturbLayout.layout( cities, cityX, cityY, width, height );
  }
}