randomcityloopfornearbynodesandedges.java

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

      double r        = complexReply[1];
      double s        = complexReply[2]; // so far unused
      double L        = complexReply[3]; // so far unused

      if ( ( r >= 0.0D ) && ( r <= 1.0D ) )  // check "facingness"
      {
        DoubleAndEdgeSortedOnDouble edge = new
          DoubleAndEdgeSortedOnDouble
          (
            distance,
            new Edge( startCity, stopCity, false )
          );
        for ( int j = 0; j < permuteSize; j++ )
        {
          if ( edges[j] == null )
          {
            edges[j] = edge;
            break;
          }
          else
          {

/*
** Conceptually, drop the edge we are carrying into the array slot, and
** pick up the contents of the array slot to possibly drop it further
** along in the array.  Practically, we are doing a cheesy insertion
** sort, but that is OK, because we are doing it into a list that will
** probably never get longer than single digit size anyway, the range
** where cheesy sorts are the most efficient sorts.
** 
** If we fall through this loop without ever dropping edge, then it was
** more distant than all edges currently in the array, and the array was
** already fully populated.  If we drop edge somewhere while walking a
** fully populated array, then we will carry out the previously most
** distant eligible edge and vanish it.  Let's hope the garbage
** collector is paying attention at the time!
** 
** It is worth commenting that we could have done all this without ever
** bothering with class Edge (which is overkill here) or the Sortable
** interface, but the sheer expressiveness of the two creates this brief
** conditional out of what would otherwise have been (at least) tens of
** lines of code.
*/

            if ( edge.compareTo( edges[j] ) == Sortable.THIS_LESS_THAN )
            {
              edge.swap( (Object) edge, (Object) edges[j] );
            }
          }
        }
      }
    }

    if (this.DB)
    {
      System.out.println
      (
        "pickEdges after loop, edges: "
        + Debugging.dump(edges)
      );
    }

    int edgesFound = 0;

    while ( edgesFound < permuteSize && edges[ edgesFound ] != null )
    {
      edgesFound++;
    }

/*
** Cater for the quite real possibility that we found no facing edges at all!
*/

    Edge result[] = null;
    if ( edgesFound > 0 )
    {
      result = new Edge[ edgesFound ];
    }

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

/*
** We really aren't interested in the distance per se in the caller,
** just that we get back a short list with the closest edge first.
*/

      result[i] = edges[i].getEdge();
    }

    if (DB)
    {
      if ( result == null )
      {
        System.out.println
        (
          "pickEdges: returning null"
        );
      }
      else
      {
        System.out.println
        (
          "pickEdges: returning "
          + Debugging.dump( result )
        );
      }
    }
    return result; // possibly null; see above
  }

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

    double x = nearnessPoint.getX();
    double y = nearnessPoint.getY();

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

    for ( int i = 0; i < permuteSize; i++ )
    {
      cities[i]    = -1;
      distances[i] = java.lang.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)
  {

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

  private Vector slotCounts(int codons, int slots)
  {
    Vector v = new Vector(10, 10);
    int slot[] = new int[slots];
    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;
      }
    }
  }

  private double [] distanceFromAPointToALine
  (
    Coordinates point,
    Coordinates lineBegin,
    Coordinates lineEnd
  )
  {
    double Ax = lineBegin.getX();
    double Ay = lineBegin.getY();
    double Bx = lineEnd.getX();
    double By = lineEnd.getY();
    double Cx = point.getX();
    double Cy = point.getY();
    double Px; // x of point on line at perpendicular dropped from C.
    double Py; // y of point on line at perpendicular dropped from C.
    double r;  // r parameter from description below.
    double L;  // length of line segment AB.
    double s;  // s parameter from description below.
    double distance;

    L = Math.sqrt
        ( ( ( Ax - Bx ) * ( Ax - Bx ) ) + ( ( Ay - By ) * ( Ay - By ) ) );
    r = ( ( ( Cx - Ax ) * ( Bx - Ax ) ) + ( ( Cy - Ay ) * ( By - Ay ) ) )
        / ( L * L );
    Px = Ax + ( r * ( Bx - Ax ) );
    Py = Ay + ( r * ( By - Ay ) );
    s = ( ( ( Ay - Cy ) * ( Bx - Ax ) ) - ( ( Ax - Cx ) * ( By - Ay ) ) )
        / ( L * L );
    distance = Math.abs( s ) * L;
    double result[] = { distance, r, s, L, };
    return result;
  }

}

/*
 from comp_graphics_algorithms_FAQ.htm:
----------------------------------------------------------------------
Subject 1.02: How do I find the distance from a point to a line?


    Let the point be C (Cx,Cy) and the line be AB (Ax,Ay) to (Bx,By).
    Let P be the point of perpendicular projection of C on AB.  The parameter
    r, which indicates P's position along AB, is computed by the dot product 
    of AC and AB divided by the square of the length of AB:
    
    (1)     AC dot AB
        r = ---------  
            ||AB||^2
    
    r has the following meaning:
    
        r=0      P = A
        r=1      P = B
        r&lt;0      P is on the backward extension of AB
        r&gt;1      P is on the forward extension of AB
        0&lt;r&lt;1    P is interior to AB
    
    The length of a line segment in d dimensions, AB is computed by:
    
        L = sqrt( (Bx-Ax)^2 + (By-Ay)^2 + ... + (Bd-Ad)^2)

    so in 2D:   
    
        L = sqrt( (Bx-Ax)^2 + (By-Ay)^2 )
    
    and the dot product of two vectors in d dimensions, U dot V is computed:
    
        D = (Ux * Vx) + (Uy * Vy) + ... + (Ud * Vd)
    
    so in 2D:   
    
        D = (Ux * Vx) + (Uy * Vy) 
    
    So (1) expands to:
    
            (Cx-Ax)(Bx-Ax) + (Cy-Ay)(By-Ay)
        r = -------------------------------
                          L^2

    The point P can then be found:

        Px = Ax + r(Bx-Ax)
        Py = Ay + r(By-Ay)

    And the distance from A to P = r*L.

    Use another parameter s to indicate the location along PC, with the 
    following meaning:
           s&lt;0      C is left of AB
           s&gt;0      C is right of AB
           s=0      C is on AB

    Compute s as follows:

            (Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)
        s = -----------------------------
                        L^2


    Then the distance from C to P = |s|*L.


*/

/*

[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.]

*/