perturblayout.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 PerturbLayout
{

/*
** BIG_FUZZ is the amount we perturb a city location to make distances
** unique in regular layouts without usually having any visual effect.
** It is sized with respect to the width of a pixel on the route display
** canvas.
*/
  public static final double BIG_FUZZ    = 0.01D;

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

    MersenneTwister mt = MersenneTwister.getTwister();
    int numCities = cities.length;

/*
** Fuzzify the city locations to avoid duplicate distances, if desired.
** Turn off exact solution known flag, if we do anything, since we then
** won't know an exact solution, of course.  Width and height inputs are
** ignored, they are already implemented in the other layout classes.
*/

    if (CheckBoxControls.getState(CheckBoxControls.CBC_LAYOUT_PERTURB))
    {
      for (int i = 0; i < numCities; ++i)
      {
        cities[i][cityX] =
          cities[i][cityX] + mt.nextDouble(0.0D, 2.0d * BIG_FUZZ) - BIG_FUZZ;
        cities[i][cityY] =
          cities[i][cityY] + mt.nextDouble(0.0D, 2.0d * BIG_FUZZ) - BIG_FUZZ;
      }
      TravellerStatus.setExactSolutionIsKnown( false );
    }
  }
}