HELP SEARCH Jocelyn Ireson-Paine October 1992 This module defines general routines for searching. They are very general: by changing the arguments, you can configure them to do depth-first, breadth-first, hill-climbing and many other types of search. To load it, do lib search; Introduction ------------ To understand how these routines are used, you have to know how the search is implemented. Each search routine maintain a "queue": a list of those points which have been marked for examination but not yet examined. The routine works in a cycle, thus: 1) Take the first element off the queue. If there is none, the search has failed: return false. Otherwise, this is the next point to be explored. 2) If this point is the goal, return true. 3) Find all the neighbours of this point, eliminating any which have already been explored. Add the others to the queue, making sure that if a neighbour is generated more than once, only one copy gets added. 4) Go back to 1. By altering the way that stage 3 adds neighbours to the queue, we can determine the type of search. For example, if each neighbour is added to the front of the queue, we get depth-first; the final neighbour added will be the first to be explored. If each neighbour is added to the end of the queue, we get breadth-first. If we sort the queue in order of estimated distance from the goal, so that the nearest point is the first to be explored, we get hill-climbing. This is explained in many references, for example in the chapter on Search in "Artificial Intelligence" by Winston. Those unfamiliar with the idea will find TEACH SEARCHING useful: note how the 'insert' procedure is used. Procedures exported ------------------- PUBLIC search( here, is_goal, next_from, insert ): The arguments are as follows: here : the initial point to search from. is_goal : a function is_goal(point) which returns true if point is a goal, and false otherwise. next_from : a function next_from(point) which returns a list of all the neighbours to be explored. insert : a function insert(point, queue) which inserts point into queue returning a new queue. 'search' searches for a goal point from 'here' as described above, returning true if it finds one and false otherwise. 'search' keeps track of the points which have already been visited, so as to avoid getting into loops. You can therefore safely use it for depth-first search, even if you suspect loops in the search tree. It also (as mentioned above) avoids adding the same neighbour to the queue more than once, if next_from returns several copies. However, for efficiency, it's as well to write a generator that doesn't do so. PUBLIC path_search( here, is_goal, next_from, insert ): 'path_search' is used when you want to know the path to the goal. If one can be found, it returns this as a list of points: the first element is 'here', the final one is the goal, and the others are the points in between. If one can't be found, it returns false. The arguments are the same as for 'search' with the exception of 'insert'. This is now a function insert( here, path, queue ) which returns a new queue. The queue is now a list of _lists_, each of the form [% point, path_to_point %] When examining an element, you must therefore get its head to get the point. When constructing the element for 'here', its second element must be 'path'. See the supplied insert functions below for examples. PUBLIC trace_search(): Turns on tracing. When this is on, the routines make the following calls in each cycle: printf('q %p\n', [%queue%] ) printf('here %p\n', [%here%] ) printf('neighbours %p\n', [%neighbours%] ) showing the queue, point being explored, and neighbours (result of next_from) respectively. PUBLIC untrace_search(): Turns off tracing. PUBLIC df_insert( point, q ): An insert routine for 'search' for implementing depth-first search. Defined as define df_insert( point, q ); lvars point, q; [ ^point ^^q ] enddefine; PUBLIC bf_insert( point, q ): An insert routine for 'search' for implementing breadth-first search. Defined as define bf_insert( point, q ); lvars point, q; [ ^^q ^point ] enddefine; PUBLIC eval_insert( point, q, eval ): An insert routine for 'search' for implementing evaluation-guided search. 'eval' is a function eval(point)->number which maps a point to an evaluation. The higher the evaluation, the better the point, so the further forward in the queue it will go. Defined as define eval_insert( point, q, eval ); lvars point, q, eval; if eval(point) > eval(hd(q)) then [ ^point ^^q ] else [ ^(hd(q)) ^^(eval_path_insert(point,tl(q),eval)) ] endif; enddefine; Note: this may evaluate the same point several times. If evaluation is expensive, store your evaluation in a property (or somewhere) and re-use it. PUBLIC df_path_insert( point, path, q ): An insert routine for 'path_search' for implementing depth-first search. Defined as define df_path_insert( point, path, q ): lvars point, path, q; [ [^point ^path] ^^q ] enddefine; PUBLIC bf_path_insert( point, path, q ): An insert routine for 'path_search' for implementing breadth-first search. Defined as define bf_path_insert( point, path, q ): lvars point, path, q; [ ^^q [^point ^path] ] enddefine; PUBLIC eval_path_insert( point, path, q, eval ): An insert routine for 'path_search' for implementing evaluation-guided search. 'eval' is a function eval(point)->number which maps a point to an evaluation. The higher the evaluation, the better the point, so the further forward in the queue it will go. Defined as define eval_path_insert( point, path, q, eval ); lvars point, path, q, eval; if eval(point) > eval(hd(hd(q))) then [ [^point ^path] ^^q ] else [ ^(hd(q)) ^^(eval_path_insert(point,path,tl(q),eval)) ] endif; enddefine;