backtrack.c

利用空间表示的rcc8模型进行空间推理

/***************************************************************************/
/***                                                                     ***/
/***                  backtrack.c (Version 1.0)                          ***/
/***                                                                     ***/
/***       Ronny Fehling, Bernhard Nebel, Jochen Renz  - March 1988      ***/
/***                                                                     ***/
/***         fehling, nebel, [e-mail]             ***/
/***                                                                     ***/
/***          http://www.informatik.uni-freiburg.de/~sppraum             ***/
/***                                                                     ***/
/***                      Institut fuer Informatik                       ***/
/***                     Albert-Ludwigs-Universitaet                     ***/
/***                           Am Flughafen 17                           ***/
/***                       79110 Freiburg, Germany                       ***/
/***                                                                     ***/
/***************************************************************************/


/*
  Heuristic for the choice of the next node while backtracking.
  The next node is the one with minimum value of splitinfo[r][0] and 
  maximum value of FVAL(splitinfo[r][1]) (i.e. minimal restricting) 
*/

#include "rcc8.h"
#include "rcc8op.h"

/* should be in stdlib.h ! */
long lrand48(void);

#define tempset(r,i,j)          17*(splitinfo[r][0]) + FVAL(r);  
#define tempenv(i,j)            10 * envcons(csp, maxnodeid, i,j)+temp;

/* extern switches */   
extern int swdebug;
extern int swcomppath;
extern int swverbose;
extern int swquite;
extern int swsummary;
extern int swbrief;
extern int swabrief;
extern int swpositive;
extern int swnegative;
extern int swposneg;
extern int swsplitinfo;
extern int swrandomorder;
extern int swwqueue;
extern int swenvcons;
extern int swfixed;
extern int swtimeout;
extern int swsolveonly;
extern int swonlypathcons;
extern int swmaxvisit;

/* extern statistical info */
extern unsigned int randomseed;
extern int maxnodeid;
extern char csptype[100];
extern int consistent;
extern int cntconsistent;
extern int pathconsistent;
extern int cntpathconsistent;
extern int pcops;
extern int pcits;
extern int nodesvisited;
extern int searchdepth;
extern int maxdepth;
extern double cputicks;
extern double cpumicro;
extern int trial;
extern int rectrial;
extern long int tpcops[MAXTRIAL];
extern long int tpcits[MAXTRIAL];
extern long int tnodesvisited[MAXTRIAL];
extern int tmaxdepth[MAXTRIAL];
extern double tcputicks[MAXTRIAL];
extern double cumcputicks;
extern double cumcpumicro;
extern int cntsize;
extern int size;

RELTYPE splitinfo[MAXSET][9];

#if defined(DYNAMIC)
extern RELTYPE **csp;
extern struct entry **entry;
extern char **mark;
extern int **consval;
extern int prevmax;
extern int path_cons(RELTYPE **csp,int maxnodeid, int node1, int node2);


#else 
extern RELTYPE csp[MAXCSP][MAXCSP];
extern struct entry entry[MAXWT][MAXCSP*MAXCSP];
extern char mark[MAXCSP][MAXCSP];
extern int consval[MAXCSP][MAXCSP];
extern int path_cons(RELTYPE csp[MAXCSP][MAXCSP],int maxnodeid, int node1, int node2);

#endif

extern void initrand(unsigned int seed);

/* compute the constrainedness of the environment of an edge */
int envcons(csp, maxnodeid, i, j)
     int    maxnodeid;
     register int i,j;
#if defined(DYNAMIC)
     RELTYPE   **csp;
#else 
     RELTYPE csp[MAXCSP][MAXCSP];
#endif
{
  register int k;
  register int w = 0;
  

  for (k = 0; k <= maxnodeid; k++) {
    if ((k != i) && (k != j)) {
      if (k < i) w += FVAL(csp[k][i]);
      else w += FVAL(FINV(csp[i][k]));
      if (k < j) w += FVAL(csp[k][j]);
      else w += FVAL(FINV(csp[j][k]));
    }
  }
  return(w);
}



/*
  check whether CSP is already solved,
  if so return 1,
  else return 0 and give a relation that can be split.
*/
int solved_csp(csp, maxnodeid, node1, node2)
     int    maxnodeid, *node1, *node2;
#if defined(DYNAMIC)
     RELTYPE   **csp;
#else
     RELTYPE csp[MAXCSP][MAXCSP];
#endif
{
  register int i,j;
  register int temp, minval;
  register RELTYPE r;
  int defaultval = DEFAULTVAL;

  minval = defaultval;
  *node1 = -1;
  *node2 = -1;
  for (i=0; i <= maxnodeid; i++)
    for (j=i+1; j <= maxnodeid; j++) {
      if (csp[j][i]) {
	r = csp[i][j];
	if (swsplitinfo) {
	  if (splitinfo[r][0] == 1) temp=0;
	  else 
	    temp = tempset(r,i,j);  
	} else {
	 
	  if ((r == DC) || (r == EC) || (r == PO) || (r == TPP) || 
	      (r == NTPP) || (r == TPPI) || (r == NTPPI) || (r == EQ) ||
	      (r ==DALL))
	    temp = 0; 
	  else temp =  (FVAL(r));
	}
	if (temp == 0)
	  csp[j][i] = 0;
	else
	  if (temp > 0) {
	    if (swfixed) temp = consval[i][j];
	    else if (swenvcons) temp = tempenv(i,j);
	    if ((temp < minval) && (temp > 0)) {
	      minval = temp;
	      *node1 = i;
	      *node2 = j;
	    }
	  }
      }
    }
  if (swdebug) {
    fprintf(stderr,"S(%d,%d->%d)  ",*node1,*node2,minval);
    fflush(stderr);
  }
  if (minval == defaultval) return(1);
  else 
    if (!swrandomorder || swfixed) return(0);
    else {
      if (randomseed == 0) 
	initrand(0);
      temp = abs(lrand48())%(maxnodeid*2);
      do {
	for (i=0; i <= maxnodeid; i++)
	  for (j=i+1; j <= maxnodeid; j++) 
	    if (csp[j][i]) 
	      if (--temp <= 0) {
		*node1 = i;
		*node2 = j;
		return(0);
	      }
      } while (1);
    }
}

/* compute initial cons values */
void init_consval(csp, maxnodeid)
     int    maxnodeid;
#if defined(DYNAMIC)
     RELTYPE   **csp;
#else 
     RELTYPE csp[MAXCSP][MAXCSP];
#endif
{
  register RELTYPE r;
  register int i,j, temp;

  for (i=0; i <= maxnodeid; i++)
    for (j=i+1; j <= maxnodeid; j++) {
	r = csp[i][j];
	if (swsplitinfo) {
	  if (splitinfo[r][0] == 1) temp=0;
	  else 
	     temp = tempset(r,i,j);
	} else {
	 
	  if ((r == DC) || (r == EC) || (r == PO) || (r == TPP) || 
	      (r == NTPP) || (r == TPPI) || (r == NTPPI) || (r == EQ) ||
	      (r ==DALL))
	    temp = 0;
	  else  temp = (FVAL(r));
	}
	if (temp <= 0) consval[i][j] = 0;
	else {
	  if (swenvcons) temp = tempenv(i,j);
	  if (swrandomorder) temp = abs(abs(lrand48())%(temp*100));
	  consval[i][j] = temp;
	}
      }
}


/* generate a "split" */
void gen_split(RELTYPE r, RELTYPE split[8])
{
  int i;
  
  if (swsplitinfo) {
    for (i=1;i<=8;i++) split[i-1] = splitinfo[r][i];
  
  } else {
    i = 0; 
    if (r & PO) split[i++] = PO;
    if (r & DC) split[i++] = DC;
    if (r & EC) split[i++] = EC;  
    if (r & TPP) split[i++] = TPP;   
    if (r & TPPI) split[i++] = TPPI;
    if (r & NTPP) split[i++] = NTPP;
    if (r & NTPPI) split[i++] = NTPPI;
    if (r & EQ) split[i++] = EQ;
    split[i] = 0;
  }
}

/* checks CSP for global consistency */
int global_cons(csp, maxnodeid, node1, node2)
     int    maxnodeid, node1, node2;
#if defined(DYNAMIC)
     RELTYPE   **csp;
#else 
     RELTYPE csp[MAXCSP][MAXCSP];
#endif
{
#if defined(DYNAMIC)
  RELTYPE   **newcsp;
#else 
  RELTYPE newcsp[MAXCSP][MAXCSP];
#endif 
  RELTYPE split[8];
  int splitnode1, splitnode2, s, cons=0;
  register int i,j;
  int node, cspsize=maxnodeid+1;

   
  nodesvisited++;
  node = nodesvisited;

  if (node > swmaxvisit) return(-1);
/*   if((node % NV_HEURISTIC_LIMIT) == 0) return(-1); */

  if((++searchdepth) > maxdepth) maxdepth++;

  if (swdebug) {
    fprintf(stderr,"D%1d(%d,%d:%d)  ",searchdepth,node1,node2,csp[abs(node1)][abs(node2)]);
    fflush(stderr);
  }

  

#if defined(DYNAMIC)
  newcsp = (RELTYPE **)malloc(cspsize*sizeof(RELTYPE *));
  newcsp[0] = (RELTYPE *)malloc(cspsize*cspsize*sizeof(RELTYPE));
  for(i=1;i<cspsize;i++)
    newcsp[i] = newcsp[0] + i * cspsize;
#endif


  if (node1 < 0) {
    for (i = 0; i <= maxnodeid; i++)
      for (j = i+1; j <= maxnodeid; j++) {
	newcsp[i][j] = csp[i][j];
	newcsp[j][i] = 1;
      } 
    if(!path_cons(newcsp,maxnodeid,node1,node2)) {
#if defined(DYNAMIC) 
      free((void *) newcsp[0]); free((void *) newcsp); 
#endif
      return(0);
    } 
    pathconsistent = 1;
    if (swonlypathcons) {
#if defined(DYNAMIC) 
      free((void *) newcsp[0]); free((void *) newcsp); 
#endif
      return(0);
    }
 

    if (swfixed) init_consval(newcsp,maxnodeid);
    /* mark all nodes that don't have to be split */ 
    if (solved_csp(newcsp,maxnodeid,&splitnode1,&splitnode2)) {
#if defined(DYNAMIC) 
      free((void *) newcsp[0]); free((void *) newcsp); 
#endif   
      return(1);
    }
  }
  else {
    for (i = 0; i <= maxnodeid; i++)
      for (j = 0; j <= maxnodeid; j++) {
	newcsp[i][j] = csp[i][j];
      }
    if (!path_cons(newcsp,maxnodeid,node1,node2)) {
      if (swdebug) {
	fprintf(stderr,"u%1d  ",searchdepth);
	fflush(stderr);
      }
      searchdepth--;
#if defined(DYNAMIC) 
      free((void *) newcsp[0]); free((void *) newcsp); 
#endif  
      return(0);
    }
    if (solved_csp(newcsp,maxnodeid,&splitnode1,&splitnode2)) {
      if (swdebug) {
	fprintf(stderr,"U%1d  ",searchdepth);
	fflush(stderr);
      }
      searchdepth--;
#if defined(DYNAMIC) 
      free((void *) newcsp[0]); free((void *) newcsp); 
#endif       
      return(1);
    } 
  }
  
  /* splitting */
  gen_split(newcsp[splitnode1][splitnode2],split);

  for (s = 0; s < 8; s++) {
    if (split[s] != 0) {
      newcsp[splitnode1][splitnode2] = split[s];
      cons=global_cons(newcsp,maxnodeid,splitnode1,splitnode2);
      if (cons==1) {
	if (swdebug) {
	  fprintf(stderr,"U%1d  ",searchdepth);
	  fflush(stderr);
	}
	searchdepth--; 
#if defined(DYNAMIC) 
      free((void *) newcsp[0]); free((void *) newcsp); 
#endif  
	return(1);
      }
      else if (cons == -1) {
	searchdepth--;
#if defined(DYNAMIC) 
	free((void *) newcsp[0]); free((void *) newcsp); 
#endif 
      return(-1);
      }
    } else break;
  }
  if (swdebug) {
    fprintf(stderr,"u%1d  ",searchdepth);
    fflush(stderr);
  }
  searchdepth--;
#if defined(DYNAMIC) 
      free((void *) newcsp[0]); free((void *) newcsp); 
#endif 
      if(cons == -1) return(-1);
      return(0);
}