btsearch.c

生成直角Steiner树的程序包

	while (p1 < endp) {
		tmp = *p1++;
		tmp -> tree_num = i++;
		tmp -> next	= NULL;
		*hookp = tmp;
		hookp = &(tmp -> next);
	}

	return (root);
}

#endif

/*
 * This routine handles the top-most level of the search.
 */

	static
	bool
perform_search (

struct sinfo *		sip,		/* IN - search/compatibility info */
bitmap_t *		smt_mask	/* OUT - solution */
)
{
int			nterms;
bitmap_t		omit;
bitmap_t		mask;
pnum_t			first_point;
struct cinfo *		cip;
int			t;
int *			tp1;
int *			endp;
bool			failed;

	cip = sip -> cip;

	/* Set up initial state of best solution so far... */
	sip -> best_length	= INF_DISTANCE;
	sip -> best_count	= 0;
	sip -> best_solution	= 0;
	sip -> found		= FALSE;

	sip -> terms_left [0] = cip -> initial_vert_mask [0];

	mask = sip -> terms_left [0];
	nterms = NBITSON (mask);

	sip -> compat [0]	= 0;
	sip -> incompat [0]	= 0;
	sip -> solution		= 0;

	/* Do the search once for each full-tree that contains the */
	/* starting point...					   */
	first_point = find_starting_point (cip);

	omit = 0;

	tp1	= cip -> term_trees [first_point];
	endp	= cip -> term_trees [first_point + 1];
	while (tp1 < endp) {
		t = *tp1++;

		/* Skip trees that are not part of this component... */
		if (NOT BITON (cip -> initial_edge_mask, t)) continue;

		sip -> solution |= (1 << t);

		sip -> terms_left [1] =
			sip -> terms_left [0] & ~(sip -> edge_vmasks [t]);

		sip -> compat [1] = sip -> cmasks [t];

		sip -> incompat [1] =   sip -> incmasks [t]
				      | omit
				      | ~ (cip -> initial_edge_mask [0]);

		search_recurse (sip,
				1,
				nterms - cip -> edge_size [t],
				cip -> cost [t]);

		sip -> solution &= ~(1 << t);
		omit |= (1 << t);
	}

	failed = NOT (sip -> found);

	smt_mask [0] = sip -> best_solution;

	return (failed);
}

/*
 * This routine allocates all of the search stacks needed.
 */

	static
	void
allocate_search_stacks (

struct sinfo *		sip		/* IN - search/compatibility info */
)
{
int		nedges;
int		n;
struct cinfo *	cip;

	cip	= sip -> cip;
	nedges	= cip -> num_edges;

	n = (nedges + 1);

	sip -> terms_left	= NEWA (n, bitmap_t);
	sip -> compat		= NEWA (n, bitmap_t);
	sip -> incompat		= NEWA (n, bitmap_t);
}

/*
 * This routine frees up the search stacks.
 */

	static
	void
free_search_stacks (

struct sinfo *		sip		/* IN - search info. */
)
{
	free ((char *) sip -> incompat);
	free ((char *) sip -> compat);
	free ((char *) sip -> terms_left);

	sip -> terms_left	= NULL;
	sip -> compat		= NULL;
	sip -> incompat		= NULL;
}

/*
 * This routine selects a single terminal to use as a starting point in
 * the search.  We choose a point that is a member of the least number
 * of full-sets.
 */

	static
	pnum_t
find_starting_point (

struct cinfo *		cip		/* IN - compatibility info */
)
{
int			i;
int			j;
int			nverts;
int			nedges;
int			cnt;
int			fewest;
pnum_t			starting;
int *			vp1;
int *			vp2;
int32u			counts [MAX_TERMINALS];

	nverts = cip -> num_verts;
	nedges = cip -> num_edges;

	(void) memset (counts, 0, nverts * sizeof (counts [0]));

	for (i = 0; i < nedges; i++) {
		if (NOT BITON (cip -> initial_edge_mask, i)) continue;

		vp1 = cip -> edge [i];
		vp2 = cip -> edge [i + 1];
		while (vp1 < vp2) {
			j = *vp1++;
			++(counts [j]);
		}
	}

	starting = -1;
	fewest	 = INT_MAX;
	for (i = 0; i < nverts; i++) {
		cnt = counts [i];
		if (cnt <= 0) {
			/* Ignore terminals that are not part	*/
			/* of this sub-problem...		*/
		}
		else if (cnt < fewest) {
			starting = i;
			fewest = cnt;
		}
	}

	if (starting < 0) {
		fatal ("find_starting_point: Bug 1.");
	}

	return (starting);
}

/*
 * This routine performs the recursive portion of the backtrack search.
 */

	static
	void
search_recurse (

struct sinfo *	sip,		/* IN/OUT - search/compatibility info */
int		level,		/* IN - recursion level */
int		nleft,		/* IN - number of terminals left to connect */
dist_t		length		/* IN - length of current partial soln */
)
{
int			k;
bitmap_t *		terms_left;
bitmap_t *		compat;
bitmap_t *		incompat;
bitmap_t		omit;
bitmap_t		mask;
int			i1;
bitmap_t		word;
int			bitno;
int8u *			p1;
int8u *			p2;
int			byte;
dist_t			budget;
struct cinfo *		cip;

	if (length >= sip -> best_length) {
		/* Current partial solution is already too long	*/
		/* to ever become the best seen so far...	*/
		return;
	}

	cip = sip -> cip;

	if (nleft <= 0) {
		if (nleft < 0) {
			fatal ("search_recurse: Bug 1.");
		}

		/* All terminals have been connected!  We have	*/
		/* a new BEST solution!  Save it off.		*/

		sip -> best_solution = sip -> solution;
		sip -> best_length	= length;
		sip -> found		= TRUE;
		return;
	}

	if ((nleft >= 10) AND
	    find_inaccessible_terminal (sip, level)) {
		/* There is a terminal still be be hooked up such that	*/
		/* none of its full-trees is compatible with the	*/
		/* current partial solution!  Early cutoff!		*/
		return;
	}

	terms_left	= &(sip -> terms_left [level]);

	compat		= &(sip -> compat [level]);
	incompat	= &(sip -> incompat [level]);

#if 0 /* Disabled so that we don't need to sort the edges. */

	/* Do the length/n ratio cutoff test -- if none of the feasible	*/
	/* pieces has a length/n ratio that beats budget/nleft, then	*/
	/* there is now way to get a better solution!			*/
	if ((nleft >= 4) AND (sip -> best_length < INF_DISTANCE)) {

		/* Compute the "length budget" with which we must	*/
		/* connect all remaining points...			*/
		budget = sip -> best_length - length;

		if (nleft <= 0) goto no_ratio_cutoff;

		/* Find piece with the lowest length/terms ratio that	*/
		/* is not incompatible with current partial solution...	*/
		word = ~(incompat [0]);
		bitno = 0;
		byte = 0;
		if (word NE 0) {
			do {
				byte = (word & 0xFF);
				if (byte NE 0) break;
				bitno += 8;
				word >>= 8;
			} while (word NE 0);
		}
		if (byte NE 0) {
			k = bitno + one_bits_in_byte [byte] [0];
			if (k < cip -> num_edges) {
				fsp = cip -> full_trees [k];
				if ((cip -> cost [k] * nleft) >=
				    (budget * (cip -> edge_size [k] - 1))) {
					/* Even the piece with the best	*/
					/* length/n ratio does not beat	*/
					/* whats required for a better	*/
					/* solution...  Cutoff!		*/
#if 0
					tracef ("%% RATIO CUTOFF!\n");
#endif
					return;
				}
			}
		}
		no_ratio_cutoff:	;
	}
#endif

	/* Determine the set of trees we will try to add to the	*/
	/* partial solution.					*/

	word = compat [0] & ~incompat [0];

	omit = 0;

	/* Loop over each feasible full-tree. */

	for (bitno = 0; word NE 0; bitno += 8, word >>= 8) {
		byte = (word & 0xFF);
		if (byte EQ 0) continue;
		p1 = one_bits_in_byte [byte];
		p2 = one_bits_in_byte [byte + 1];
		while (p1 < p2) {
			k = bitno + *p1++;
			/* Full-set K is feasible.  Test to see	*/
			/* if it is truly compatible...		*/

			mask = sip -> edge_vmasks [k] & ~terms_left [0];
			i1 = NBITSON (mask);
			if (i1 NE 1) continue;

			/* Tree K intersects the current partial */
			/* solution at exactly one point!	 */

			compat [1] = compat [0] | sip -> cmasks [k];

			incompat [1] =	  incompat [0]
					| sip -> incmasks [k]
					| omit;

			terms_left [1] =
				terms_left [0] & ~ sip -> edge_vmasks [k];

			sip -> solution |= (1 << k);

			search_recurse (sip,
					level + 1,
					nleft - cip -> edge_size [k] + 1,
					length + cip -> cost [k]);

			sip -> solution &= ~(1 << k);
			omit |= (1 << k);
		}
	}
}

/*
 * This routine checks the given node level to see if there are any
 * inaccessible terminals.
 */

	static
	bool
find_inaccessible_terminal (

struct sinfo *	sip,		/* IN - search/compatibility info */
int		level		/* IN - recursion level */
)
{
int		t;
int		bitno;
int		byte;
bitmap_t	cur_incompat;
bitmap_t	word;
bitmap_t	mask;
int8u *		p1;
int8u *		p2;
struct cinfo *	cip;

	cip = sip -> cip;

	cur_incompat = sip -> incompat [level];

	word = sip -> terms_left [level];

	for (bitno = 0; word NE 0; bitno += 8, word >>= 8) {
		byte = (word & 0xFF);
		if (byte EQ 0) continue;

		p1 = one_bits_in_byte [byte];
		p2 = one_bits_in_byte [byte + 1];
		while (p1 < p2) {
			t = bitno + *p1++;

			mask = sip -> vert_emasks [t];
			if (mask EQ (mask & cur_incompat)) {
				/* EVERY edge containing T has been	*/
				/* found to be incompatible with >= 1	*/
				/* edge in the current partial tree	*/
				/* solution!				*/
				return (TRUE);
			}
		}
	}

	return (FALSE);
}