btree.cpp

与遗传算法混合的模拟退火算法的应用

    if(n==NIL){ // i.e, mod_mf.x==0
      contour_root = mod;
      contour[mod].back = NIL;
    }
    else{
      contour[n].front = mod;
      contour[mod].back = n;
    }
  }
  
  int min_y = INT_MIN;
  int bx,by;
  assert(p!=NIL);
    
  for(; p!=NIL ; p=contour[p].front)
  {
    bx = modules_info[p].rx;
    by = modules_info[p].ry;
    min_y = max(min_y, by);
      
    if(bx >= mod_mf.rx){ 	// update contour
      mod_mf.y = min_y;
      mod_mf.ry = mod_mf.y + h;
      if(bx > mod_mf.rx){
        contour[mod].front = p;
        contour[p].back = mod;
      }else{ 			// bx==mod_mf.rx
        int n= contour[p].front;
        contour[mod].front = n;
        if(n!=NIL)
          contour[n].back = mod;
      }
      break;     
    }
  }

  if(p==NIL){
    mod_mf.y  = (min_y==INT_MIN? 0 : min_y);
    mod_mf.ry = mod_mf.y + h;
    contour[mod].front = NIL;
  }
}

//---------------------------------------------------------------------------
//   Manipulate B*Tree auxilary procedure
//---------------------------------------------------------------------------

void B_Tree::wire_nodes(int parent,int child,DIR edge){
  assert(parent!=NIL);
  (edge==LEFT? nodes[parent].left: nodes[parent].right) = child;
  if(child!=NIL) nodes[child].parent = nodes[parent].id;
}

int B_Tree::child(int node,DIR d){
  assert(node!=NIL);
  return (d==LEFT? nodes[node].left:nodes[node].right);  
}


//---------------------------------------------------------------------------
//   Simulated Annealing Temporal Solution
//---------------------------------------------------------------------------

void B_Tree::get_solution(Solution &sol){
  sol.nodes_root = nodes_root;
  sol.nodes = nodes;
  sol.cost = getCost();
}

void B_Tree::keep_sol(){
  get_solution(last_sol);
}

void B_Tree::keep_best(){
  get_solution(best_sol);
}

void B_Tree::recover(){
  recover(last_sol);
  // recover_partial();
}

void B_Tree::recover_best(){
  recover(best_sol);
}

void B_Tree::recover(Solution &sol){
  nodes_root = sol.nodes_root;
  nodes = sol.nodes;
}

void B_Tree::recover_partial(){
  if(changed_root != NIL)
    nodes_root = changed_root;
  
  for(int i=0; i < changed_nodes.size(); i++){
    Node &n = changed_nodes[i];
    nodes[n.id] = n;
  }
}

void B_Tree::add_changed_nodes(int n){
  if(n==NIL) return;

  for(int i=0; i < changed_nodes.size(); i++)
    if(changed_nodes[i].id == n)
	return;
  changed_nodes.push_back(nodes[n]);
}

//---------------------------------------------------------------------------
//   Simulated Annealing Permutation Operations
//---------------------------------------------------------------------------

void B_Tree::perturb(){
  int p,n;
  n = rand()%modules_N;

//  changed_nodes.clear();
//  changed_root = NIL;


  if(rotate_rate > rand_01()){
//    changed_nodes.push_back(nodes[n]);
    nodes[n].rotate = !nodes[n].rotate;
    if(rand_bool()) nodes[n].flip = !nodes[n].flip;
  }
  else{ 	

    if(swap_rate >rand_01()){
      do{
        p = rand()%modules_N;
      }while(n==p||nodes[n].parent==p||nodes[p].parent==n);

//      changed_nodes.push_back(nodes[p]);
//      changed_nodes.push_back(nodes[n]);

      swap_node(nodes[p],nodes[n]);

    }else{
      do{
        p = rand()%modules_N;
      }while(n==p);

//      changed_nodes.push_back(nodes[p]);
//      changed_nodes.push_back(nodes[n]);

      delete_node(nodes[n]);
      insert_node(nodes[p],nodes[n]);
    }
  }
}

void B_Tree::swap_node(Node &n1, Node &n2){

  if(n1.left!=NIL){  
    //add_changed_nodes(n1.left);
    nodes[n1.left].parent  = n2.id;
  }
  if(n1.right!=NIL){
    //add_changed_nodes(n1.right);
    nodes[n1.right].parent = n2.id;  
  }
  if(n2.left!=NIL){
    //add_changed_nodes(n2.left);
    nodes[n2.left].parent  = n1.id;
  }
  if(n2.right!=NIL){
    //add_changed_nodes(n2.right);
    nodes[n2.right].parent = n1.id;  
  }

  if(n1.parent != NIL){
    //add_changed_nodes(n1.parent);
    if(nodes[n1.parent].left==n1.id)
       nodes[n1.parent].left  = n2.id;
    else
       nodes[n1.parent].right = n2.id; 
  }else{
    changed_root = n1.id;
    nodes_root = n2.id;
  }

  if(n2.parent != NIL){
    //add_changed_nodes(n2.parent);
    if(nodes[n2.parent].left==n2.id)
       nodes[n2.parent].left  = n1.id;
    else
       nodes[n2.parent].right = n1.id; 
  }else{
//    changed_root = n2.id;
    nodes_root = n1.id;
  }

  swap(n1.left,n2.left);
  swap(n1.right,n2.right);
  swap(n1.parent,n2.parent);
}

void B_Tree::insert_node(Node &parent, Node &node){
  node.parent = parent.id;
  bool edge = rand_bool();

  if(edge){
    //add_changed_nodes(parent.left);
    node.left  = parent.left;
    node.right = NIL;
    if(parent.left!=NIL)
      nodes[parent.left].parent = node.id;

    parent.left = node.id;

  }else{
    //add_changed_nodes(parent.right);
    node.left  = NIL;
    node.right = parent.right;
    if(parent.right!=NIL)
      nodes[parent.right].parent = node.id;
    
    parent.right = node.id;
  }
}

void B_Tree::delete_node(Node &node){
  int child    = NIL;	// pull which child
  int subchild = NIL;   // child's subtree
  int subparent= NIL; 

  if(!node.isleaf()){
    bool left= rand_bool();			// choose a child to pull up
    if(node.left ==NIL) left=false;
    if(node.right==NIL) left=true;

    //add_changed_nodes(node.left);
    //add_changed_nodes(node.right);

    if(left){
      child = node.left;			// child will never be NIL
      if(node.right!=NIL){
        subchild  = nodes[child].right;
        subparent = node.right;
        nodes[node.right].parent = child; 
        nodes[child].right = node.right;	// abut with node's another child
      }
    }
    else{
      child = node.right;
      if(node.left!=NIL){
        subchild  = nodes[child].left;
        subparent = node.left;
	nodes[node.left].parent = child;
        nodes[child].left = node.left;
      }
    }
    //add_changed_nodes(subchild);
    nodes[child].parent = node.parent;
  }

  if(node.parent == NIL){			// root
//    changed_root = nodes_root;
    nodes_root = child;
  }else{					// let parent connect to child
    //add_changed_nodes(node.parent);
    if(node.id == nodes[node.parent].left)
      nodes[node.parent].left  = child;
    else
      nodes[node.parent].right = child;
  }

  // place subtree
  if(subchild != NIL){
    Node &sc = nodes[subchild];
    assert(subparent != NIL);

    while(1){
      Node &p = nodes[subparent];

      if(p.left==NIL || p.right==NIL){
        //add_changed_nodes(p.id);

	sc.parent = p.id;
        if(p.left==NIL) p.left = sc.id;
        else p.right = sc.id;
        break;
      }else{
	subparent = (rand_bool() ? p.left : p.right);
      }
    }
  }
}


bool B_Tree::delete_node2(Node &node,DIR pull){
  DIR npull = !pull;
 
  int p = node.parent;
  int n= node.id;
  int c= child(n,pull);
  int cn=child(n,npull);

  assert(n!= nodes_root); // not root;

  DIR p2c = (nodes[p].left==n ? LEFT:RIGHT);

  if(c==NIL){
    wire_nodes(p,cn,p2c);
    return (cn!=NIL);   // folding
  }else{
    wire_nodes(p,c,p2c);
  }

  while(c!=NIL){
    int k=child(c,npull);
    wire_nodes(c,cn ,npull);
    cn= k;
    n= c;
    c= child(c,pull);
  }

  if(cn != NIL){
    wire_nodes(n,cn,pull);
    return true;
  }else 
    return false;
}

/*
   Insert node into parent's left or right subtree according by "edge".
   Push node into parent's subtree in  "push" direction.

   if "fold" is true, then fold the leaf.
   (for the boundary condition of "delete" operation)

   delete <==> insert are permutating operations that can be recoved.
*/

void B_Tree::insert_node2(Node &parent,Node &node,
                        DIR edge=LEFT,DIR push=LEFT,bool fold=false){
  DIR npush = !push;
  int p= parent.id;
  int n= node.id;
  int c= child(p,edge);

  wire_nodes(p,n,edge);
  wire_nodes(n,c,push);
    
  while(c!=NIL){
    wire_nodes(n,child(c,npush) ,npush);
    n= c;
    c= child(c,push);
  }
  wire_nodes(n,NIL,npush);

  if(fold){
    wire_nodes(nodes[n].parent,NIL,push);
    wire_nodes(nodes[n].parent,n,npush); 
  }
}