randomcityloopfornearbynodes.java

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

    if
    (
      ( slotPredecessors == null )
      ||
      ( slotStarts == null )
      ||
      ( slotStops == null )
      ||
      ( slotSuccessors == null )
    )
    {
      System.err.println
      (
        "ERROR! RandomCityLoopForNearbyNodes.findSlots(): "
        + "failed to allocate some array at the end."
      );
    }

    for ( int i = 0; i < howManySlots; i++ )
    {
      slotPredecessors[i] = slotBefores[i];
      slotStarts[i]       = slotBeginnings[i];
      slotStops[i]        = slotEndings[i];
      slotSuccessors[i]   = slotAfters[i];
    }

    if (DB) { System.out.println( "findSlots() mark 013" ); }

    int slotList[][] = null;

    try
    {
      int tempSlotList[][] =
        {
          slotPredecessors,
          slotStarts,
          slotStops,
          slotSuccessors,
        };
      if (DB) { System.out.println( "findSlots() mark 014" ); }
      slotList = tempSlotList;
      if (DB) { System.out.println( "findSlots() mark 015" ); }
    }
    catch (Exception e)
    {
      System.err.println
      (
        "ERROR! RandomCityLoopForNearbyNodes.findSlots(): "
        + "failed to fill slotList at end."
      );
    }

    if (DB) { System.out.println( "findSlots() mark 016" ); }

    return slotList;
  }

  private boolean inList( int c, int list[] )
  {

    while ( c < 0 ) { c += ValuatorControls.getNumberOfCities(); }

    for (int i = 0; i < list.length; i++)
    {
      if (c == list[i]) { return true; }
    }
    return false;
  }

  private int listIndex( int c, int list[] )
  {

    while ( c < 0 ) { c += ValuatorControls.getNumberOfCities(); }

    for (int i = 0; i < list.length; i++)
    {
      if (c == list[i]) { return i; }
    }
    return -1;
  }

  private int [] pickCities
  (
    TravellerWorld world,
    int permuteSize,
    int codonName
  )
  {

    MersenneTwister mt = MersenneTwister.getTwister();

/*
** Pick a location in the working canvas playfield area in a gaussian
** distribution centered around the the next city in sequence, from
** which to reach out for the nearest permuteSize cities.
*/

    double someCityExactLocation[] = world.getCityExactLocation(codonName);

    double x =
      someCityExactLocation[TravellerWorld.CITY_X]
      + mt.nextGaussian() * gaussianScaler;
    double y =
      someCityExactLocation[TravellerWorld.CITY_Y]
      + mt.nextGaussian() * gaussianScaler;

    if (this.DB) { System.out.println("pickedCities at: " + x + "," + y ); }

    int    cities[]    = new int[permuteSize];
    double distances[] = new double[permuteSize];

    for ( int i = 0; i < permuteSize; i++ )
    {
      cities[i]    = -1;
      distances[i] = Double.MAX_VALUE;
    }

    int genomeLength = world.getNumberOfCities();

    if (this.DB)
    {
      System.out.println( "pickCities, cities: " + Debugging.dump(cities) );
      System.out.println( "pickCities, distances: " + Debugging.dump(distances) );
    }

    for ( int i = 0; i < genomeLength; i++ )
    {

      double cityExactLocation[] = world.getCityExactLocation(i);

      double cx = cityExactLocation[TravellerWorld.CITY_X];
      double cy = cityExactLocation[TravellerWorld.CITY_Y];

      double distance =
        Math.sqrt( ( ( cx - x ) * ( cx - x ) ) + ( ( cy - y ) * ( cy - y ) ) );
      if (this.DB) { System.out.println( "pickCities OK to inner loop" ); }
      double dtemp;
      int    ctemp;
      int    itemp = i;
      for ( int j = 0 ; j < permuteSize; j++ )
      {
        if ( distance < distances[j] )
        {
          dtemp        = distances[j];
          ctemp        = cities[j];
          distances[j] = distance;
          cities[j]    = itemp;
          distance     = dtemp;
          itemp        = ctemp;
        }
      }
      if (this.DB)
      {
        System.out.println( "pickCities, cities,i: " + Debugging.dump(cities) + i );
        System.out.println( "pickCities, distances: " + Debugging.dump(distances) );
      }
    }

    return cities;
  }

  private void dive(int slot[], int depth, Vector v)
  {

    try
    {

      depth++;

/*
** Since we pass arrays by reference, and will be modifying the array at
** each deeper level of recursion but wanting it intact for further work
** when we return, we must create a new copy at each level for the
** effort there.
*/

      int recurse[] = new int[slot.length];

      for (int i = 0; i < slot.length; i++) { recurse[i] = slot[i]; }

      if ( depth < slot.length)
      {
        while (recurse[depth - 1] != 0)
        {
          recurse[depth - 1]--;
          recurse[depth]++;
          int saveAs[] = new int[slot.length];

/*
**  We need to make a new array copy to save into the returned vector,
**  we will clobber recurse when we next come up for air if we do more
**  work on it in this loop, and again, v is getting a reference, so it
**  needs to be a reference to a separate, never modified copy.
*/

          for (int i = 0; i < slot.length; i++)
          {
            saveAs[i] = recurse[i];
          }
          v.add(saveAs);
          if ( ( depth + 1 ) < slot.length ) { dive( recurse, depth, v ); }
        }
      }

    }
    catch (Exception e)
    {
      System.err.println
      (
        "ERROR! RandomCityLoopForNearbyNodes.dive() threw at depth" + depth
      );
    }
  }

  private Vector createSlotCounts( int codons, int slots )
  {

    Vector v = new Vector();
    if ( v == null )
    {
      System.err.println
      (
        "RandomCityLoopForNearbyNodes.createSlotCounts():"
        + "failed to create a new Vector v"
      );
    }

    int slot[] = new int[slots];
    if ( slot == null )
    {
      System.err.println
      (
        "RandomCityLoopForNearbyNodes.createSlotCounts():"
        + "failed to create a new int slot[]"
      );
    }

    for ( int i = 0; i < slots; i++ )
    {
      slot[i] = 0;
    }
    slot[0] = codons;
    int depth = 0;

/*
** We can safely add slot to v, slot is never itself modified in dive()
*/

    v.add(slot);

/*
** We pass v down, and whenever a new slot fill pattern is found, it is
** appended to v.
*/

    dive( slot, depth, v);
    return v;
  }

  private void updateProgressDisplay( String update )
  {
    if
    (
      CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PROGRESS_COUNTERS)
    ) 
    {
      if ( m_progressDisplay == null )
      {
        m_progressDisplay =
          new SmallDisplay( m_progressDisplayName, SMALL_DISPLAY_WIDTH );
      }
      m_progressDisplay.updateDisplay( update );
    }
    else
    {
      if ( m_progressDisplay != null )
      {
        m_progressDisplay.closeWindow();
        m_progressDisplay = null;
      }
    }
  }

}

/*

[How this algorithm works, from my original "to do" list writeup.]

Consider dropping a random point on the map, computing distances to all cities,
sorting, selecting the M closest, removing them from the genome while keeping
track of the S <= M slots they leave behind, then permuting all combinations of
the removed genomes and reinserting them in permuted order in all possible
subsettings into the voids left behind:

For example, given genome:

a b c d e f g h i j k l m

remove, say, d e h j as the closest to the given point (u,v), leaving
S = three slots "1", "2", "3":

a b c 1 f g 2 i 3 k l m

Permutations:        Subsets:         Child genomes:

d e h j              ()   ()   dehj   a b c f g i d e h j k l m
                     ()   d    ehj    a b c f g d i e h j k l m
                     ()   de   hj     a b c f g d e i h j k l m
                     ()   deh  j      a b c f g d e h i j k l m
                     ()   dehj ()     a b c f g d e h j i k l m
                     d    ()   ehj    a b c d f g i e h j k l m
                     d    e    hj     a b c d f g e i h j k l m
                     d    eh   j      a b c d f g e h i j k l m
                     d    ehj  ()     a b c d f g e h j i k l m
                     de   ()   hj     a b c d e f g i h j k l m
                     de   h    j      a b c d e f g h i j k l m (original!)
                     de   hj   ()     a b c d e f g h j i k l m
                     deh  ()   j      a b c d e h f g i j k l m
                     deh  j    ()     a b c d e h f g j i k l m
                     dehj ()   ()     a b c d e h j f g i k l m
                     and similarly for the permutations below...
d e j h
d h e j
d h j e
d j e h
d j h e
e d h j
e d j h
e h d j
e h j d
e j d h
e j h d
h d e j
h d j e
h e d j
h e j d
h j d e
h j e d
j d e h
j d h e
j e d h
j e h d
j h d e
j h e d

The number of permutations is of course M!  The number of subsets of M
items subsetted in a frozen order into S containers is more complicated
to compute, and turns out to be most easily read from Pascal's triangle:

                                            ..1     ...     ...     ...
                                        ..1     .12     ...     ...     ...
                                    ..1     .11     .78     ...     ...
                                ..1     .10     .66     364     ...     ...
                            ..1     ..9     .55     286    1365     ...
                        ..1     ..8     .45     220    1001    4368     ...
                    ..1     ..7     .36     165     715    3003   12376
                ..1     ..6     .28     120     495    2002    8008   31824
            ..1     ..5     .21     .84     330    1287    5005   19448
        ..1     ..4     .15     .56     210     792    3003   11440   43758
    ..1     ..3     .10     .35     126     462    1716    6435   24310
..1     ..2     ..6     .20     .70     252     924    3432   12870   48620
    ..1     ..3     .10     .35     126     462    1716    6435   24310
        ..1     ..4     .15     .56     210     792    3003   11440   43758
            ..1     ..5     .21     .84     330    1287    5005   19448
                ..1     ..6     .28     120     495    2002    8008   31824
                    ..1     ..7     .36     165     715    3003   12376
                    /   ..1     ..8     .45     220    1001    4368     ...
                  /         ..1     ..9     .55     286    1365     ...
Example:        /               ..1     .10     .66     364     ...     ...
The sixth diagonal, used for M=5,   ..1     .11     .78     ...     ...
has values 1, 6, 21, 56, 126, 252       ..1     .12     ...     ...     ...
for    S = 1  2   3   4    5    6 slots'    ..1     ...     ...     ...
total ways to subdivide those M items without
regard for their identity/value into S slots.

Where the M+1st diagonal contains, in order, the number of subsets of M for
S = 1 , 2, 3, 4, ... slots.  Obviously, remembering that these subsettings
must be multiplied by the number of permutations of M to get the total
number of new genomes to be generated and for which fitnesses must be
calculated, the number of cities allowed must be severely limited:

Number of child genomes generated by permuting M cities and then listing each
permutation in all possible same-ordered subsets partitioned among S <= M
slots, as illustrated above.

                Cities
  \ M 1  2   3    4      5       6        7          8            9
S  \  -  -  --  ---  -----  ------  -------  ---------  -----------
  1 | 1  2   6   24    120     720     5040      40320       362880
S 2 |    6  24  120    720    5040    40320     362880      3628800
l 3 |       60  360   2520   18060   181440    1814400     19958400
o 4 |           840   6720   60480   604800    6652800     79833600
t 5 |                15120  151200  1663200   19958400    259459200
s 6 |                       322640  3991680   51891840    726485760
  7 |                               8648640  121080960   1816214400
  8 |                                        259459200   4141347200
  9 |                                                    8821612800

While geometry might suggest that usually a less than maximal number
of slots will occur, the worst cases are such that a producer / consumer,
rather than list passing, technology must be incorporated before an M
larger than 4 can reasonably be allowed.  Passing a vector of even 2520
chromosomes all at once, for five cities that create three slots, an
easily realized situation, would likely kill the Java engine.  Anyway, a
producer / consumer technology recommends itself for lots of other
reasons, particularly where croppers are concerned, and the thing being
produced is empty population slots to be refilled.

Alternately, of course, emitting the single best result would suffice.

[No queuing was implemented for this heuristic, the latter suggestion
prevailed by its simplicity to implement. By adding adaptive permutation
limits, the ugly worst cases are mostly avoided by getting the points
fairly well locally organized along the tour before using large numbers
of permutees, so that fewer slots are produced in the general case than
would happen at the beginning of a purely randomly seeded problem.]

*/