evengridlayout.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 EvenGridLayout
{
  public static void layout
  (
    double cities[][],
    int cityX,
    int cityY,
    double width,
    double height
  )
  {

    double radius = Math.min ( height, width ) / 2.0D;
    int numCities = cities.length;

    TravellerStatus.setCircumference( 8.0D * radius );

    int N = 1;
    int derivedN = N * N;
    while (derivedN < numCities )
    {
      N++;
      derivedN = N * N;
    }

    int naturalProblemSize = N;

    double x_span = width;
    double x_step = x_span / ( naturalProblemSize - 1 );
    double y_span = height;
    double y_step = y_span / ( naturalProblemSize - 1 );

    double step   = Math.min( x_step, y_step );

    if ( ( numCities % 2 ) == 0 )
    {

      TravellerStatus.setExactSolution( step * ( (double) numCities ) );

    }
    else
    {
      TravellerStatus.setExactSolution 
      (
        ( step * ( (double) ( numCities - 1 ) ) )
        + step * Math.sqrt( 2.0D )
      );
    }

    int currentCityNumber = 0;

    for (int i = 0; i < naturalProblemSize; i++)
    {
      for (int j = 0; j < naturalProblemSize; j++)
      {
        if ( currentCityNumber < numCities )
        {
          cities[currentCityNumber][cityX] = step * (double)i;
          cities[currentCityNumber][cityY] = step * (double)j;
        }
        currentCityNumber++;
      }
    }

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