search_plan.c

intel ipp4.1性能库的一些例子。

/*********************************************************************
 * File: search_plan.c
 * Description: contains the machinery necessary to search the graph
 *
 * Author: Joerg Hoffmann 1998
 *
 *********************************************************************/ 
/*********************************************************************
 * (C) Copyright 1998 Albert Ludwigs University Freiburg
 *     Institute of Computer Science
 *
 * All rights reserved. Use of this software is permitted for 
 * non-commercial research purposes, and it may be copied only 
 * for that use.  All copies must include this copyright message.
 * This software is made available AS IS, and neither the authors
 * nor the  Albert Ludwigs University Freiburg make any warranty
 * about the software or its performance. 
 *********************************************************************/
/*********************************************************************
 *
 * NOTE: the commentaries in this file are all in German, cause these are
 *       notes that I made for my own use while working on the search
 *       code, which is really terribly complicated.
 * 
 *       If you have problems understanding the code (like I do when I have
 *       a look at it now), contact me at:
 *       
 *       [e-mail]
 *
 *       and I'll be happy to answer your questions, if I can...
 *
 **********************************************************************/








#include "ipp.h"

#include "output.h"
#include "utilities.h"
#include "memory.h"

#include "search_plan.h"
#include "memoize.h"
#include "wave_front.h"








/**************************************************
 * SIMPLE HELPERS, SHOULD BE MACROS. OFTEN CALLED *
 **************************************************/









void DO_OP( int time, OpNode *op )

{

  int was_used;

  was_used = op->info_at[time-1]->is_used++;
  if ( !was_used && gnum_ops_at[time-1] == ARRAY_SIZE ) {
    printf( "\n\nipp: increase ARRAY_SIZE( preset value: %d )", ARRAY_SIZE );
    exit( 1 );
  }
  if ( !was_used ) {
    gops_at[time-1][gnum_ops_at[time-1]++] = op;
    gnum_of_actions_tried++;
    if ( op->is_noop ) {
      gnum_of_noops_tried++;
    }
  }

}



void UNDO_OP( int time, OpNode *op )

{

  int was_used;

  was_used = --op->info_at[time-1]->is_used;
  if( !was_used ) {
    gops_at[time-1][--gnum_ops_at[time-1]] = NULL;
  }

}



void DO_FT( int time, FtNode *ft, OpNode *op )

{

  int was_used;
  FtNode *neg_ft = ft->positive ? gft_table[NEG_ADR( ft->index )] :
    gft_table[ft->index];
    
  if ( !neg_ft || !neg_ft->info_at[time] ) {
    return;
  }

  was_used = ft->info_at[time]->is_goal++;

  if ( ( !was_used && gnum_goals_at[time] == ARRAY_SIZE ) ||
       ft->info_at[time]->is_goal > ARRAY_SIZE ) {
    printf( "\n\nipp: increase ARRAY_SIZE( preset value: %d )", ARRAY_SIZE );
    exit( 1 );
  }
  (ft->info_at[time]->is_goal_for)[ft->info_at[time]->is_goal-1] = op;
  if ( !was_used ) {
    ggoals_at[time][gnum_goals_at[time]++] = ft;
    if ( ft->positive ) {
      gpos_goals_vector_at[time][ft->uid_block] |= ft->uid_mask;
    } else {
      gneg_goals_vector_at[time][ft->uid_block] |= ft->uid_mask;
    }
  }

}



void UNDO_FT( int time, FtNode *ft )

{

  int was_used;
  FtNode *neg_ft = ft->positive ? gft_table[NEG_ADR( ft->index )] :
    gft_table[ft->index];
    
  if ( !neg_ft || !neg_ft->info_at[time] ) {
    return;
  }

  was_used = --ft->info_at[time]->is_goal;
  (ft->info_at[time]->is_goal_for)[ft->info_at[time]->is_goal] = NULL;
  if ( !was_used ) {
    ggoals_at[time][--gnum_goals_at[time]] = NULL;
    if ( ft->positive ) {
      gpos_goals_vector_at[time][ft->uid_block] &= ~(ft->uid_mask);
    } else {
      gneg_goals_vector_at[time][ft->uid_block] &= ~(ft->uid_mask);
    }
  }

}




FtNode *NEG_FT( FtNode *ft )

{

  return ( ft->positive ? gft_table[NEG_ADR( ft->index )] : gft_table[ft->index] );

}









/*********************
 * SETTING UP SEARCH *
 *********************/









Bool search_plan( int max_time )

{

  int i;
  Bool result;
  Integers *j;


  expand( max_time );


  /* achtung!! hier muss noch irgendwie die reihenfolge der ziele
   * in bezug auf definition im domain file beruecksichtigt werden
   */
  gnum_goals_at[max_time] = 0;
  for ( j = gbit_goal_state->positive->indices; j; j = j->next ) {
    DO_FT( max_time, gft_table[j->index], NULL );
  }
  for ( j = gbit_goal_state->negative->indices; j; j = j->next ) {
    DO_FT( max_time, gft_table[NEG_ADR( j->index )], NULL );
  }


  gnum_ops_at[max_time-1] = 0;
  gnum_goals_at[max_time-1] = 0;

  result = search( max_time, gnum_goals_at[max_time] - 1);

  for ( i=gnum_goals_at[max_time] - 1; i>-1; i-- ) {
    UNDO_FT( max_time, ggoals_at[max_time][i] );
  }

  if ( !result ) memoize( max_time );
                        
  return result;

}








/********************************
 * THE TWO MAIN SEARCH FUNCIONS *        
 ********************************/










Bool search( int time, int curr_index )

{

  EfEdge *ef_i;
  EfNode *ef;
  FtNode *ft;

  if ( time == 0 ) return TRUE;


  if ( curr_index < 0 ) {

    if ( !action_set_is_minimal( time ) ) {
      return FALSE;
    }

    return complete_goals_and_search( time );

  }


  while ( ( ft = ggoals_at[time][curr_index] )->info_at[time]->is_true ) {
    curr_index--;
    if ( curr_index < 0 ) {
      return search( time, -1 );
    }
  }


  if ( ft->noop ) {

    if ( try_noop( time, ft, curr_index ) ) {

      if ( search( time, curr_index - 1 ) ) {
	return TRUE;
      }     

      untry_noop( time, ft );
    }
  }


  for ( ef_i = ft->info_at[time]->adders_pointer; ef_i; ef_i = ef_i->next ) { 
    ef = ef_i->ef;

    if ( !try_ef( time, ef, curr_index ) ) {
      continue;
    }

    if ( search( time, curr_index - 1 ) ) {
      return TRUE;
    }
    

    untry_ef( time, ef );
  }

  return FALSE;

}






Bool complete_goals_and_search( int time )

{

  int i, j;
  OpNode *op;
  EfNode *i_ef;
  FtEdge *i_ft;
  FtNode *ft;

  for ( i = 0; i < gnum_ops_at[time-1]; i++ ) {
    op = gops_at[time-1][i];

    for ( i_ef = op->conditionals; i_ef; i_ef = i_ef->next ) {

      /* ALLE effekte, also auch dummys, werden auf schaedlichkeit
       * geprueft!!!
       */

      if ( i_ef->first_occurence > time-1 ) {
	/* erst soweit runterspulen, bis wir auf dem richtigen level sind...
	 * (zeiger op->conditionals zeigt auf letzten hinzugekommenen
	 * effekt...)
	 *
	 * ACHTUNG: INEFFIZIENT. koennte mit einfachen mitteln direkt
	 * drauf zugegriffen werden (op_level_info den korrekten anfang
	 * mitspeichern oder so...)
	 */
	continue;
      }

      if ( cant_do_conditions( time, i_ef ) ) {
	/* effekt hat onehin bedingungen, die nicht mit neuen zielen
	 * wahr sein koennen; also gar nicht erst auf schaedlichkeit
	 * pruefen.
	 *
	 * beachte: in exclusivitaet ist widerspruechlichkeit bereits
	 * enthalten, also werden hier bereits gewaehlte verhinderungs
	 * goals erkannt.
	 *
	 * ACHTUNG DUMMYS: dummy knoten haben zwar keine explizite exclusivitaet,
	 *                 solange sie noch nicht integriert sind,
	 *                 (PRINZIPIELL IST AUCH EIGENE BERECHNUNG DENKBAR), aber
	 *                 auf widerspruechlichkeit, also insbesondere effekt
	 *                 verhinderung wird hier reagiert, da auch dummy
	 *                 knoten automatisch exclusiv zu ihrer negation sind.
	 */
	continue;
      }

      for ( i_ft = i_ef->effects; i_ft; i_ft = i_ft->next ) {

	if ( (ft = NEG_FT( i_ft->ft )) == NULL ||
	     !ft->info_at[time] ) {
	  /* widersprechendes fact kann kein ziel sein, da (noch)
	   * nicht vorhanden auf step time
	   */
	  continue;
	}

        if ( !ft->info_at[time]->is_goal && 
	     !( ft->info_at[time-1] && ft->info_at[time-1]->is_goal ) ) {
	  /* widersprechendes fact kein ziel und 
	   * auf neuem step nicht da oder auch kein ziel
	   */
	  continue;
	}

	if ( !ft->info_at[time]->is_goal ) {
	  /* ist neues ziel: nur einschreiten, falls nicht ausschliesslich
	   * ziel fuer op selbst
	   */
	  for ( j=0; j<ft->info_at[time-1]->is_goal; j++ ) {
	    if ( (ft->info_at[time-1]->is_goal_for)[j] != op ) break;
	  }
	  if ( j == ft->info_at[time-1]->is_goal ) {
	    /* fact ist nur widerspruch zu op's eigenen effekten
	     */
	    continue;
	  }
	}

	/* wir muessen diesen effekt verhindern!!
	 *
	 * aus uebersichtlichkeitsgruenden sprung in die
	 * effekt schleife.
	 */
	break;
      }

      if ( !i_ft ) {
	/* haben kein schaedliches fact in diesem effekt
	 * gefunden! --> naechsten effekt pruefen.
	 */
	continue;
      }

      /* der reihe nach versuchen, die bedingungen zu 
       * verhindern
       */
      for ( i_ft = i_ef->conditions; i_ft; i_ft = i_ft->next ) {
	
	if ( i_ft->ft->info_at[time-1]->is_goal ) {
	  /* conditions sind auf time-1 garantiert da...
	   * ACHTUNG!!! wenns spaeter dummys gibt
	   *            > kein problem:(?) werden als knoten eingetragen.
	   *
	   * neue ziele koennen nicht verhindert werden.
	   */
	  continue;
	}
	
	if ( (ft = NEG_FT( i_ft->ft )) == NULL ||
	     !ft->info_at[time-1] ) {
	  /* widerspruchs fact, also verhinderung, (noch) nicht da
	   */
	  continue;
	}

	if ( cant_do_ft( time-1, ft ) ||
	     is_deleted( time-1, ft, op ) ) {
	  /* widerspruchsbedingung ist exklusiv zu ausgewaehlten
	   * zielen oder
	   * wird von ausgewaehltem op' != op zerstoert...
	   *
	   * hier auch moeglich: effekte als used markieren und
	   * bei zerstoerung beruecksichtigen!!
	   *
	   * ebenfalls moeglich: getriggerte effekte beruecksichtigen,
	   * solche werden aber spaeter im fixpunkt auch noch erkannt.
	   * effizienzfrage...??
	   */
	  continue;
	}

	/* HOPPLA: effekt bedingung koennte dummy gewesen sein.
	 *         wenn das aber der fall ist, dann ist die negation
	 *         WEGEN CWA schon da, also KEIN DUMMY. deshalb
	 *         werden hier wie gewuenscht nur nicht-dummys
	 *         als ziele eingesetzt!!
	 *
	 *       OHNE CWA NICHT KORREKT!!!!
	 */
	DO_FT( time-1, ft, op );
  
	if ( complete_goals_and_search( time ) ) {
	  return TRUE;
	}

	UNDO_FT( time-1, ft );
      }

      /* schaedlicher effekt kann hier nicht verhindert werden!
       */
      return FALSE;
    }
  }

  /* an dieser stelle sind alle ausgewaehlten ops auf nicht -
   * schaedlichkeit geprueft.
   *
   * suche fortsetzen.
   */

  /* hier nochmal minimalitaets check !! ??
   */
  if ( !action_set_is_minimal( time ) ) {
    return FALSE;
  }


  if ( memoized( time - 1 ) ) {
    return FALSE;
  }

  if ( time > 1 ) {
    gnum_ops_at[time-2] = 0;
    gnum_goals_at[time-2] = 0;
  }
	
  if ( search( time - 1, gnum_goals_at[time-1] - 1 ) ) {
    return TRUE;
  }

  memoize( time - 1 );

  if ( gsame_as_prev_flag && time == gfirst_full_time + 1 ) {
    add_candidate( time - 1 );
  }

  return FALSE;
      
}









/********************************
 * SOPHISTICATED SEARCH HELPERS *
 ********************************/








Bool action_set_is_minimal( int time )

{

  int i;
  Bool result = TRUE;
  EfNode *i_ef;
  FtEdge *i_ft;
  FtNode *neg_ft = NULL;

  /* zunaechst werden alle getriggerten effekte eingetragen.
   *
   * wie ueblich: INEFFIZIENT! besser waere es, explizit ausgewaehlte
   * effekte zu markieren, dann braucht man die nicht mehr anzuschauen.
   */
  for ( i = 0; i < gnum_ops_at[time-1]; i++ ) {
    for ( i_ef = gops_at[time-1][i]->conditionals; i_ef; i_ef = i_ef->next ) {
      if ( i_ef->first_occurence > time-1 ) {
	/* INEFFIZIENT: wie im complete - goals pattern waere es besser,
	 * direkt vom op auf die hier vorhandenen effekte zugreifen zu 
	 * koennen.
	 */
	continue;
      }
      for ( i_ft = i_ef->conditions; i_ft; i_ft = i_ft->next ) {
	neg_ft = i_ft->ft->positive ? gft_table[NEG_ADR( i_ft->ft->index )] :
	  gft_table[i_ft->ft->index];
	if ( neg_ft &&
	     neg_ft->info_at[time-1] &&
	     !i_ft->ft->info_at[time-1]->is_goal ) {
	  break;
	}
      }
      if ( !i_ft ) {
	for ( i_ft = i_ef->effects; i_ft; i_ft = i_ft->next ) {
	  i_ft->ft->info_at[time]->is_true++;
	}
      }
    }
  }

  /* wenn es einen op gibt, der kein einziges fact alleine addet, dann