crstrtgy.c

NASA 开发使用的一个专家系统

   /*******************************************************/
   /*      "C" Language Integrated Production System      */
   /*                                                     */
   /*             CLIPS Version 6.05  04/09/97            */
   /*                                                     */
   /*         CONFLICT RESOLUTION STRATEGY MODULE         */
   /*******************************************************/

/*************************************************************/
/* Purpose: Used to determine where a new activation is      */
/*   placed on the agenda based on the current conflict      */
/*   resolution strategy (depth, breadth, mea, lex,          */
/*   simplicity, or complexity). Also provides the           */
/*   set-strategy and get-strategy commands.                 */
/*                                                           */
/* Principal Programmer(s):                                  */
/*      Gary D. Riley                                        */
/*                                                           */
/* Contributing Programmer(s):                               */
/*                                                           */
/* Revision History:                                         */
/*                                                           */
/*************************************************************/

#define _CRSTRTGY_SOURCE_

#include <stdio.h>
#define _CLIPS_STDIO_
#include <string.h>

#include "setup.h"

#if DEFRULE_CONSTRUCT

#include "constant.h"
#include "pattern.h"
#include "reteutil.h"
#include "argacces.h"
#include "agenda.h"
#include "crstrtgy.h"

#define GetMatchingItem(x,i) (x->basis->binds[i].gm.theMatch->matchingItem)
   
/***************************************/
/* LOCAL INTERNAL FUNCTION DEFINITIONS */
/***************************************/

#if ANSI_COMPILER
   static ACTIVATION             *PlaceDepthActivation(ACTIVATION *,ACTIVATION *);
#if CONFLICT_RESOLUTION_STRATEGIES
   static ACTIVATION             *PlaceBreadthActivation(ACTIVATION *,ACTIVATION *);
   static ACTIVATION             *PlaceLEXActivation(ACTIVATION *,ACTIVATION *);
   static ACTIVATION             *PlaceMEAActivation(ACTIVATION *,ACTIVATION *);
   static ACTIVATION             *PlaceComplexityActivation(ACTIVATION *,ACTIVATION *);
   static ACTIVATION             *PlaceSimplicityActivation(ACTIVATION *,ACTIVATION *);
   static ACTIVATION             *PlaceRandomActivation(ACTIVATION *,ACTIVATION *);
   static struct partialMatch    *SortPartialMatch(struct partialMatch *);
   static int                     ComparePartialMatches(ACTIVATION *,ACTIVATION *);
   static char                   *GetStrategyName(int);
#endif
#else
   static ACTIVATION             *PlaceDepthActivation();
#if CONFLICT_RESOLUTION_STRATEGIES
   static ACTIVATION             *PlaceBreadthActivation();
   static ACTIVATION             *PlaceLEXActivation();
   static ACTIVATION             *PlaceMEAActivation();
   static ACTIVATION             *PlaceComplexityActivation();
   static ACTIVATION             *PlaceSimplicityActivation();
   static ACTIVATION             *PlaceRandomActivation();
   static struct partialMatch    *SortPartialMatch();
   static int                     ComparePartialMatches();
   static char                   *GetStrategyName();
#endif
#endif

/***************************************/
/* LOCAL INTERNAL VARIABLE DEFINITIONS */
/***************************************/

#if CONFLICT_RESOLUTION_STRATEGIES
   static int                  Strategy = DEFAULT_STRATEGY;
#endif

/******************************************************************/
/* PlaceActivation: Coordinates placement of an activation on the */
/*   Agenda based on the current conflict resolution strategy.    */
/******************************************************************/
globle VOID PlaceActivation(whichAgenda,newActivation)
  ACTIVATION **whichAgenda;
  ACTIVATION *newActivation;
  {
   ACTIVATION *placeAfter = NULL;

   /*================================================*/
   /* Set the flag which indicates that a change has */
   /* been made to the agenda.                       */
   /*================================================*/
   
   SetAgendaChanged(CLIPS_TRUE);

   /*=============================================*/
   /* Determine the location where the activation */
   /* should be placed in the agenda based on the */
   /* current conflict resolution strategy.       */
   /*==============================================*/

#if ! CONFLICT_RESOLUTION_STRATEGIES
   if (*whichAgenda != NULL) placeAfter = PlaceDepthActivation(*whichAgenda,newActivation);
#else
   if (*whichAgenda != NULL) switch (Strategy)
     {
      case DEPTH_STRATEGY:
        placeAfter = PlaceDepthActivation(*whichAgenda,newActivation);
        break;

      case BREADTH_STRATEGY:
        placeAfter = PlaceBreadthActivation(*whichAgenda,newActivation);
        break;

      case LEX_STRATEGY:
        placeAfter = PlaceLEXActivation(*whichAgenda,newActivation);
        break;

      case MEA_STRATEGY:
        placeAfter = PlaceMEAActivation(*whichAgenda,newActivation);
        break;

      case COMPLEXITY_STRATEGY:
        placeAfter = PlaceComplexityActivation(*whichAgenda,newActivation);
        break;

      case SIMPLICITY_STRATEGY:
        placeAfter = PlaceSimplicityActivation(*whichAgenda,newActivation);
        break;

      case RANDOM_STRATEGY:
        placeAfter = PlaceRandomActivation(*whichAgenda,newActivation);
        break;
     }
#endif

   /*==============================================================*/
   /* Place the activation at the appropriate place in the agenda. */
   /*==============================================================*/

   if (placeAfter == NULL) /* then place it at the beginning of then agenda. */
     {
      newActivation->next = *whichAgenda;
      *whichAgenda = newActivation;
      if (newActivation->next != NULL) newActivation->next->prev = newActivation;
     }
   else /* insert it in the agenda. */
     {
      newActivation->next = placeAfter->next;
      newActivation->prev = placeAfter;
      placeAfter->next = newActivation;
      if (newActivation->next != NULL)
        { newActivation->next->prev = newActivation; }
     }
  }

/*******************************************************************/
/* PlaceDepthActivation: Determines the location in the agenda     */
/*    where a new activation should be placed for the depth        */
/*    strategy. Returns a pointer to the activation after which    */
/*    the new activation should be placed (or NULL if the          */
/*    activation should be placed at the beginning of the agenda). */
/*******************************************************************/
static ACTIVATION *PlaceDepthActivation(actPtr,newActivation)
  ACTIVATION *actPtr;
  ACTIVATION *newActivation;
  {
   int salience;
   unsigned long timetag;
   ACTIVATION *lastAct;

   /*============================================*/
   /* Set up initial information for the search. */
   /*============================================*/

   salience = newActivation->salience;
   timetag = newActivation->timetag;
   lastAct = NULL;

   /*=========================================================*/
   /* Find the insertion point in the agenda. The activation  */
   /* is placed before activations of lower salience and      */
   /* after activations of higher salience. Among activations */
   /* of equal salience, the activation is placed before      */
   /* activations with an equal or lower timetag (yielding    */
   /* depth first traversal).                                 */
   /*=========================================================*/
   
   while (actPtr != NULL)
     {
      if (actPtr->salience > salience)
        {
         lastAct = actPtr;
         actPtr = actPtr->next;
        }
      else if (actPtr->salience < salience)
        { return(lastAct); }
      else if (timetag < actPtr->timetag)
        {
         lastAct = actPtr;
         actPtr = actPtr->next;
        }
      else
        { return(lastAct); }
     }

   /*===========================================*/
   /* Return the insertion point in the agenda. */
   /*===========================================*/
   
   return(lastAct);
  }

#if CONFLICT_RESOLUTION_STRATEGIES
/*******************************************************************/
/* PlaceBreadthActivation: Determines the location in the agenda   */
/*    where a new activation should be placed for the breadth      */
/*    strategy. Returns a pointer to the activation after which    */
/*    the new activation should be placed (or NULL if the          */
/*    activation should be placed at the beginning of the agenda). */
/*******************************************************************/
static ACTIVATION *PlaceBreadthActivation(actPtr,newActivation)
  ACTIVATION *actPtr;
  ACTIVATION *newActivation;
  {
   int salience;
   unsigned long timetag;
   ACTIVATION *lastAct;

   /*============================================*/
   /* Set up initial information for the search. */
   /*============================================*/

   salience = newActivation->salience;
   timetag = newActivation->timetag;
   lastAct = NULL;

   /*=========================================================*/
   /* Find the insertion point in the agenda. The activation  */
   /* is placed before activations of lower salience and      */
   /* after activations of higher salience. Among activations */
   /* of equal salience, the activation is placed after       */
   /* activations with a lessor timetag (yielding breadth     */
   /* first traversal).                                       */
   /*=========================================================*/

   while (actPtr != NULL)
     {
      if (actPtr->salience > salience)
        {
         lastAct = actPtr;
         actPtr = actPtr->next;
        }
      else if (actPtr->salience < salience)
        { return(lastAct); }
      else if (timetag > actPtr->timetag)
        {
         lastAct = actPtr;
         actPtr = actPtr->next;
        }
      else
       {  return(lastAct); }
     }

   /*===========================================*/
   /* Return the insertion point in the agenda. */
   /*===========================================*/
   
   return(lastAct);
  }

/*******************************************************************/
/* PlaceLEXActivation: Determines the location in the agenda       */
/*    where a new activation should be placed for the lex          */
/*    strategy. Returns a pointer to the activation after which    */
/*    the new activation should be placed (or NULL if the          */
/*    activation should be placed at the beginning of the agenda). */
/*******************************************************************/
static ACTIVATION *PlaceLEXActivation(actPtr,newActivation)
  ACTIVATION *actPtr;
  ACTIVATION *newActivation;
  {
   int salience;
   unsigned long timetag;
   ACTIVATION *lastAct;
   int flag;

   /*===============================================*/
   /* Sort the fact identifiers for the activation. */
   /*===============================================*/

   if (newActivation->sortedBasis == NULL)
     { newActivation->sortedBasis = SortPartialMatch(newActivation->basis); }

   /*============================================*/
   /* Set up initial information for the search. */
   /*============================================*/

   timetag = newActivation->timetag;
   salience = newActivation->salience;