Programmer 7500

home *** CD-ROM | disk | FTP | other *** search

/ Programmer 7500 / MAX_PROGRAMMERS.iso / CLIPPER / MISC / BM_STAR.ZIP / STAR.DOC < prev next >

Wrap

Text File | 1992-07-26 | 22.3 KB | 567 lines

25jun91/bm -Contents- ... Generation of Test Data ... Linked List Structures for DFID ... On TeamWork ... Comparision of Dfid and A_Star ... The DFID Test Program ... Results of DFID Test Program ... The A* Test Program ... Statistics ... Program Listings -Generation of Test Data- Fifteen Puzzle Problem This traditional puzzle has 15 sliding blocks labeled as 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 and blank. But these labels, some with one symbol, some with two, are akward for a computer program. Any sensible arrangement of unique symbols will do so we choose the following goal: 1 2 3 4 5 6 7 8 9 A B C D E F - This means the test data can be input and manipulated in character string form, say "123-56749ab8dEfc". Note that this puzzle really has sixteen elements. Since the "blank" changes position, there are 16! puzzle permutations. A compiled C program using the compact memory model which has multiple data segments, could only support 9420 puzzles. Puzzles created at random are unlikely to fall into such a small state space. The puzzles provided in the handouts do not have a "hardness" quotient so are not a guide for algorithm correctness. There is a simple way to produce a large number of test puzzles for this project. Do an unconditional Breadth- First Search starting with the goal configuration and expanding until machine memory is full. This will produce thousands of puzzles which can be written in string form to a test file. Append the "Gn" value to the puzzle string as an indication of solvability. Example: Dfid 1-2356749AB8DEFC ** Level_5 ** Astar 13645A-29B87DEFC ** Level_13 ** If a problem puzzle happens to fit in the above state- space mapping, then it's solvability is predictable. For example, Dfid solves a level_12 puzzle by searching down six levels and up six levels. Level_13 requires six down and seven up. Admissable algorithms such as A-star should provide a solution path equal to the known puzzle depth. The number of puzzles at each level of the above state- space mapping can be easily counted. For example, there are 3584 puzzles at level_12 and more than 4000 at thirteen when the machine memory becomes full. Yet Dfid generates only 1092 puzzles for a level_12 problem. This indicates the space economy of bidirectional algorithms and implies solvability for problems outside the test domain. The reader may generate and examine puzzles using the compiled program provdided as follows:- MakePuz List Puzzles.dat 23jun91/bm ---LINKED DATA STRUCTURES FOR DFID--- =================== ================== Open-> | Num | Ptr | Next --> | Num | Ptr | Next ---/ =================== ================== | | \|/ \|/ ======= ======= Hn Hn Gn Gn Parent Parent ptr->"1234.." ptr->"A13C.." ======= ======= ^ ^ =========|========= | Hash-> | Num | Ptr | Next --> | .. =================== | .. | .. ___________________>| .. | .. =================== Hash-> | Num | Ptr | Next --> =================== The Dfid open list is a stack stored as a linked list. The linked list pointers are separated from the puzzle data structures to permit multiple orderings of the puzzles. Puzzles in both the open and closed lists are pointed to by collision chains attached to an array of pointers. The puzzle hash key is the array index. Each puzzle link is assigned a unique number as the associated puzzle is created. The Parent field of each puzzle contains the NodeNum of it's parent. This allows tracing of the solution path to establish algorithm correctness. Note that the solution path could have been established by doublely-linked lists. But I have chosen to make the search process more efficient by ignoring the cost of reproducing the solution path. Not shown in the above diagram is the additional structure used for the A* algorithm. For A*, the open list must be resorted in heuristic order with the best node (lowest Fn) available first. Instead of one list, I use a table of lists with each list containing nodes having equal heuristic value -- the ordering of a particular list does not matter. The heuristic function, Fn = Gn + Hn, is the table index. In theory, Fn could grow very large but in the limited space of a 640k PC, a fixed table size of FN_MAX=199 was found to be adequate. The important point.. no sorting required. The bidirectional DFID discards most of the forward state space. Therefore, a software switch set by menu option "3..Save Result in file", saves all the forward nodes in a hash table so the solution path can be displayed as well as detected. // COMPARISION OF DFID AND A_STAR Except for very simple problems, Dfid is a loser when compared to A*. A* solves more puzzles, such as puzzle 2 in appendix I of the class handout, produces fewer node expansions, and runs to completion in less time. On a slow machine, Dfid fills memory in ten minutes, while A* stops after six minutes. Dfid loses time by having to rebuild the state space for each iteration. Also, because Depth First Search uses a stack, promising paths are often buried by poor ones. On the other hand, A* always picks the best candidate from the open list... using the Manhattan heuristic in my example. Dfid could only search to depth twelve in the memory available so is unable to solve puzzle 2 of the handout. A* solves this puzzle by searching to depth twenty-six. // rem ...DfidTest.bat... del BmResult.tmp :xx Dfid 123-56749AB8DEFC Level_3 Dfid 123456789-ABDEFC Level_3 Dfid 12345-689A7CDEBF Level_4 Dfid 12345-7896BCDAEF Level_4 Dfid 1-2356749AB8DEFC Level_5 Dfid 123456789EAC-DBF Level_5 Dfid 16245-379AB8DEFC Level_6 Dfid -12456379AB8DEFC Level_6 Dfid 16245A389-7CDEBF Level_7 Dfid 12345678ABC-9DEF Level_7 Dfid 12345678ABEC9DF- Level_8 Dfid 12345678ABEC9-DF Level_8 Dfid 1-34927865BCDAEF Level_9 Dfid 123497-865BCDAEF Level_9 Dfid -27316B459A8DEFC Level_10 Dfid 124756389-FBDAEC Level_11 Dfid -247153896ABDEFC Level_12 Dfid 13645A-29B87DEFC Level_13 Dfid 12345678DFEBA9C- puz1_appndxI Dfid 9513D728E64BAFC- puz2_appndxI_no_room Dfid 62475FB8A13CD9E- puz3_appndxI_no_room Dfid 1374958BE62CAEF- puz4_appndxI_no_room Dfid 256491F7ED38ACB- puz5_appndxI_no_room Dfid 12345678acbdfe9- puz6_appndxI_no_room Dfid 1423658be9cfad7- puz7_appndxI_no_room Dfid 7DB1-4E6852CAF93 puz8_appndxI_no_room Dfid FBEC7AD98465321- puz9_appndxI_no_room Dfid 92DA5C74E1-FB638 puz10_appndxI_no_room goto xx // This is an example of the optional solution file. A PD utility "List.com" is provided for convenient viewing and called by the Dfid program. Nodes Expanded: Count of child nodes put on the open lists Moves Considered: Count of moves possible as each node is expanded. This exceeds nodes expanded because only unique puzzles are created. Puzzles Generated: All the puzzle nodes created for a solution attempt. BiDirectional DFID --- by Bob McIsaac Clock: 0.0 Seconds Nodes Expanded: S->G 2 Depth 1 Nodes Expanded: G->S 8 Depth 2 Moves Considered: 12 Puzzles generated: 13 Source= 123-56749AB8DEFC ** Level_3 ** ..Final Closed List.. ..Trace path backwards to source.. 123-56749AB8DEFC ..from common node 2 1234567-9AB8DEFC NodeNum: 1 Gn: 0 Hn: 0 Dad 0 123-56749AB8DEFC NodeNum: 3 Gn: 1 Hn: -1 Dad 1 12-356749AB8DEFC NodeNum: 2 Gn: 1 Hn: -1 Dad 1 1234567-9AB8DEFC ..Trace path backwards to goal.. 123456789ABCDEF- ..from common node 12 1234567-9AB8DEFC NodeNum: 12 Gn: 2 Hn: -1 Dad 8 1234567-9AB8DEFC NodeNum: 13 Gn: 2 Hn: -1 Dad 8 123456789A-BDEFC NodeNum: 8 Gn: 1 Hn: -1 Dad 7 123456789AB-DEFC NodeNum: 10 Gn: 2 Hn: -1 Dad 9 123456789A-CDEBF NodeNum: 11 Gn: 2 Hn: -1 Dad 9 123456789ABCD-EF NodeNum: 9 Gn: 1 Hn: -1 Dad 7 123456789ABCDE-F NodeNum: 7 Gn: 0 Hn: 0 Dad 0 123456789ABCDEF- rem ....StarTest.Bat... del BmResult.tmp :xx Astar 123-56749AB8DEFC Level_3 Astar 123456789-ABDEFC Level_3 Astar 12345-689A7CDEBF Level_4 Astar 12345-7896BCDAEF Level_4 Astar 1-2356749AB8DEFC Level_5 Astar 123456789EAC-DBF Level_5 Astar 16245-379AB8DEFC Level_6 Astar -12456379AB8DEFC Level_6 Astar 16245A389-7CDEBF Level_7 Astar 12345678ABC-9DEF Level_7 Astar 12345678ABEC9DF- Level_8 Astar 12345678ABEC9-DF Level_8 Astar 1-34927865BCDAEF Level_9 Astar 123497-865BCDAEF Level_9 Astar -27316B459A8DEFC Level_10 Astar 124756389-FBDAEC Level_11 Astar -247153896ABDEFC Level_12 Astar 13645A-29B87DEFC Level_13 Astar 12345678DFEBA9C- puz1_appndxI Astar 9513D728E64BAFC- puz2_appndxI Astar 62475FB8A13CD9E- puz3_appndxI_no_room Astar 1374958BE62CAEF- puz4_appndxI_no_room Astar 256491F7ED38ACB- puz5_appndxI_no_room Astar 12345678acbdfe9- puz6_appndxI_no_room Astar 1423658be9cfad7- puz7_appndxI_no_room Astar 7DB1-4E6852CAF93 puz8_appndxI_no_room Astar FBEC7AD98465321- puz9_appndxI_no_room Astar 92DA5C74E1-FB638 puz10_appndxI_no_room goto xx ; STATE-SPACE HEURISTIC SEARCH ALGORITHM ; This is a short (very short) description of the control algorithm ;used by the heuristic search procedure below. This code is fully described ;in the "Expert's Toolbox" column of the March 1987 AI-Expert magazine. ;For a more complete description of heuristic search, and a discussion of ;strategies for heuristic functions, see Nils J. Nilsson, "Principles of ;Artificial Intelligence", Tioga Publications, 1980, as well as many other ;texts on AI. ;Terminology: ; Problems which lend themselves to this kind of solution can be thought ;of in terms of a series of STATES. The INITIAL STATE is known, and some ;GOAL STATE is desired. For example, in chess, the initial state is a board ;with no pieces moved, and the goal state is a mate situation for your side. ; One state can be changed in to another state by some predictable ;change. We say that it has SUCCESSORS, or those states which result from ;only one of the possible changes. In chess, the initial state has as many ;successors as can be produced by making the possible legal moves for white. ; Ideally, a program would search through all the possible combinations ;of moves to find a goal state. Often however (as in our chess example), ;there are far too many combinations for the program to consider before its ;human operators become impatient or run out of money. ; That's where the HEURISTIC part comes in. The heuristic function assigns ;a value to each state, which represents how hard it was to reach the state and ;how hard it is likely to be to get from there to the goal. It helps the ;program decide which sequence of moves is most likely to lead to the goal ;state. The search doesn't consider unfruitful sequences, and so (hopefully, ;if the heuristic function is adequate) finds the goal state in a reasonable ;amount of time. There is a body of theory which deals with evaluating the ;quality of heuristic functions. This is discussed in Nilsson's book, and is ;beyond the scope of this note. ; One or two more terms are necessary to understand the algorithm. If n is ;a state, the cost f(n) produced by the heuristic function is f(n) = g(n) + h(n), ;where g(n) is an estimate of the cost of reaching state n, and h(n) is an ;estimate of the cost of reaching the goal from state n. The actual method of ;obtaining g and h varies with the problem. For chess, it would be some very ;elaborate function. For a "Tower of Hanoi" problem, it is a straight- ;forward estimate of numbers of disk moves. ; It is worth noting that this can be a very inefficient way of solving a ;problem. If you can come with an algorithmic solution to a problem, it is ;almost certainly faster than using a state space search. For example, Xlisp ;on an Apple Macintosh can solve a three disk tower of hanoi with a simple ;recursive function in a blink of an eye. The same problem using heuristic ;search takes about two minutes. However, some problems are (as far as we know) ;impossible to solve without a search technique like the one given here. ;The Algorithm: ; Uses two lists, OPEN and CLOSED. For notational convenience, ; let the cost of getting from state n to state m be represented ; by C(n,m). ;1. Put the initial state S1 into OPEN. ; Let g(S1) = 0, compute h(S1) ;2. If OPEN is empty, exit with failure. ;3. Remove from OPEN the state for which g(n) + h(n) is minumum. ; Call it N. ; Add N to CLOSED. ; If N is a goal state, exit with success. ;4. For all states m which are successors of N: ; if m is not on OPEN or CLOSED ; add m to OPEN ; set g(m) = g(N) + C(n,m) ; compute h(m) ; if m is on OPEN ; if current value of g(m) > g(N) + C(N,m) ; then reset g(m) = g(N) + C(N,m) [We found a cheaper path] ; if m is on CLOSED ; if current value of g(m) > g(N) + C(N,m) ; then reset g(m) = g(N) + C(N,m) ; move m back to OPEN ;5. Go to step 2 ; This algorithm is implemented below. The art of this business is ;in defining the problem in such a way that one can express the cost of getting ;from one state to another, and in calculating h(n) to be as close to the true ;cost as possible without going over. ; I welcome comments and correspondence concerning these ;programs. ;Marc Rettig ;Technical Editor, AI-Expert ;76703,1037 ;/******************** GENERIC SEARCH ROUTINES **********************/ ; STATE-SPACE SEARCH PROCEDURE ; These functions provide a general control structure for ; solving problems using heuristic search. In order to apply ; this method to a particular problem, you must write the ; functions: initial-state, goal, successors, and print-solution. ; ; In the programs and comments below, ; g(n) refers to the best estimate of the cost to get to state n, ; and h(n) is the best estimate of the cost to reach the goal ; state from state n. This corresponds with Nilsson's notation. ; ; Algorithm given by Dr. Ralph Grishman, New York University. ; Adapted for Xlisp by Marc Rettig (76703,1037), 9/86. (defun search () (prog (open closed n m successor-list same) ; Step 1. Put initial state on open. (setq open (list (initial-state))) ; Step 2. If open is empty, exit with failure. expand: (cond ((null open) (print 'failure) (return nil))) ; Step 3. Remove state from open with minimum g + h and ; call it n. (open is sorted by increasing g + h, so ; this is first element.) Put n on closed. ; Exit with success if n is a goal node. (setq n (car open)) (setq open (cdr open)) (setq closed (cons n closed)) (trace 'expanding n) (cond ((goal n) (print-solution n) (return t))) ; For each m in successors(m): (setq successor-list (successors n)) next-successor: (cond ((null successor-list) (go expand:))) (setq m (car successor-list)) (setq successor-list (cdr successor-list)) (trace 'successor m) (cond ((setq same (find m open)) ; if m is on open, reset g if new value is smaller (cond ((< (get m 'g) (get same 'g)) (setq open (add m (remove same open)))))) ((setq same (find m closed)) ; If m is on closed and new value of g is smaller, ; remove state from closed and add it to open with new g. (cond ((< (get m 'g) (get same 'g)) (setq closed (remove same closed)) (setq open (add m open))))) (t ; else add m to open (setq open (add m open)))) (go next-successor:))) (defun add (state s-list) ; Inserts state into s-list so that list remains ordered ; by increasing g + h. (cond ((null s-list) (list state)) ((> (+ (get (car s-list) 'g) (get (car s-list) 'h)) (+ (get state 'g) (get state 'h))) (cons state s-list)) (t (cons (car s-list) (add state (cdr s-list)))))) (defun find (state s-list) ; returns first entry on s-list whose position is same ; as that of state. (cond ((null s-list) nil) ((equal (get state 'position) (get (car s-list) 'position)) (car s-list)) (t (find state (cdr s-list))))) ; M I S S I O N A R I E S A N D C A N N I B A L S ; ; The following routines, when used in conjunction with the state-space ; search procedure, solve the missionaries and cannibals problem. Three ; missionaries and 3 cannibals are located on the right bank of a river, ; along with a two-man rowboat. We must find a way of moving all the ; missionaries and cannibals to the left bank. However, if at any time ; there are more cannibals than missionaries on a bank, the cannibals will ; exhibit a consuming interest in the misssionaries; this must be avoided. ; ; Each state is represented by an atom with the following properties: ; position -- a list of three elements, ; the number of missionaries on the right bank ; the number of cannibals on the right bank ; the position of the boat (left or right) ; g -- the estimated g for that state ; h -- the estimated h (value of function heuristic) ; parent -- the preceding state on the path from the initial state ; (the preceding state which gives rise to the least g, ; if there are several) (defun initial-state () ; return the initial state (build-state 3 3 'right 0 nil)) (defun successors (state) ; returns the successors of state ; note that procedure try uses state and new-g, and modifies suc (setq new-g nil) (setq suc nil) (prog () (setq m (car (get state 'position))) (setq c (cadr (get state 'position))) (setq boat (caddr (get state 'position))) ; extract parameters of current position and put in m, c, and boat ; g of new state = g of old state + 1 (all crossings are unit cost) (setq new-g (+ 1 (get state 'g))) (cond ((equal boat 'right) (try (- m 2) c 'left state) (try (- m 1) c 'left state) (try (- m 1) (- c 1) 'left state) (try m (- c 1) 'left state) (try m (- c 2) 'left state)) (t ; boat is on left (try (+ m 2) c 'right state) (try (+ m 1) c 'right state) (try (+ m 1) (+ c 1) 'right state) (try m (+ c 1) 'right state) (try m (+ c 2) 'right state))) (return suc))) (defun try (new-m new-c new-boat state) ; if position(new-m,new-c,new-boat) is valid, add new state to suc (cond ((valid new-m new-c) (setq suc (cons (build-state new-m new-c new-boat new-g state) suc))))) (defun valid (miss cann) ; returns true if having 'miss' missionaries and 'cann' cannibals ; on the right bank is a valid state (and (>= miss 0) (>= cann 0) (< miss 4) (< cann 4) (or (zerop miss) (>= miss cann)) (or (zerop (- 3 miss)) (>= (- 3 miss) (- 3 cann))))) (defun build-state (miss cann boat g parent) ; creates a new state with parameters as specified by argument list (prog (newstate) (setq newstate (gensym)) (putprop newstate (list miss cann boat) 'position) (putprop newstate g 'g) (putprop newstate (heuristic miss cann boat) 'h) (putprop newstate parent 'parent) (return newstate))) (defun heuristic (miss cann boat) ; our heuristic (h) function (cond ((equal boat 'left) (* 2 (+ miss cann))) (t ; boat is on right (* 2 (max 0 (+ miss cann -2)))))) (defun goal (state) ; returns true if state is a goal state (no missionaries or cannibals on right) (and (zerop (car (get state 'position))) (zerop (cadr (get state 'position))))) (defun print-solution (state) ; invoked by search algorithm with goal state, ; prints sequence of states from initial state to goal. (cond ((null state) (print 'solution:) (print 'miss-cannib-bank)) (t (print-solution (get state 'parent)) (print (get state 'position)) )) ) (defun trace (comment state) ; if trace-switch is true, printout comment and position ; associated with state (cond (trace-switch (print `(,comment state ,state with position ,(get state 'position) h(x) = ,(get state 'h))))))