travellerworld.java

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

      {
        for (int city2 = 0; city2 < m_numCities; ++city2)
        {
          double dX
            = Math.abs
              (
                m_cityExactLocations[city1][CITY_X] -
                m_cityExactLocations[city2][CITY_X]
              );
          double dY
            = Math.abs
              (
                m_cityExactLocations[city1][CITY_Y] -
                m_cityExactLocations[city2][CITY_Y]
              );

          // m_distances[city1][city2] = Math.sqrt(dX * dX + dY * dY);
          cityDistancesVA.putValue
          (
            Math.sqrt( ( dX * dX ) + ( dY * dY ) ),
            city1,
            city2
          );
        }
      }

    }
  }

  private void createDrawingLocationsForCites()
  {
      // Calculate corresponding drawing locations for exact locations
      // set above.
      for (int i = 0; i < m_numCities; ++i)
      {
          m_cityDrawAtLocations[i][CITY_X] =
           (int)Math.round(m_cityExactLocations[i][CITY_X]);
          m_cityDrawAtLocations[i][CITY_Y] =
            (int)Math.round(m_cityExactLocations[i][CITY_Y]);
      }
  }

  public double getDistance(int city1, int city2)
  {
      return cityDistancesVA.getValue(city1, city2);
  }

  public double[] getCityExactLocation(int cityIndex)
  {
    double value[] = new double[CITY_SIZE];
    value[CITY_X] = m_cityExactLocations[cityIndex][CITY_X];
    value[CITY_Y] = m_cityExactLocations[cityIndex][CITY_Y];
    return value;
  }

  public double[][] getCityExactLocations()
  {
    return m_cityExactLocations;
  }

  public int[][] getCityDrawAtLocations()
  {
    return m_cityDrawAtLocations;
  }

  public double getAnnealingDecrementer()
  {
    return m_population.getAnnealingDecrementer();
  }

  public double getAnnealingLimit()
  {
    if ( m_population == null )
    {
      return 0.0D;
    }
    else
    {
      return m_population.getAnnealingLimit();
    }
  }

  public Dimension getWorldDimensions()
  {
    return m_dim;
  }

  public int getNumberOfCities()
  {
    return m_numCities;
  }

  public int getPopulationSize()
  {
    return m_popSize;
  }

  public double getShortestPath()
  {
      if (m_population != null)
          return m_population.getBestFit();
      else
          return -1.0;
  }

  public double getAveragePath()
  {
      if (m_population != null)
          return m_population.getAverageFit();
      else
          return -1.0;
  }

  public double getLongestPath()
  {
      if (m_population != null)
          return m_population.getWorstFit();
      else
          return -1.0;
  }

  public int getBestGenomeName()
  {
      if (m_population != null)
        return m_population.getBestName();
      else
          return -1;
  }

  public String getBestGenomeOriginator()
  {
    if (m_bestChromosome == null)
    {
      return new String( "" );
    }
    else
    {
      return new String( m_bestChromosome.getOriginator() );
    }
  }

  public int getSameFitnessCount()
  {
    if (m_population != null)
    {
      return m_population.getSameFitnessCount();
    }
    else
    {
      return -1;
    }
  }

  public int getBestGenomeCloneCount()
  {
    if (m_population != null)
    {
      return m_population.getBestCloneCount();
    }
    else
    {
      return -1;
    }
  }

  public String dumpBestChromosome()
  {
    if ( m_bestChromosome == null )
    {
      return new String("not built yet");
    }
    else
    {
      return m_bestChromosome.toString();
    }
  }

  public double getMutationRate()
  {
    return m_mutationRate;
  }

  public void resetChromosomes()
  {

    if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
    {
      System.out.println
      (
        "Entered TravellerWorld.resetChromosomes()"
      );
    }

/*
** Create an initial population of chromosomes.
*/

    TravellerChromosome [] chromosomes
      = new TravellerChromosome [m_popSize];

/*
** Seed the genomes (Scott's chromosomes) according to the user's
** selection.
*/

    MasterSeeder.seedGenomes( chromosomes, this );

    for (int n = 0; n < m_popSize; ++n)
    {
//      if (CheckBoxControls.getState(CheckBoxControls.CBC_LAYOUT_CLOSED_PATH))
//      {
      chromosomes[n].canonicalize();
//      }
    }

//    TravellerChromosome.SetClosedPath
//      (CheckBoxControls.getState(CheckBoxControls.CBC_LAYOUT_CLOSED_PATH));

/*
** Create a new population from the parts we've constructed.
*/

    m_population
      = new
        Population
        (
          chromosomes,
          MasterReproducer.hookMutators(),
          MasterReproducer.hookReproducers(),
          m_mutationRate,
          true  // minimizing fitnesses
        );

/*
** Cater for splitting calls to Population to do just an
** evaluateGenomes() method call the first time we get tasked after
** creating a new population, so we can display statistics for the
** unmodified genome seeding.
*/

    m_firstTaskingCall = true;

  }

  public void taskHandler()
  {

    // update the population
    try
    {
      if ( m_firstTaskingCall )
      {
        m_firstTaskingCall = false;
        m_bestChromosome =
          (TravellerChromosome) m_population.evaluateGenomes();
      }
      else
      {
        m_bestChromosome =
          (TravellerChromosome)m_population.nextGeneration();
      }
    }
    catch (Exception ex)
    {

      if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
      {
        System.out.println
        (
          "in TravellerWorld.TaskHandler received exception from newGeneration"
        );
      }

    }

    // let other programs do their thing
    m_task.yield();

    // initialize the image
    m_routeCanvas.clearPlayfield();

/*
** Put the cities on the bottom, so they show when nothing else is drawn.
*/

    m_routeCanvas.drawNodes
    (
      m_cityDrawAtLocations,
      ValuatorControls.getNumberOfCities(),
      CITY_X,
      CITY_Y,
      TravellerColors.COLOR_CITY
    );

    // if requested, draw everyone's path.

    if 
    (
      CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_DRAW_ALL_ALWAYS)
      ||
      CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_DRAW_ALL_ONCE)
    )
    {
      for (int p = 0; p < m_popSize; p++)
      {
        TravellerChromosome current =
          (TravellerChromosome)(m_population.getMember(p));

        m_routeCanvas.drawEdges
        (
          current.getGenomeAsArray(),
          ValuatorControls.getNumberOfCities(),
          m_cityDrawAtLocations,
          CITY_X,
          CITY_Y,
          TravellerColors.COLOR_ALTERNATE_ROUTES,
          true // closed path
//          CheckBoxControls.getState(CheckBoxControls.CBC_LAYOUT_CLOSED_PATH)
        );

      }

/*
** In case we drew everything in response to a "draw all once", clear
** that checkbox controls flag.
*/

      if 
      (
        CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_DRAW_ALL_ONCE)
      )
      {
        CheckBoxControls.setState
        (
          CheckBoxControls.CBC_DEBUG_DRAW_ALL_ONCE,
          false
        );
      }
    }

    // now plot best chromosome's path

    m_routeCanvas.drawEdges
    (
      m_bestChromosome.getGenomeAsArray(),
      ValuatorControls.getNumberOfCities(),
      m_cityDrawAtLocations,
      CITY_X,
      CITY_Y,
      TravellerColors.COLOR_ROUTE,
      true // closed path
//      CheckBoxControls.getState(CheckBoxControls.CBC_LAYOUT_CLOSED_PATH)
    );

/*
** Put the cities on top, so that they can be seen when the screen is
** solid edges!
*/

    m_routeCanvas.drawNodes
    (
      m_cityDrawAtLocations,
      ValuatorControls.getNumberOfCities(),
      CITY_X,
      CITY_Y,
      TravellerColors.COLOR_CITY
    );

    // draw the image and we're done
    m_routeCanvas.drawImage();

  }

  // thread methods
  public static void start()
  {
      m_task.start();
  }

  public static void stop()
  {
      m_task.stop();
  }

  public static void addTaskListener(TaskListener listener)
  {
      m_task.addTaskListener(listener);
  }

}