optimizenodesandedgesnearapoint.java

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

      System.out.println
      (
        Debugging.dump(bestPermutation)
        + " bestPermutation in OptimizeNodesAndEdgesNearAPoint"
      );
      System.out.println
      (
        offspring.toString()
        + " final offspring genome in OptimizeNodesAndEdgesNearAPoint"
      );
    }

    if (VDB) { m_vdb.step( offspring ); }

    double finalFitness = offspring.testFitness();

/*
** We intend only to change for the better, but we'd better be careful,
** so if we haven't changed, or we've changed the wrong way, we haven't
** improved.  Report back so that adaptive permutation high limit can
** eventually be updated.
*/

    if
    (
      (
        Math.abs( finalFitness - startingFitness )
        <
        TravellerStatus.LITTLE_FUZZ
      )
      ||
      ( finalFitness > startingFitness )
    )
    {
      PermutationController.reportFailure();
      // System.out.println ( "F: " + startingFitness + " / " + finalFitness + " Near" );
    }
    else
    {
      PermutationController.reportSuccess();
      // System.out.println ( "S: " + startingFitness + " / " + finalFitness + " Near" );
    }

    if (VDB) { m_vdb.done( parent, offspring ); }

    return offspring;
  }

  private double fitnessIncrement
  (
    Integer             permutation[],
    int                 slotCounts[],
    int                 cityList[],
    int                 slotBefores[],
    int                 slotBeginnings[],
    int                 slotEndings[],
    int                 slotAfters[],
    TravellerChromosome tc
  )
  {
    TravellerWorld world = tc.getWorld();
    double increment =  0.0D;
    int howManySlots = slotBeginnings.length;
    int howManyCodons = permutation.length;

    int placeInPermutation = 0;
    for (int i = 0; i < howManySlots; i++)
    {
      if ( slotCounts[i] == 0 )
      {
        increment +=
          world.getDistance
          (
            tc.getCity(slotBefores[i]),
            tc.getCity(slotAfters[i])
          );
      }
      else
      {
        increment +=
          world.getDistance
          (
            tc.getCity(slotBefores[i]),
            cityList[permutation[placeInPermutation].intValue()]
          );
        for ( int j = 1; j < slotCounts[i]; j++ )
        {
          increment +=
            world.getDistance
            (
              cityList[permutation[placeInPermutation + j - 1].intValue()],
              cityList[permutation[placeInPermutation + j].intValue()]
            );
        }
        increment +=
          world.getDistance
          (
            cityList
            [
              permutation[placeInPermutation + slotCounts[i] - 1].intValue()
            ],
            tc.getCity(slotAfters[i])
          );
          placeInPermutation += slotCounts[i];
      }
    }
    return increment;
  }

  private int[][] findSlots
  (
    Edge cityEdges[], // full of edges full of codons
    int cityList[],   // full of city _names_
    TravellerChromosome tc
  )
  {
    if (DB)
    {
      System.out.println
      (
        "findSlots at entry: genome "
        + tc.toString()
        + "\r\n"
        + "... cityList / cityEdges "
        + Debugging.dump( cityList )
        + " / "
        + Debugging.dump( cityEdges )
      );
    }

    int genomeLength = ValuatorControls.getNumberOfCities();
    int slotAllowance = cityList.length;

    if ( cityEdges != null ) { slotAllowance += cityEdges.length; }

/*
** slotAllowance may in the end be too big, because several situations
** can create slots that need to be combined.
*/

    int slotBefores[]    = new int[slotAllowance];
    int slotBeginnings[] = new int[slotAllowance];
    int slotEndings[]    = new int[slotAllowance];
    int slotAfters[]     = new int[slotAllowance];

    for ( int i = 0; i < cityList.length; i++ )
    {
      slotBefores[i]    = -1;
      slotBeginnings[i] = -1;
      slotEndings[i]    = -1;
      slotAfters[i]     = -1;
    }

    int howManySlots = 0;

/*
** We take advantage here of the design that tc.getCity() is working
** in modular coordinates, so our arithmetic here can be sloppy about
** array boundaries.
*/

/*
** Go forward looking for the end of a slot.
*/

    for ( int i = 0; i < genomeLength; i++ )
    {
      if
      (
        (  inList( tc.getCity( i     ), cityList ) )
        &&
        (! inList( tc.getCity( i + 1 ), cityList ) )
      )
      {
        slotEndings[howManySlots] = i;
        slotAfters[howManySlots]  = ( i + 1 ) % genomeLength;

/*
** Go backward from there looking for the beginning of the same slot.
*/

        for (int j = 0; j < genomeLength; j++)
        {
          if
          (
            (  inList( tc.getCity( i - j     ), cityList ) )
            &&
            (! inList( tc.getCity( i - j - 1 ), cityList ) )
          )
          {
            slotBeginnings[howManySlots] =
              ( i - j + genomeLength ) % genomeLength;
            slotBefores[howManySlots]    =
              ( i - j - 1 + genomeLength ) % genomeLength;
            break;
          }
        }
        howManySlots++;
      }
    }

    if (DB)
    {
      System.out.println ( "findSlots after finds for cityList:" );
      System.out.println ( "slotBefores    : " + Debugging.dump(slotBefores) );
      System.out.println ( "slotBeginnings : " + Debugging.dump(slotBeginnings) );
      System.out.println ( "slotEndings    : " + Debugging.dump(slotEndings) );
      System.out.println ( "slotAfters     : " + Debugging.dump(slotAfters) );
    }

/*
** Beelz, my brane hurts.  Try to merge in the cityEdges list while not
** creating new slots where old ones will do.
*/

    if ( cityEdges != null )
    {
      for ( int i = 0; i < cityEdges.length; i++ )
      {

        int startIs =  ( cityEdges[i].getStart() ).get();
        int stopIs  =  ( cityEdges[i].getEnd()   ).get();
        int startIsAt = tc.findCity( ( cityEdges[i].getStart() ).get() );
        int stopIsAt  = tc.findCity( ( cityEdges[i].getEnd()   ).get() );

/*
** If one end or the other of the selected edge is a city already
** selected, then that city will leave a slot when it is lifted for
** permuting, we don't need to create the slot again.  That's correct
** with regards to our intention here too; the city we are attempting to
** place on a nearby edge with remote ends  with this algorithm is
** surely not a city already at one end of the edge.
*/
        if
        (
          inList( startIs, cityList )
          ||
          inList( stopIs, cityList )
        )
        {
          if (DB)
          {
            System.out.println
            (
              "findSlots: edge "
              + cityEdges[i].toString()
              + " collided with an index in cityList "
              + Debugging.dump( cityList )
              + " via either of cites "
              + startIs
              + " / "
              + stopIs
            );
          }
          continue;
        }
        else
        {

          if (DB)
          {
            System.out.println
            (
              "findSlots: adding Edge derived slot between city names "
              + startIs
              + " / "
              + stopIs
            );
          }
/*
** Yeuk!  Now we have to cater for the Edge constructor possibly having
** reversed the Codons it contains to make them sorted by name.
*/

/*
** FIXED The current design assumes that there is a city _within_ a
** slot; for a selected edge, that won't work; bugger stuff around so
** that something feasible magically erupts.  Hmm.  Since neither
** slotBeginnings nor slotEndings are ever actually used anywhere, I can
** probably get away with assigning them bogus -1 values and putting the
** edge ends into the slotBefores and slotAfters arrays.
*/

//      int startIsAt = tc.findCity( ( cityEdges[i].getStart() ).get() );
//      int stopIsAt  = tc.findCity( ( cityEdges[i].getEnd()   ).get() );
//      int startIs =  ( cityEdges[i].getStart() ).get();
//      int stopIs  =  ( cityEdges[i].getEnd()   ).get();
          if
          (
            ( ( stopIsAt == 0 ) && ( startIsAt == ( genomeLength - 1 ) ) )
            ||
            ( ( stopIsAt - startIsAt ) == 1 )
          )
          {
            slotBefores[howManySlots]    = startIsAt;
            slotBeginnings[howManySlots] = -1;
            slotEndings[howManySlots]    = -1;
            slotAfters[howManySlots]     = stopIsAt;
          }
          else // reversed, so put them in the other way
          {
            slotBefores[howManySlots]    = stopIsAt;
            slotBeginnings[howManySlots] = -1;
            slotEndings[howManySlots]    = -1;
            slotAfters[howManySlots]     = startIsAt;
          }
          howManySlots++;
        }
      }
    }

/*
** We've merged the two arrays, but they need to be collated or horrible
** things happen, so do another cheesy sort.  Don't get fancy, just make
** it order N*N and be done with it.
*/

    for ( int i = 0; i < howManySlots; i++ )
    {
      for ( int j = 1; j < howManySlots; j++ )
      {
        if ( slotBefores[j] < slotBefores[j - 1] )
        {
          int slotBeforeTemp    = slotBefores[j];
          int slotBeginningTemp = slotBeginnings[j];
          int slotEndingTemp    = slotEndings[j];
          int slotAfterTemp     = slotAfters[j];
          slotBefores[j]        = slotBefores[j - 1];
          slotBeginnings[j]     = slotBeginnings[j - 1];
          slotEndings[j]        = slotEndings[j - 1];
          slotAfters[j]         = slotAfters[j - 1];
          slotBefores[j - 1]    = slotBeforeTemp;
          slotBeginnings[j - 1] = slotBeginningTemp;
          slotEndings[j - 1]    = slotEndingTemp;
          slotAfters[j - 1]     = slotAfterTemp;
        }
      }
    }

    if (DB)
    {
      System.out.println ( "findSlots after finds for cityEdges:" );
      System.out.println ( "slotBefores    : " + Debugging.dump(slotBefores) );
      System.out.println ( "slotBeginnings : " + Debugging.dump(slotBeginnings) );
      System.out.println ( "slotEndings    : " + Debugging.dump(slotEndings) );
      System.out.println ( "slotAfters     : " + Debugging.dump(slotAfters) );
    }

/*
** Produce arrays sized for the numbers actually found, so that the
** array lengths accurately define the count of their valid contents.
*/

    int slotPredecessors[] = new int[howManySlots];
    int slotStarts[]       = new int[howManySlots];
    int slotStops[]        = new int[howManySlots];
    int slotSuccessors[]   = new int[howManySlots];

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

    int slotList[][] =
      {
        slotPredecessors,
        slotStarts,
        slotStops,
        slotSuccessors,
      };

    return slotList;
  }

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

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

  private Edge [] pickEdges
  (
    TravellerChromosome tc,
    TravellerWorld world,
    int permuteSize,
    Coordinates nearnessPoint
  )
  {
    DoubleAndEdgeSortedOnDouble edges[] =
      new DoubleAndEdgeSortedOnDouble[permuteSize];

    for ( int i = 0; i < permuteSize; i++ )
    {
      edges[i] = null;
    }

    int genomeLength = world.getNumberOfCities();

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

    for ( int i = 0; i < genomeLength; i++ )
    {
      Codon startCity = tc.getCodon(i);
      Codon stopCity = tc.getCodon(i + 1); // trusting getCodon to wrap for us
      Coordinates startLine = new Coordinates( tc, i );
      Coordinates stopLine = new Coordinates( tc, (i + 1) );

      double complexReply[] =
        distanceFromAPointToALine( nearnessPoint, startLine, stopLine );

      // Unpack the complexReply array.
      double distance = complexReply[0];
      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 )
            {