minimalspanningtree.java

来自「经典的货郎担问题解决办法」· Java 代码 · 共 764 行 · 第 1/2 页

/*
** This code was written from scratch by Kent Paul Dolan, the greedy MST
** creation part from memory of published algorithms, probably due to
** Preparata and Shamos's _Computational Geometry_.  See accompanying
** file TravellerDoc.html for status for your use.
*/

package com.well.www.user.xanthian.java.seeders;

import com.coyotegulch.genetic.*;
import com.coyotegulch.tools.*;

import com.well.www.user.xanthian.java.structures.*;
import com.well.www.user.xanthian.java.tools.*;
import com.well.www.user.xanthian.java.ui.*;

public class MinimalSpanningTree
{

  private int         []  m_minimalSpanningTree = null;
  private int             m_genomeLength;
  private int             m_treeSize;
  private long            VIEWING_DELAY = 100;
  private static double   m_floor = Double.MAX_VALUE;
  private MersenneTwister m_mt = null;
  private TravellerCanvas m_mstCanvas = null;

/*
** FIXME This is trashy, MinimalSpanningTree has no business knowing
** about something as complex as a TravellerWorld, but to fix it requires
** ripping the city location information out of TravellerWorld and into
** a public class; live with it for now.
*/

  public MinimalSpanningTree( TravellerWorld world )
  {
    m_mt = MersenneTwister.getTwister();

    m_genomeLength           = ValuatorControls.getNumberOfCities();
    m_treeSize               = ( m_genomeLength * 2 ) - 2;
    m_minimalSpanningTree    = new int     [m_treeSize];
    m_mstCanvas              = new TravellerCanvas();
    boolean [] isIn          = new boolean [m_genomeLength];
    boolean [] attached      = new boolean [m_treeSize];
    int     [] nodeRepeats   = new int     [m_genomeLength];
    double  [] toNearest     = new double  [m_genomeLength];
    int     [] myNearest     = new int     [m_genomeLength];
    int       nodesFilled    = 0;
    double floor             = 0.0D;

    m_mstCanvas.setup( "Minimal Spanning Tree" );

    for (int i = 0; i < m_treeSize; i++)
    {
      m_minimalSpanningTree[i] = -1;
      attached[i]              = false;
    }

    for (int i = 0; i < m_genomeLength; i++)
    {
      isIn[i] = false;
      toNearest[i] = Double.MAX_VALUE;
      myNearest[i] = -1;
      nodeRepeats[i] = 0;
    }

/*
** Add the shortest possible edge, as the minimum which could possibly
** be added to an MST to make a circuit (in the circular layout case).
** Though, obviously this would not be the omitted edge, something at
** least the length of the Nth smallest would be.  [It's more
** complicated than _that_, too; lots of short edges could be crowded
** out by shorter ones that share a node.] FIXME LATER Hmmm.  Worth
** doing?  Maybe not.  A tighter floor would use this Nth smallest edge
** instead, I just don't want to sort a list of distances of length N*N,
** though maintaining a heap of length N shortest edges seen so far, and
** taking it would be doable.
*/

    m_floor = Double.MAX_VALUE;
    for (int i = 0; i < m_genomeLength; i++)
    {
      // Method world.getDistance() returns all off-diagonal lengths
      // twice, but we only need to look at them once, here, so
      // do a triangular walk to save effort.
      for (int j = 0; j <= i ; j++)
      {
        double temp = world.getDistance(i, j);
        if ( temp < m_floor ) { m_floor = temp; }
      }
    }

/*
** Seed the minimal spanning tree with a single node. It doesn't matter
** where we start, so start with node 0.
*/

    m_minimalSpanningTree[0] = 0;
    attached[0] = true;
    isIn[0] = true;
    nodeRepeats[0]++;
    nodesFilled++;

/*
** Display start state.
*/

    m_mstCanvas.redraw();

    m_mstCanvas.drawNodes
    (
      world.getCityDrawAtLocations(),
      ValuatorControls.getNumberOfCities(),
      world.CITY_X,
      world.CITY_Y,
      TravellerColors.COLOR_CITY
    );
    m_mstCanvas.drawImage();

    while ( nodesFilled < m_treeSize )
    {
      int    bestInnie   = -1;
      int    bestOutie   = -1;
      int    addAfter    = nodesFilled;
      double bestDistance = Double.MAX_VALUE;
      for (int i = (nodesFilled - 1); i >= 0; i--)
      {
        int currentNode = m_minimalSpanningTree[i];
        int otherNode   = myNearest[currentNode];
        double otherDistance = toNearest[currentNode];
        // Do we need to create or refresh a nearest neighbor entry?
        // This better be a lazy disjunctive, or we access outside array!
        if ( ( otherNode == -1 ) || isIn[ otherNode ] )
        {
          otherDistance = Double.MAX_VALUE;
          otherNode     = -1;
          for ( int j = 0; j < m_genomeLength; j++ )
          {
            if ( ( j != currentNode ) && ( ! isIn[j] ) )
            {
              // if ( distances[currentNode][j] < otherDistance )
              double temp = world.getDistance( currentNode, j );
              if ( temp < otherDistance )
              {
                otherDistance = temp;
                otherNode     = j;
              }
            }
          }
          // FIXME create an exception to throw so that we can
          // FIXME cater for algorithm failure here!
          if (otherNode == -1) { kablooie("otherNode == -1"); }
          myNearest[currentNode] = otherNode;
          toNearest[currentNode] = otherDistance;
        }
        if ( toNearest[currentNode] < bestDistance )
        {
          bestDistance = toNearest[currentNode];
          bestInnie = currentNode;
          bestOutie = otherNode;
          addAfter = i;
        }
      }

/*
** Roll data two slots toward end of MST array, to make room for two
** added nodes.
*/

      for ( int i = (nodesFilled - 1); i > addAfter; i-- )
      {

/*
** Special case the very last copy, so that we can avoid a redundant
** copy of node zero, and make the MST one element shorter.
*/

        if ( i + 2 < m_treeSize )
        {
          m_minimalSpanningTree[i + 2] = m_minimalSpanningTree[i];
          attached[i+2] = attached[i];
        }
      }
      // FIXME another place to check for failure!
      // bestInnie must equal m_minimalSpanningTree[addAfter];
      // The idea is to add an edge out to the new node
      // and then add an edge back to the connecting node,
      // to keep the graph tree-shaped, and so that the edge
      // to the former succeeding node is preserved.
      if (bestInnie != m_minimalSpanningTree[addAfter])
      { kablooie("bestInnie != m_minimalSpanningTree[addAfter]"); }
      m_minimalSpanningTree[addAfter + 1] = bestOutie;
      m_minimalSpanningTree[addAfter + 2] = bestInnie;
      isIn[ bestOutie ] = true;
      attached[addAfter + 1] = true;
      attached[addAfter + 2] = true;
      nodeRepeats[bestOutie]++;
      nodeRepeats[bestInnie]++;
      if ( nodesFilled + 2 < m_treeSize )
      {
        nodesFilled += 2;
      }
      else
      {
        nodesFilled += 1;
      }

/*
** Display progress.
*/

    m_mstCanvas.clearPlayfield();

    m_mstCanvas.drawEdges
    (
      m_minimalSpanningTree,
      nodesFilled,
      world.getCityDrawAtLocations(),
      world.CITY_X,
      world.CITY_Y,
      TravellerColors.COLOR_SEED_ROUTE,
      true // closed path
    );

    m_mstCanvas.drawNodes
    (
      world.getCityDrawAtLocations(),
      ValuatorControls.getNumberOfCities(),
      world.CITY_X,
      world.CITY_Y,
      TravellerColors.COLOR_CITY
    );

    m_mstCanvas.drawImage();

/*
** Add length of newly added edge to "mst length + shortest edge" floor
** value.
*/

      m_floor += bestDistance;
    }

    m_mstCanvas.clearPlayfield();
  }

  public void closeWindow()
  {
    if ( m_mstCanvas != null )
    {
      m_mstCanvas.windowClose();
      m_mstCanvas = null;
    }
  }

  public static double getFloor() { return m_floor; }

/*
** Implement a greedy deriver of a genome from the MST; greedy in the
** sense that it removes replicated codon names in order of the one
** currently providing the greatest improvement in fitness, until only a
** permutation genome's worth are left.  Maintaining the current
** removable-node fitness increments would be easy, if they were just
** kept in an array, but that would imply at least N*N performance,
** hopeless for the eventual problem size goals of Traveller.  At the
** cost of great code complexity and debugging time, instead I have
** implemented a Heap With Deletion, into which fitness improvement
** values and associated tag information can be pushed and from which
** the next node to remove can be popped.  The killer is that when a
** node is removed, the two nodes to which it was connected need their
** fitness increments revised, which means finding them wherever they
** may be in the heap, removing them from the heap, then pushing them
** back on the heap with revised fitness increment values.  Keeping all
** the pointers, counters, flags, and other foofooraw needed to do this,
** correct, is mind-bogglingly complex. Beelz, my brane hurts!
** 
** Since this algorithm has no randomness, it makes no particular sense
** to put more than one of these genomes in the Traveller population, so
** TravellerWorld caters by calling this routine for the only first
** MST-derived genome, and the non-greedy, partially random-driven,
** MST-derived genome generator twin to this function for the rest.
*/

  public int [] getGreedilyDerivedNodeList( TravellerWorld world )
  {
    boolean DB = false;
    if ( CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS) )
    {
      DB = true;
    }

    int nodeRepeats[] = new int[m_genomeLength];

    for ( int i = 0; i < m_genomeLength; i++ )
    {
      nodeRepeats[i] = 0;
    }

    boolean attached[] = new boolean[m_treeSize];

    for (int i = 0; i < m_treeSize; i++)
    {
      attached[i] = true;
      nodeRepeats[ m_minimalSpanningTree[i] ]++;
    }

/*
** Compute for each repeated node the gain if that repetition were
** removed.  Our intention always, of course, is to remove all but one
** of the MSTs repeated nodes to make a valid genome; here we try to
** remove all but the least useful-to-remove one.
*/

    HeapWithDelete fitnessGains =
      new HeapWithDelete( HeapWithDelete.POPS_LARGEST );

    IntDoublePairSortedOnDouble fitnessChange[] =
      new IntDoublePairSortedOnDouble[m_treeSize];

    for ( int i = 0; i < m_treeSize; i++ )
    {
      if ( nodeRepeats[m_minimalSpanningTree[i]] > 1 )
      {
        double fitnessToBeGained =
          fitnessGained
          (
            ( i - 1 + m_treeSize ) % m_treeSize,
            i,
            ( i + 1 ) % m_treeSize,
            world
          );
        fitnessChange[i] =
          new IntDoublePairSortedOnDouble( i, fitnessToBeGained );
        fitnessGains.push( (ContentComparable) new IntDoublePairSortedOnDouble( fitnessChange[i] ) );
      }
      else
      {
        fitnessChange[i] =
          new IntDoublePairSortedOnDouble( i, Double.MIN_VALUE );
        // and do _not_ push it on the heap.
      }
    }

    if (DB)
    {
      System.out.println( "m_minimalSpanningTree at start of greedily:\r\n" + Debugging.dump( m_minimalSpanningTree ) );
      System.out.println( "attached at start of greedily:\r\n" + Debugging.dump( attached ) );
      System.out.println( "fitnessChange at start of greedily:\r\n" + Debugging.dump( fitnessChange ) );
      System.out.println( "nodeRepeats at start of greedily:\r\n" + Debugging.dump( nodeRepeats ) );
    }

    int nodesLeft = m_treeSize;

    while ( nodesLeft > m_genomeLength && ( ! fitnessGains.isEmpty() ) )
    {

      if (DB)
      {
        System.out.println( "m_minimalSpanningTree at top of greedily main while loop:\r\n" + Debugging.dump( m_minimalSpanningTree ) );
        System.out.println( "attached at top of greedily main while loop:\r\n" + Debugging.dump( attached ) );
        System.out.println( "fitnessChange at top of greedily main while loop:\r\n" + Debugging.dump( fitnessChange ) );
        System.out.println( "nodeRepeats at top of greedily main while loop:\r\n" + Debugging.dump( nodeRepeats ) );
      }

      IntDoublePairSortedOnDouble pair =
        (IntDoublePairSortedOnDouble) fitnessGains.pop();

      if (DB) { System.out.println( pair.toString() + " popped to detach in greedily" ); }

      int currentTreeNode = pair.getInt();
      int currentCodonName = m_minimalSpanningTree[currentTreeNode];

      if ( nodeRepeats[currentCodonName] > 1 )
      {

/*
** We have a _lot_ of work to do here; mark the node unattached, do
** bookkeeping on the repeat and nodesLeft counts, and find this node's
** predecessor and successor nodes and redo their fitness gains and
** reinsert them in the fitness heap.
*/