travellerstatus.java

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

/*
** We figure out our estimated time at 500000000 flops or 500Mflops, a
** conservative laptop computer speed in 2002 AD.
*/

    BigInteger flopsOfEffort =
      permutations.multiply(cities).multiply(flopsPerCity);

    if
    (
      flopsOfEffort.compareTo
      (
        new BigInteger( String.valueOf( halfGigaFlop ) )
      )
      !=
      1
    )
    {
      result.append(" a second or less." );
      return result.toString();
    }


    BigInteger secondsOfEffort =
      flopsOfEffort.divide( new BigInteger( String.valueOf( halfGigaFlop ) ) );

/*
** A year is 365.25 days, or 365 days plus six hours.
*/

    BigInteger secondsInAYear = new
      BigInteger
      (
        String.valueOf
        (
          ( ( 365 * 24 ) + 6 ) * 60 * 60
        )
      );

    BigInteger secondsInADay = new
      BigInteger ( String.valueOf ( 24  * 60 * 60 ) );

    BigInteger secondsInAnHour = new
      BigInteger ( String.valueOf ( 60 * 60 ) );

    BigInteger secondsInAMinute = new
      BigInteger ( String.valueOf ( 60 ) );

    BigInteger wholeYearsToCompute =
      secondsOfEffort.divide( secondsInAYear );

    BigInteger leftoverSeconds =
      secondsOfEffort.subtract
      (
        secondsInAYear.multiply( wholeYearsToCompute )
      );

    BigInteger wholeDaysToCompute =
      leftoverSeconds.divide( secondsInADay );

    leftoverSeconds =
      leftoverSeconds.subtract
      (
        secondsInADay.multiply( wholeDaysToCompute )
      );

    BigInteger wholeHoursToCompute =
      leftoverSeconds.divide( secondsInAnHour );

    leftoverSeconds =
      leftoverSeconds.subtract
      (
        secondsInAnHour.multiply( wholeHoursToCompute )
      );

    BigInteger wholeMinutesToCompute =
      leftoverSeconds.divide( secondsInAMinute );

    leftoverSeconds =
      leftoverSeconds.subtract
      (
        secondsInAMinute.multiply( wholeMinutesToCompute )
      );

    BigInteger wholeSecondsToCompute = leftoverSeconds;

    if ( wholeYearsToCompute.compareTo( BigInteger.ZERO ) != 0 )
    {
      if ( wholeYearsToCompute.toString().length() > 4 )
      {
        String leadDigit = wholeYearsToCompute.toString().substring( 0 , 1 );
        String nextFour  = wholeYearsToCompute.toString().substring( 1 , 5 );
        result.append
        (
          leadDigit
          + "."
          + nextFour
          + "*10^"
          + String.valueOf(wholeYearsToCompute.toString().length() - 1)
          + " 年."
        );
        return result.toString();
      }
      result.append( wholeYearsToCompute.toString() + " years " );
      result.append( wholeDaysToCompute.toString()  + " days." );
      return result.toString();
    }

    if ( wholeDaysToCompute.compareTo( BigInteger.ZERO ) != 0 )
    {
      result.append( wholeDaysToCompute.toString() + " days " );
      result.append( wholeHoursToCompute.toString() + " hours." );
      return  result.toString();
    }

    if ( wholeHoursToCompute.compareTo( BigInteger.ZERO ) != 0 )
    {
      result.append( wholeHoursToCompute.toString() + " hours " );
      result.append( wholeMinutesToCompute.toString() + " minutes." );
      return  result.toString();
    }

    if ( wholeMinutesToCompute.compareTo( BigInteger.ZERO ) != 0 )
    {
      result.append( wholeMinutesToCompute.toString() + " minutes " );
      result.append( wholeSecondsToCompute.toString() + " seconds." );
      return  result.toString();
    }

    if ( wholeSecondsToCompute.compareTo( BigInteger.ZERO ) != 0 )
    {
      result.append( wholeSecondsToCompute.toString() + " seconds " );
    }

    return result.toString();
  }


  // task handlers

  public void cycleCompleted()
  {

    // handle time

    m_tod = new Date();
    m_timeCurrently = m_tod.getTime()/1000;

    // display generation

    showStatus();

    ++m_generationCurrently;

  }

  private void showStatus()
  {

    m_shortestPathCurrently = m_world.getShortestPath();
    m_averagePathCurrently = (long)m_world.getAveragePath();
    m_longestPathCurrently = (long)m_world.getLongestPath();
    String bf = null;
    boolean isDone = false;


/*
** Generation zero is a special setup generation that does no
** improvements or genetic algorithm running.  Handle that setup
** generation's special settings for instrumentation.
*/

    if (m_generationCurrently == 0)
    {
      m_shortestPathAtStart            = (long)m_shortestPathCurrently;
      m_shortestPathAtLastImprovement  =       m_shortestPathCurrently;
      m_shortestPathBestEver           =       m_shortestPathCurrently;
      m_shortestPathWorstEver          = (long)m_shortestPathCurrently;
      m_longestPathAtStart             =       m_longestPathCurrently;
      m_longestPathAtLastImprovement   =       m_longestPathCurrently;
      m_longestPathBestEver            =       m_longestPathCurrently;
      m_longestPathWorstEver           =       m_longestPathCurrently;
      m_averagePathAtStart             =       m_averagePathCurrently;
      m_averagePathBestEver            =       m_averagePathCurrently;
      m_averagePathWorstEver           =       m_averagePathCurrently;
      m_averagePathAtLastImprovement   =       m_averagePathCurrently;
      m_numberOfImprovementChanges     = 0;
      m_bf                             = bruteForce();
    }

    if (m_exactSolutionIsKnown)
    {
      if
      (
        Math.abs( m_shortestPathCurrently - m_exactSolution )
        <
        LITTLE_FUZZ
      )
      {
        isDone = true;
      }
    }

/*
** Avoid possible false change indications due to roundoff errors
** originating in different orders of evaluation of the path length by
** employing a tiny "fuzz" in the comparision.  If two successive paths
** which happen to be the last two found are really this close, live
** with it.
*/

    if
    (
      // Math.abs  -- probably not
      ( m_shortestPathBestEver - m_shortestPathCurrently )
      >
      LITTLE_FUZZ
    )
    {
      m_shortestPathAtLastImprovement  = m_shortestPathCurrently;
      m_averagePathAtLastImprovement   = m_averagePathCurrently;
      m_longestPathAtLastImprovement   = m_longestPathCurrently;
      m_generationAtLastImprovement    = m_generationCurrently;
      m_timeAtLastImprovement          = m_timeCurrently;
      m_numberOfImprovementChanges    += 1;
    }

    if ( m_shortestPathCurrently > m_shortestPathWorstEver )
    {
      m_shortestPathWorstEver = (long)m_shortestPathCurrently;
    }

    if ( m_shortestPathCurrently < m_shortestPathBestEver )
    {
      m_shortestPathBestEver = m_shortestPathCurrently;
    }

    if ( m_averagePathCurrently < m_averagePathBestEver )
    {
      m_averagePathBestEver = m_averagePathCurrently;
    }

    if ( m_averagePathCurrently > m_averagePathWorstEver )
    {
      m_averagePathWorstEver = m_averagePathCurrently;
    }

    if ( m_longestPathCurrently < m_longestPathBestEver )
    {
      m_longestPathBestEver = m_longestPathCurrently;
    }

    if ( m_longestPathCurrently > m_longestPathWorstEver )
    {
      m_longestPathWorstEver = m_longestPathCurrently;
    }

    StringBuffer status[] = new StringBuffer[STATUS_LINES_COUNT];
    for (int i = 0; i < STATUS_LINES_COUNT; i++)
    {
      status[i] = new StringBuffer();
      if (isDone) { status[i].append( "DONE! "); }
    }

    status[STATUS_CURRENT_ORIGIN]
      .append( "当前最佳基因组: " )
      .append( m_world.getBestGenomeOriginator() );

    status[STATUS_CURRENT_IMAGE]
      .append( "当前最佳基因组 ID: " )
      .append( m_world.getBestGenomeName() )
      .append( "; 克隆: " )
      .append( m_world.getBestGenomeCloneCount() )
      .append( "; 相同的适应度函数: " )
      .append( m_world.getSameFitnessCount() )
      ;

    status[STATUS_BRUTE_FORCE]
      .append( m_bf );

    status[STATUS_CHANGE_TITLE]
      .append
      ( "候选 --改进的 / 退火的 / 变异的 / 仔细考虑的" )
      ;

    accumulateTotalChangeCounts();

    status[STATUS_CHANGE_COUNTS]
      .append( "总体: " )
      .append( m_totalCandidatesImproved )
      .append( " / " )
      .append( m_totalCandidatesAnnealed )
      .append( " / " )
      .append( m_totalCandidatesMutated )
      .append( " / " )
      .append( m_totalCandidatesConsidered )
      .append( ", 上一代: " )
      .append( m_candidatesImproved )
      .append( " / " )
      .append( m_candidatesAnnealed )
      .append( " / " )
      .append( m_candidatesMutated )
      .append( " / " )
      .append( m_candidatesConsidered )
      ;

    clearChangeCounts();

    status[STATUS_LENGTHS_TITLE]
      .append( "长度 -- 最好 / 最新改进 /当前 / " )
      .append( "开始 /最坏" );

    status[STATUS_LENGTHS_SHORTEST]
      .append( "最短: ")
      .append( (long)m_shortestPathBestEver )
      .append( " / " )
      .append( (long)m_shortestPathAtLastImprovement )
      .append( " / " )
      .append( (long)m_shortestPathCurrently )
      .append( " / " )
      .append( m_shortestPathAtStart )
      .append( " / " )
      .append( m_shortestPathWorstEver );

    status[STATUS_LENGTHS_AVERAGE]
      .append( ": 平均")
      .append( m_averagePathBestEver )
      .append( " / " )
      .append( m_averagePathAtLastImprovement )
      .append( " / " )
      .append( m_averagePathCurrently )
      .append( " / " )
      .append( m_averagePathAtStart )
      .append( " / " )
      .append( m_averagePathWorstEver )
      .append( "; 领域边界, x/y: " )
      .append( (long)m_world.getWorldDimensions().width )
      .append( "/" )
      .append( (long)m_world.getWorldDimensions().height );

    status[STATUS_LENGTHS_LONGEST]
      .append( "最长: " )
      .append( m_longestPathBestEver )
      .append( " / " )
      .append( m_longestPathAtLastImprovement )
      .append( " / " )
      .append( m_longestPathCurrently )
      .append( " / " )
      .append( m_longestPathAtStart )
      .append( " / " )
      .append( m_longestPathWorstEver );

    status[STATUS_PERMUTATION]
      .append
      (
        " 改变: (极限::少量) 现在/最高::在一排/极限凸起 "
      )
      .append( PermutationController.getPermutationRuntimeInfo() );

    if ( m_exactSolutionIsKnown )
    {
      status[STATUS_LENGTHS_SHORTEST]
        .append( "; solved at: ")
        .append( (long)m_exactSolution );
    }

    if
    (
      CheckBoxControls.getState
      (
        CheckBoxControls.CBC_SEED_FROM_MINIMAL_SPANNING_TREE
      )
    )
    {
      status[STATUS_LENGTHS_SHORTEST]
        .append( "; MST floor " )
        .append( (long)MasterSeeder.getFloor() );
    }

    if ( CheckBoxControls.getState(CheckBoxControls.CBC_LAYOUT_CIRCULAR) )
    {
      status[STATUS_LENGTHS_LONGEST]
        .append( ";circle circumference: " )
        .append( (long)m_circumference );
    }

    status[STATUS_GENERATIONS]
      .append( "代数: 改进 / 现在 " )
      .append( m_generationAtLastImprovement )
      .append( " / " )
      .append( m_generationCurrently )
      .append( "; # 改进: " )
      .append( m_numberOfImprovementChanges );


    if
    (
      CheckBoxControls.getState
      (
        CheckBoxControls.CBC_METAHEURISTIC_ANNEALING
      )
    )
    {
      status[STATUS_ANNEALING]
        .append( "退火: 减流计: " )
        .append( m_world.getAnnealingDecrementer() )
        .append( " & 界限: " )
        .append( m_world.getAnnealingLimit() );
    }
    else
    {
      status[STATUS_ANNEALING]
        .append( "退火未激活" );
    }

    status[STATUS_TIMES]
      .append ( "测试所用时间（s）: 改进 / 现在 " )
      .append( (m_timeAtLastImprovement - m_timeAtStart) )
      .append( " / " )
      .append( (m_timeCurrently - m_timeAtStart) )
      .append( "; 安装所用时间（s）: " )
      .append
      (
        ( m_timeAtConfigurationFinished - m_timeAtConfigurationStart )
      );

    for ( int i = 0; i < STATUS_LINES_COUNT; i++ )
    {
      m_statusLines[i].setText( status[i].toString() );
    }

  }

}