best.c

人智算法基本程序

/****************************************************************/
/*    NAME: Smith Surasmith                                     */
/*    ACCT: sls                                                 */
/*   EMAIL: [e-mail]                                    */
/*    FILE: best.C                                              */
/*    ASGN: C++ code                                            */
/*    DATE: Wed Jun 22 13:44:22 1994                            */
/****************************************************************/

/*
 * Copyright 1994, Brown University, Providence, RI
 * See end of file for full copyright information
 */



#include <State.H>
#include <Searches.H>
#include <SortedQueue.H>



/****************************************************************/
/*                                                              */
/* Function Name: best                                          */
/* Parameters:    (State*) start state                          */
/*                (State*) goal state                           */
/*                (Comparator*) the comparator which will       */
/*                              allow the addition of the       */
/*                              new State into the list         */
/*                              should allow for the best       */
/*                              State to be the first in        */
/*                              the list.                       */
/* Returns:       (State*) 0 if failed                          */
/*                (State*) goal if succeeded                    */
/* Effects:       implements a heuristic search in which        */
/*                the "best" state is prioritized in the        */
/*                search                                        */
/*                                                              */
/*                added note: instead of a queue being used     */
/*                one could also implement a heap, which        */
/*                is more likely to be a more accurate          */
/*                application.                                  */
/*                                                              */
/****************************************************************/




State*
best(State* current,State* goal,Comparator* heuristic)
{
  SortedQueue<State,Comparator> search_list(heuristic);
  State* transition;

  if ((current == 0) || (goal == 0))
    return 0;

  for(;
      ((current != 0) 
       && (current->compare(goal) != (int) State::EQUAL));
      search_list.remove(current))
    {
      for(transition = current->makeTransition(); 
	  transition != 0;
	  transition = current->makeTransition())
	{
	  if (transition)
	    transition->mark();
	  search_list.insert(transition);
	}
    }
  return current;
}
	
  

/*
 * Copyright 1994, Brown University, Providence, RI
 *
 * Permission to use and modify this software and its documentation for
 * any purpose other than its incorporation into a commercial product is
 * hereby granted without fee.  Permission to copy and distribute this
 * software and its documentation only for non-commercial use is also
 * granted without fee, provided, however, that the above copyright notice
 * appear in all copies, that both that copyright notice and this permission
 * notice appear in supporting documentation, that the name of Brown
 * University not be used in advertising or publicity pertaining to
 * distribution of the software without specific, written prior permission,
 * and that the person doing the distribution notify Brown University of
 * such distributions outside of his or her organization. Brown University
 * makes no representations about the suitability of this software for
 * any purpose.  It is provided "as is" without express or implied warranty.
 * Brown University requests notification of any modifications to this
 * software or its documentation.
 *
 * Send the following redistribution information:
 *
 *	Name:
 *	Organization:
 *	Address (postal and/or electronic):
 *
 * To:
 *	Software Librarian
 *	Computer Science Department, Box 1910
 *	Brown University
 *	Providence, RI 02912
 *
 *		or
 *
 *	[e-mail]
 *
 * We will acknowledge all electronic notifications.
 */