new_perm.cpp

在任务级并行平台P2HP上开发的demo应用

            Average_Weight[ i ] = Weight[ i ] ;
            Number_Len[ i ] = 1 ;
            Best_Coordinate[ i ].x = Coordinate[ i ].x ;
            Best_Coordinate[ i ].y = Coordinate[ i ].y ;
            Best_Coordinate[ i ].z = Coordinate[ i ].z ;
           }
            for( i = 0 ; i < 2 * Num - Edge ; i ++ )
             for( j = 0 ; j < 2 * Num - Edge ; j ++ )
              for( k = 0 ; k < 2 * Num - Edge ; k ++ )
              Judgement[ i ][ j ][ k ] = 0 ;


           Judgement[ Num - 1 ][ Num - 1 ][ Num - 1 ] = 1 ;
           Judgement[ Num - 1 ][ Num - 1 ][ Num ] = 2 ;

           Num_Processed = 2 ;
           Cur_Energy = 0 ;      // 重新开始，势能为0
           New_Cur_Energy = 0 ;      // 重新开始，势能为0
           return ;
         }  // if
     } // while
  }



/*******************************************************
***                                                  ***
***               四、递归主函数部分                 ***
***                                                  ***
*******************************************************/
/*******************************************************
***                                                  ***
***               4.1 绘制当前构形                   ***
***                                                  ***
*******************************************************/

void Drawing( )
{
 int i , j ;
 int px, x , py, y , pz, z ;
 Form1->Edit3->Text = (double) New_Best_Energy ;
 Form1->Edit1->Text = (double) Best_Energy / Ehh ;
 Form1->Edit2->Text = (double)( clock() - Time_Start )/1000 ;;

 Form1->Image1->Canvas->Brush->Color = RGB(255,255,255);
 Form1->Image1->Canvas->Rectangle( 0, 0, 681, 601 );

 Converted_Coordinate[ 0 ][ 0 ] = Best_Coordinate[ 0 ].x ;
 Converted_Coordinate[ 0 ][ 1 ] = Best_Coordinate[ 0 ].y ;

 for( i = 1 ; i < Num ; i ++ )
   {
    px = Best_Coordinate[ i - 1 ].x ;
    py = Best_Coordinate[ i - 1 ].y ;
    pz = Best_Coordinate[ i - 1 ].z ;
    x  = Best_Coordinate[ i ].x ;
    y  = Best_Coordinate[ i ].y ;
    z  = Best_Coordinate[ i ].z ;
    Converted_Coordinate[ i ][ 0 ] = Converted_Coordinate[ i - 1 ][ 0 ] + ( x - px ) - 0.1 * ( z - pz ) ;
    Converted_Coordinate[ i ][ 1 ] = Converted_Coordinate[ i - 1 ][ 1 ] + 0.8 * ( y - py ) + 0.15 * ( z - pz ) ;
   }

  //将各个球依次画出来
  for( i = 0 ;i < Num; i ++ )
  {
   Form1->Image1->Canvas->MoveTo( ( 330 - Ratio * Num ) + (int)( Ratio * Converted_Coordinate[ i ][ 0 ] ),
                                ( 280 - Ratio * Num ) + (int)( Ratio* Converted_Coordinate[ i ][ 1 ] ) );
   if( Data[ i ] == 1 )
   {
    Form1->Image1->Canvas->Brush->Color = RGB(0,0,0);//RGB(0,140,255);
    Form1->Image1->Canvas->Ellipse(( 330 - Ratio * Num ) + (int)( Ratio * Converted_Coordinate[ i ][ 0 ] ) - 4,
                            ( 280 - Ratio * Num ) + (int)( Ratio * Converted_Coordinate[ i ][ 1 ] ) - 4,
                            ( 330 - Ratio * Num ) + (int)( Ratio* Converted_Coordinate[ i ][ 0 ] ) + 4,
                            ( 280 - Ratio * Num ) + (int)( Ratio* Converted_Coordinate[ i ][ 1 ] ) + 4 );
   }
   else //if( Data[ i ] == 0 )
    {
    Form1->Image1->Canvas->Brush->Color =  RGB(255,255,255);
    Form1->Image1->Canvas->Ellipse(( 330 - Ratio * Num ) + (int)( Ratio * Converted_Coordinate[ i ][ 0 ] ) - 4,
                           ( 280 - Ratio * Num ) + (int)( Ratio * Converted_Coordinate[ i ][ 1 ] ) - 4,
                           ( 330 - Ratio * Num ) + (int)( Ratio* Converted_Coordinate[ i ][ 0 ] ) + 4,
                           ( 280 - Ratio * Num ) + (int)( Ratio* Converted_Coordinate[ i ][ 1 ] ) + 4 );
    }
  }

    Form1->Image1->Canvas->Brush->Color =  RGB(250,250,250);
    for(j = 0; j < Num -1; j ++ )
     {
      Form1->Image1->Canvas->MoveTo( ( 330 - Ratio * Num ) + (int)( Ratio * Converted_Coordinate[ j ][ 0 ] ),
                             ( 280 - Ratio * Num ) + (int)( Ratio * Converted_Coordinate[ j ][ 1 ]  ) );
      Form1->Image1->Canvas->LineTo( ( 330 - Ratio * Num ) + (int)( Ratio * Converted_Coordinate[ j + 1 ][ 0 ] ) ,
                               ( 280 - Ratio * Num ) + (int)( Ratio * Converted_Coordinate[ j + 1 ][ 1 ] ) );
     }
   return ;

}


/*******************************************************
***                                                  ***
***               4.1 打印当前构形                   ***
***                                                  ***
*******************************************************/
void Print_Cur_Conformation( )
{
  register int i , j ;
  AnsiString PictureNam ;

  if( Cur_Energy > Best_Energy )
    Best_Energy = Cur_Energy ;
  if( ( New_Cur_Energy > New_Best_Energy ) )
   {
    New_Best_Energy = New_Cur_Energy ;
    for( j = 0 ;j < Num ; j ++ )
     {
      Best_Coordinate[ j ].x = Coordinate[ j ].x ;
      Best_Coordinate[ j ].y = Coordinate[ j ].y ;
      Best_Coordinate[ j ].z = Coordinate[ j ].z ;
     }
       Drawing( ) ;
      ShowMessage(" Continue  !!! ");
   }

    if( New_Cur_Energy >= Optimized_Energy )
     {
      Time_Consuming = clock() - Time_Start ;
      Outputing_Data( ) ;
     }
  return ;
  }

/*******************************************************
***                                                  ***
***               4.2  释放占据的位置                ***
***                                                  ***
*******************************************************/

void Release_Occupied( int energy, int hh )
{
 int x , y , z ;
 Num_Processed -- ;             // 先将已放木块数减1
 x = Coordinate[ Num_Processed ].x ;
 y = Coordinate[ Num_Processed ].y ;
 z = Coordinate[ Num_Processed ].z ;
 Judgement[ x ][ y ][ z ] = 0 ;
 New_Cur_Energy -=  energy ;
 Cur_Energy -= hh ;
 return ;
}

/*******************************************************
***                                                  ***
***               4.3  指定占据的位置                ***
***                                                  ***
*******************************************************/

void Designating_Operation( int operation , int e_incre, int hh_incre )
{
  int x , y , z, ex, ey, ez;           // 标记上一个点位置
  x =  Coordinate[ Num_Processed - 1 ].x ;
  y =  Coordinate[ Num_Processed - 1 ].y ;
  z =  Coordinate[ Num_Processed - 1 ].z ;
  ex = x + Base[ operation ][ 0 ] ;
  ey = y + Base[ operation ][ 1 ] ;
  ez = z + Base[ operation ][ 2 ] ;

  Judgement[ ex ][ ey ][ ez ] = Num_Processed + 1 ;
  Coordinate[ Num_Processed ].x = ex ;
  Coordinate[ Num_Processed ].y = ey ;
  Coordinate[ Num_Processed ].z = ez ;
  New_Cur_Energy +=  e_incre ;
  Cur_Energy += hh_incre ;
}


/*******************************************************
***                                                  ***
***               Func 4.3: 选择一个位置             ***
***                                                  ***
*******************************************************/
int Choosing_Operation( )
{
  int i;
  double operation;
  double Q_Sum[Vectors + 1 ];
  Q_Sum[ 0 ] = 0 ;
  for( i = 1 ; i < Vectors + 1  ; i ++ )
     Q_Sum[ i ] = Q_Sum[ i - 1 ] + Quality[ i - 1 ] / Total_Quality ;

  operation =(double)( rand( )%1000) / 1000 ;
                        // 产生一[0，1）随机数
  for( i = 1 ; i <= Vectors ; i ++ )
    if ( operation <= Q_Sum[ i ] && operation >= Q_Sum[ i - 1 ] ) // 选定第i个方向,作此动作
       return (i-1) ;
}


/*******************************************************
***                                                  ***
***               4.4  选出不同的位置                ***
***                                                  ***
*******************************************************/
//***************数组做为函数的参数时，应当是传址
void Selecting_Different_Directions( int direct[ Vectors ] )
{// 参数数组传回去选定的K_Copy个不同的方向，并且将这些方向
 // 随机地打乱，以便将来不要总是优先走一支
 int i , j ;
 int choose[ Vectors - 1  ] ;
 int flag[ Vectors ] ; //标记哪个动作已被选过了
 double quality[ Vectors ] ;
 double quality_sum[ Vectors ] ;
 double total_sum = 0 ;
 int select ;
 int k ;

   for ( i = 0 ; i < Vectors ; i ++ )
    {
     if( Quality[ i ] != 0 )
      {
       direct[ i ] = i ;
       flag[ i ] = 10 ; //此方向未被占据或未被使用过
      }
     else
      {
       direct[ i ] = -1 ;
       flag[ i ] = -10 ;
      }
    }

   //随机选K_Copy次。
   //   k = 0 ;
   for( j = 0 ; j < K_Copy ; j ++ )
     {
        select = rand( ) % Vectors;
       while( flag[ select ] == -10 )
        select = rand( ) % Vectors;
       choose[ j ] = select ;
       flag[ select ] = -10 ;
       // 总共K_Free个数，选其中K_Copy个。
     } // for
   for( i = 0 ; i < K_Copy ; i ++ )
    direct[ i ] = choose[ i ] ;
   return;
 }

/*******************************************************
***                                                  ***
***               Func 4.6: 总递归函数               ***
***                                                  ***
*******************************************************/

void Recursion_Process( )
{
  int e_incre, hh_incre ;              // 记录当前新增黑切点
  int i ;
  int direction ;
  int direct[ Vectors ] ;          // 选中K_Copy不同方向(乱序)
  int e_increase[ Vectors - 1  ] ;      // 各方向新增势能值。
  int hh_increase[ Vectors - 1  ] ;      // 新增黑切点

  Computing_Quality( ) ;     // 计算当前各参数的值

  if( K_Free == 0 )          // 走到死胡同则退出
     return ;

  if( Num_Processed == Num ) // 走到头则输出构型
   {
     Print_Cur_Conformation( ) ;
      return ;
    }

  Weight_Predict = Weight[ Num_Processed - 1 ] * Average_Quality * K_Free ;

  //***********关键的公式，以下几个是关键的内容***************
  Uper_Threshold = C * ( Average_Weight[ Num_Processed ] / Z0 )
                     * ( ( Number_Len[ Num_Processed ] ) / C0 ) 
                     * ( ( Number_Len[ Num_Processed ] ) / C0 ) ;

  Down_Threshold = Uper_Threshold * 0.0005 ;

  // 即不复制也不剪枝
  if ( ( Weight_Predict >=  Down_Threshold ) &&
       ( Weight_Predict <=  Uper_Threshold ) )
   {
     direction = Selecting_Operation( ) ;
     Weight[ Num_Processed ] = Weight[ Num_Processed - 1 ]
                             * pow(Exp1T , New_E_Increasement[ direction ] ) ;
     e_incre = New_E_Increasement[ direction ] ;
     hh_incre = E_Increasement[ direction ] ;
     Designating_Operation( direction, e_incre, hh_incre ) ;
     Average_Weight[ Num_Processed ] = ( Number_Len[ Num_Processed ] *
                                         Average_Weight[ Num_Processed ] +
                                         Weight[ Num_Processed ] )
                                      /( Number_Len[ Num_Processed ] + 1 ) ;
     Number_Len[ Num_Processed ] ++ ;
     Num_Processed ++ ;
     Recursion_Process( ) ;
     Release_Occupied( e_incre, hh_incre ) ;
   }

  // 以1/2概率减枝
  else if ( Weight_Predict <  Down_Threshold )
   {
     if ( (double)( rand( ) % 1000 ) / 1000 < 0.5 )
                               // 剪枝
        return ;
     else                      // 保留
     {
       direction = Selecting_Operation( ) ;
       Weight[ Num_Processed ] = Weight[ Num_Processed - 1 ]
                               * pow( Exp1T,  New_E_Increasement[ direction ] );
       e_incre = New_E_Increasement[ direction ] ;
       hh_incre = E_Increasement[ direction ] ;
       Designating_Operation( direction, e_incre, hh_incre ) ;
       Average_Weight[ Num_Processed ] = ( Number_Len[ Num_Processed ] *
                                           Average_Weight[ Num_Processed ] +
                                           Weight[ Num_Processed ] )
                                        /( Number_Len[ Num_Processed ] + 1 ) ;
       Number_Len[ Num_Processed ] ++ ;
       Num_Processed ++ ;
       Recursion_Process( ) ;
       Release_Occupied( e_incre, hh_incre) ;
      } // else
    } // else if

  // 选择K个不同位置进行复制
  else if ( Weight_Predict > Uper_Threshold )
   {
     if ( Weight_Predict / Uper_Threshold  >= Vectors )
          K_Copy = Vectors - 1 ;
     else
          K_Copy = (int)( ( Weight_Predict / Uper_Threshold ) ) + 1;

     if( K_Copy > K_Free )
          K_Copy = K_Free ;
     int  Kc = K_Copy ;

     Selecting_Different_Directions( direct );

    //先记录下来各动作好度及其新增势能值
     for ( i = 0 ; i < Kc ; i ++ )
       {
        hh_increase[ i ] = E_Increasement[ direct[ i ] ] ;
        e_increase[ i ] = New_E_Increasement[ direct[ i ] ] ;
       }

     // 这时已标记出所有选出的动作, 然后依次等概率选取其中一个，并标记出
     // 这一动作已做过。
      int flag ;
      for( i = 0 ; i < Kc ; i ++ )
      if( direct[ i ] != -1 )
      {
       flag = direct[ i ] ;
       e_incre = e_increase[ i ] ;
       hh_incre = hh_increase[ i ] ;
       Weight[ Num_Processed ] = Weight[ Num_Processed - 1 ] *
                                 pow( Exp1T , e_incre ) ;
       Designating_Operation( flag , e_incre , hh_incre) ;
       Average_Weight[ Num_Processed ] = ( Number_Len[ Num_Processed ] *
                                           Average_Weight[ Num_Processed ] +
                                           Weight[ Num_Processed ] )
                                          /( Number_Len[ Num_Processed ] + 1 ) ;
       Number_Len[ Num_Processed ] ++ ;
       Num_Processed ++ ;
       Recursion_Process( ) ;
       Release_Occupied( e_incre ,hh_incre ) ;
    //   Computing_Quality( ) ;
       } // if
    } // else if
 }



/*******************************************************
***                                                  ***
***                    五、主函数                    ***
*******************************************************/
int New_Perm( )
{
  int i ;
 // srand(Time_Start);
 // randomize();
  Recursion_Process( ) ;
  getch( );
  return 1;
}