optimizenodesandedgesnearapoint.java

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

              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 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, modified from my original "to do"
list writeup for less complex algorithm Optimize Nodes Near
A Point.]

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 adding more slots by
computing the distance to all edges, keeping only those
edges where a perpendicular from the random point to the
edge falls between the nodes (cities) defining the edge, and
from that set selecting the M closest "facing" edges and
considering the edge to be another slot between its defining
cities, merging redundant slots, then permuting all
combinations of the removed genomes and reinserting them in
permuted order in all possible subsettings into the voids
left behind.  For purposes of this part of the exposition
we'll sort of ignore the extra slots induced by the facing
edges (because I don't want to rewrite this hard-to-format
part of the original write-up), so just imagine that the
slots by both methods selected merged into the set shown.

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 (widen your text
browser window if this looks like a mess, it is about 120
columns wide):

                                                                ..1     .18     ...     ...     ...     ...     ...
                                                            ..1     .17     ...     ...     ...     ...     ...
                                                        ..1     .16     153     ...     ...     ...     ...     ...
                                                    ..1     .15     136     969     ...     ...     ...     ...
                                                ..1     .14     120     816    4835     ...     ...     ...     ...
                                            ..1     .13     105     680    3866   20299     ...     ...     ...
                                        ..1     .12     .91     560    3050   15464   74463     ...     ...     ...
                                    ..1     .11     .78     455    2370   11598   54164  244807     ...     ...
                                ..1     .10     .66     364    1810    8548   38700  170344  734771     ...     ...
                            ..1     ..9     .55     286    1365    6178   27102  116180  489964     ...     ...
                        ..1     ..8     .45     220    1001    4368   18554   77480  319620 1308844     ...     ...
                    ..1     ..7     .36     165     715    3003   12376   50378  203440  818880     ...     ...
                ..1     ..6     .28     120     495    2002    8008   31824  125960  499260 1959376     ...     ...
            ..1     ..5     .21     .84     330    1287    5005   19448   75582  295820 1140496     ...     ...
        ..1     ..4     .15     .56     210     792    3003   11440   43758  169860  642236 2484564     ...     ...
    ..1     ..3     .10     .35     126     462    1716    6435   24310   93278  356416 1344068     ...     ...
..1     ..2     ..6     .20     .70     252     924    3432   12870   48620  186556  712832 2688136     ...     ...
    ..1     ..3     .10     .35     126     462    1716    6435   24310   93278  356416 1344068     ...     ...
        ..1     ..4     .15     .56     210     792    3003   11440   43758  169860  642236 2484564     ...     ...
            ..1     ..5     .21     .84     330    1287    5005   19448   75582  295820 1140496     ...     ...
                ..1     ..6     .28     120     495    2002    8008   31824  125960  499260 1959376     ...     ...
                    ..1     ..7     .36     165     715    3003   12376   50378  203440  818880     ...     ...
                    /   ..1     ..8     .45     220    1001    4368   18554   77480  319620 1308844     ...     ...
                  /         ..1     ..9     .55     286    1365    6178   27102  116180  489964     ...     ...
Example:        /               ..1     .10     .66     364    1810    8548   38700  170344  734771     ...     ...
The sixth diagonal, used for M=5,   ..1     .11     .78     455    2370   11598   54164  244807     ...     ...
has values 1, 6, 21, 56, 126, 252       ..1     .12     .91     560    3050   15464   74463     ...     ...     ...
for    S = 1  2   3   4    5    6 slots'    ..1     .13     105     680    3866   20299     ...     ...     ...
total ways to subdivide those M items without   ..1     .14     120     816    4835     ...     ...     ...     ...
regard for their identity/value into S slots.       ..1     .15     136     969     ...     ...     ...     ...
                                                        ..1     .16     153     ...     ...     ...     ...     ...
                                                            ..1     .17     ...     ...     ...     ...     ...
                                                                ..1     .18     ...     ...     ...     ...     ...

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 to prevent insufferable single heuristic application
run times.

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

                Cities
  \ M  1    2     3      4        5         6          7            8
S  \  --  ---  ----  -----  -------  --------  ---------  -----------
  1 |  1    2     6     24      120       720       5040        40320
S 2 |  2    6    24    120      720      5040      40320       362880
l 3 |  3   12    60    360     2520     18060     181440      1814400
o 4 |  4   20   120    840     6720     60480     604800      6652800
t 5 |  5   30   210   1680    15120    151200    1663200     19958400
s 6 |  6   42   336   3024    30240    322640    3991680     51891840
  7 |  7   56   504   5040    55440    665280    8648640    121080960
  8 |  8   72   720   7920    95040   1235520   17297280    259459200
  9 |  9   90   990  11880   154440   2162160   32432400    518918400
 10 | 10  110  1320  17160   240240   3603600   57657600    980179200
 11 | 11  132  1716  24024   360360   5765760   98017920   1764322560
 12 | 12  156  2184  32760   524160   8910720  160392960   3047466240
 13 | 13  182  2730  43440   741360  13358880  160392960   5078707200
 14 | 14  210  3360  56880  1025760  19513440  390499200   8202700800
 15 | 15  240  4080  73200  1391760  27864000  585547200  12887078400
 16 | 16  272  4896  92784  1855680  38998080  858533760  19755348480

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, and is in fact the course taken.

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

*/