minimalspanningtree.java

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

        if (DB) { System.out.println( "detaching treeNode/codonName" + currentTreeNode + "/" + currentCodonName );  }
        attached[currentTreeNode] = false;
        nodeRepeats[currentCodonName]--;
        nodesLeft--;

      if (DB)
      {
        System.out.println( "m_minimalSpanningTree after popped codon delete of greedily main while loop:\r\n" + Debugging.dump( m_minimalSpanningTree ) );
        System.out.println( "attached after popped codon delete of greedily main while loop:\r\n" + Debugging.dump( attached ) );
        System.out.println( "fitnessChange after popped codon delete of greedily main while loop:\r\n" + Debugging.dump( fitnessChange ) );
        System.out.println( "nodeRepeats after popped codon delete of greedily main while loop:\r\n" + Debugging.dump( nodeRepeats ) );
        System.out.println( "fitnessGains heap after popped codon delete of greedily main while loop:\r\n" + fitnessGains.toString() );
      }

/*
** Find four MST nodes we need to recompute and re-heapify fitness gains.
*/

        int predecessorTreeNode = currentTreeNode;

        while ( !attached[predecessorTreeNode] )
        {
          predecessorTreeNode =
            ( predecessorTreeNode - 1 + m_treeSize ) % m_treeSize ;
        }

        int predecessorsPredecessorTreeNode =
          ( predecessorTreeNode - 1 + m_treeSize ) % m_treeSize ;

        while ( !attached[predecessorsPredecessorTreeNode] )
        {
          predecessorsPredecessorTreeNode =
            ( predecessorsPredecessorTreeNode - 1 + m_treeSize ) % m_treeSize ;
        }

        int successorTreeNode = currentTreeNode;

        while ( !attached[successorTreeNode] )
        {
          successorTreeNode =
            ( successorTreeNode + 1 + m_treeSize ) % m_treeSize ;
        }

        int successorsSuccessorTreeNode =
          ( successorTreeNode + 1 ) % m_treeSize ;

        while ( !attached[successorsSuccessorTreeNode] )
        {
          successorsSuccessorTreeNode =
            ( successorsSuccessorTreeNode + 1 ) % m_treeSize ;
        }

/*
** Remove the superseded fitness gain indicators from the fitness gains
** heap, for the still attached points just before and behind the node
** we unattached, which had been using it to determine their fitness
** gains.
*/

        if ( nodeRepeats[ m_minimalSpanningTree[predecessorTreeNode] ] > 1 )
        {
          int scapegoat =
            fitnessGains.findByValue
            (
              (ContentComparable) fitnessChange[ predecessorTreeNode ]
            );

          fitnessGains.delete( scapegoat );

          fitnessChange[predecessorTreeNode] =
            new IntDoublePairSortedOnDouble
            (
              predecessorTreeNode,
              fitnessGained
              (
                predecessorsPredecessorTreeNode,
                predecessorTreeNode,
                successorTreeNode,
                world
              )
            );

          if (DB) { System.out.println( "pushing " + fitnessChange[predecessorTreeNode].toString() ); }
          fitnessGains.push( (ContentComparable) new IntDoublePairSortedOnDouble( fitnessChange[predecessorTreeNode] ) );

          if (DB)
          {
            System.out.println( "m_minimalSpanningTree after predecessor node delete and reinsert of greedily main while loop:\r\n" + Debugging.dump( m_minimalSpanningTree ) );
            System.out.println( "attached after predecessor node delete and reinsert of greedily main while loop:\r\n" + Debugging.dump( attached ) );
            System.out.println( "fitnessChange after predecessor node delete and reinsert of greedily main while loop:\r\n" + Debugging.dump( fitnessChange ) );
            System.out.println( "nodeRepeats after predecessor node delete and reinsert of greedily main while loop:\r\n" + Debugging.dump( nodeRepeats ) );
            System.out.println( "fitnessGains heap after predecessor node delete and reinsert of greedily main while loop:\r\n" + fitnessGains.toString() );
          }

        }

        if ( nodeRepeats[ m_minimalSpanningTree[successorTreeNode] ] > 1 )
        {
          int scapegoat =
            fitnessGains.findByValue
            (
              (ContentComparable) fitnessChange[ successorTreeNode ]
            );
          fitnessGains.delete( scapegoat );

          fitnessChange[successorTreeNode] =
            new IntDoublePairSortedOnDouble
            (
              successorTreeNode,
              fitnessGained
              (
                predecessorTreeNode,
                successorTreeNode,
                successorsSuccessorTreeNode,
                world
              )
            );

          if (DB) { System.out.println( "pushing " + fitnessChange[successorTreeNode].toString() ); }
          fitnessGains.push( (ContentComparable) new IntDoublePairSortedOnDouble( fitnessChange[successorTreeNode] ) );

          if (DB)
          {
            System.out.println( "m_minimalSpanningTree after successor node delete and reinsert of greedily main while loop:\r\n" + Debugging.dump( m_minimalSpanningTree ) );
            System.out.println( "attached after successor node delete and reinsert of greedily main while loop:\r\n" + Debugging.dump( attached ) );
            System.out.println( "fitnessChange after successor node delete and reinsert of greedily main while loop:\r\n" + Debugging.dump( fitnessChange ) );
            System.out.println( "nodeRepeats after successor node delete and reinsert of greedily main while loop:\r\n" + Debugging.dump( nodeRepeats ) );
            System.out.println( "fitnessGains heap after successor node delete and reinsert of greedily main while loop:\r\n" + fitnessGains.toString() );
          }
        }

      }

    }

    boolean isIn[] = new boolean[m_genomeLength];
    int dnl[]  = new int[m_genomeLength];
    for ( int i = 0; i < m_genomeLength; i++ )
    {
      isIn[i] = false;
      dnl[i] = -1;
    }

    int nodeCount = 0;

    for ( int i = 0; i < m_treeSize; i++ )
    {
      int codonName = m_minimalSpanningTree[i];
      if
      (
        ( attached[i] == true )
        &&
        ( isIn[ codonName ] == false )
      )
      {
        if ( nodeCount > m_genomeLength - 1 )
        {
          kablooie( "nodeCount too big in getBestDerivedNodeList()" );
        }
        else
        {
          isIn[ codonName ] = true;
          dnl[ nodeCount ] = codonName;
          nodeCount++;
        }
      }
    }

    if ( nodeCount != m_genomeLength )
    {
      kablooie( "wrong nodeCount in getBestDerivedNodeList()" );
    }

    m_mstCanvas.drawEdges
    (
      dnl,
      nodeCount,
      world.getCityDrawAtLocations(),
      world.CITY_X,
      world.CITY_Y,
      TravellerColors.COLOR_ALTERNATE_ROUTES,
      true // closed path
    );

    m_mstCanvas.drawEdges
    (
      m_minimalSpanningTree,
      m_treeSize,
      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();

    return dnl;

  }

  private double fitnessGained
  (
    int previousNode,
    int currentNode,
    int nextNode,
    TravellerWorld world
  )
  {
    return
      world.getDistance
      (
        m_minimalSpanningTree[previousNode],
        m_minimalSpanningTree[currentNode]
      )
      +
      world.getDistance
      (
        m_minimalSpanningTree[currentNode],
        m_minimalSpanningTree[nextNode]
      )
      -
      world.getDistance
      (
        m_minimalSpanningTree[previousNode],
        m_minimalSpanningTree[nextNode]
      )
      ;
  }

  public int [] getDerivedNodeList( TravellerWorld world )
  {
    int dnl[] = new int[m_genomeLength];
    boolean attached[] = new boolean[m_treeSize];

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

    // Start at some random spot; that's how we get differing chromosomes.
    // int index = m_mt.nextInt(m_treeSize);

    for ( int i = 0; i < m_genomeLength; i++ )
    {
      int index = m_mt.nextInt(m_treeSize);
      for ( int j = 0; j < m_treeSize; j++ )
      {
        int thisIndex = ( j + index ) % m_treeSize;
        if ( m_minimalSpanningTree[ thisIndex ] == i )
        {
          attached[ thisIndex ] = true;
          break;
        }
      }
    }

/*
** Display progress.
*/

    m_mstCanvas.drawEdges
    (
      m_minimalSpanningTree,
      m_treeSize,
      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();

    // m_mstCanvas.clearPlayfield();

    int nodesFilled = 0;
    for ( int j = 0; j < m_treeSize; j++ )
    {
      if ( attached[ j ] )
      {
        if ( nodesFilled >= m_genomeLength )
        {
          kablooie( "nodesFilled >= m_genomeLength" );
          break;
        }
        dnl[nodesFilled] = m_minimalSpanningTree[j];
        nodesFilled++;


/*
** Unfortunately, though drop dead gorgeous, this is unbearably slow for
** big problems.
** 
** FIXME Put in a "show detailed progress" checkbox so user can enable
** this.
*/

/*
        m_mstCanvas.drawEdges
        (
          dnl,
          nodesFilled,
          world.getCityDrawAtLocations(),
          world.CITY_X,
          world.CITY_Y,
          TravellerColors.COLOR_ROUTE,
          false // closed path
        );

        m_mstCanvas.drawImage();
*/
      }
    }

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

    m_mstCanvas.drawEdges
    (
      m_minimalSpanningTree,
      m_treeSize,
      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();

//    Debugging.snooze( VIEWING_DELAY );

    return dnl;
  }

  private void kablooie(String why)
  {
    System.out.println
    (
     "MinimalSpanningTree evoked kablooie()"
     + "\r\n"
     + "because "
     + why
    );
  }

}