nestedgridlayout.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 NestedGridLayout
{
  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 ) + ( 4 * ( N - 1 ) * ( N - 1 ) );
    while (derivedN < numCities )
    {
      N++;
      derivedN = ( N * N ) + ( 4 * ( N - 1 ) * ( N - 1 ) );
    }

    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 );

    int currentCityNumber = 0;

    for (int i = 0; i < naturalProblemSize; i++)
    {
      for (int j = 0; j < naturalProblemSize; j++)
      {

        if ( ( i > 0 ) && ( j > 0 ) )
        {

/*
** Do the nested four before the bottom right corner, so as not to leave
** it as a straggler requiring an extra long line.  That should simplify
** the computation of the known best solution.
*/

          for (int k = 2; k > 0; k--)
          {
            for (int L = 2; L > 0; L--)
            {
              if ( currentCityNumber < numCities )
              {
                cities[currentCityNumber][cityX] =
                  x_step * (double)i
                  - (((double)k)/3.0D) * x_step;

                cities[currentCityNumber][cityY] =
                  y_step * (double)j
                  - (((double)L)/3.0D) * y_step;
              }

              currentCityNumber++;

            }
          }
        }

        if ( currentCityNumber < numCities )
        {
          cities[currentCityNumber][cityX] = x_step * (double)i;
          cities[currentCityNumber][cityY] = y_step * (double)j;
        }

        currentCityNumber++;
      }
    }

    TravellerStatus.setExactSolutionIsKnown( false );
    TravellerStatus.setExactSolution( -1.0D );
    PerturbLayout.layout( cities, cityX, cityY, width, height );
  }
}