[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Sample _working code_ for project 1 (Compiled binary) [**Important**]
Folks:
Since several of you wanted the ability to test the working of the
first part of the code before doing the other parts, I have decided to
provide you, in binary form, my working code. The atttached file,
sample-code.fasl
is a compiled file that should be directly loadable into any of the
windows allegro common lisps that we are supporting (both the one in labs
and the student one).
if you save the file into sample-code.fasl you load it using the
command
(load "sample-code.fasl")
;;need to prepend any subdirectories as needed. or you can do it from the
file menu
Once you load it if you run the function
(rao::help)
you get the usage instructions. Essentially, the instructions ask you to
1. define an init state (which is a 8-puzzle state of your choosing). We
assume that the final state is always the completely sorted state
((1 2 3) (4 5 6) (7 8 0))
2. Invoke A* search along with parameters
open-list initialized to the list
containing a single node whose state is the one you gave
the goal function
the children generator function
the f-value function
In the example, all functions start with rao:: meaning
that these are the functions defined in the sample-code.fasl.
To check YOUR A* code, you just need to use the name of YOUR A*
function instead of rao::top-A*
The rest of the functions rao::puz-goal-p rao::puz-expand and
rao::puz-f1-val can be used as is. This will allow you to check your A*
code of task 1 and 2 pending the creation of your own children generator,
goal-test functions etc.
Once you write your own goal test, children generator and f1-value
functions, you can use those instead of mine.
Note that the .fasl contains fully functional code. So you can compare
your code against mine on specific example if you want. Notice that
if you use rao::puz-f2-val instead of rao::puz-f1-val you will be getting
manhattan distance heuristic instead of the misplaced tiles heuristic.
> (rao::help)
********************USAGE EXAMPLE***********************
USER(168): (setq init (make-array '( 3 3 ) :initial-contents '((4 1 2)(7
6 3) ( 5 8 0))))
#2A((4 1 2) (7 6 3) (5 8 0))
USER(185): (time (rao::top-A* (list (make-node :state init :depth 0
:g-val 0)) #'rao::puz-goal-p #'rao::puz-expand #'rao::puz-f1-val))
earch Succeeded!
Initial state is #2A((4 1 2) (7 6 3) (5 8 0))
GO-LEFT -> #2A((4 1 2) (7 6 3) (5 0 8))
GO-LEFT -> #2A((4 1 2) (7 6 3) (0 5 8))
GO-UP -> #2A((4 1 2) (0 6 3) (7 5 8))
GO-UP -> #2A((0 1 2) (4 6 3) (7 5 8))
GO-RIGHT -> #2A((1 0 2) (4 6 3) (7 5 8))
GO-RIGHT -> #2A((1 2 0) (4 6 3) (7 5 8))
GO-DOWN -> #2A((1 2 3) (4 6 0) (7 5 8))
GO-LEFT -> #2A((1 2 3) (4 0 6) (7 5 8))
GO-DOWN -> #2A((1 2 3) (4 5 6) (7 0 8))
GO-RIGHT -> #2A((1 2 3) (4 5 6) (7 8 0))
Goal cost: 10 Goal depth: 10
Num nodes generated: 99
Num nodes expanded: 36
Av branching factor 2.75
Eff branching factor 1.4309691
; cpu time (non-gc) 141 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 141 msec user, 0 msec system
; real time 141 msec
; space allocation:
; 7,159 cons cells, 0 symbols, 18,616 other bytes, 646 static
bytes
NIL
*******************USAGE EXAMPLE***********
INSTEAD OF RAO::top-A* you subistitute the name of your A* function
ALSO IF YOU USED rao::puz-f2-val instead of rao::puz-f1-val, you will be
using manhattan distance heuristic instead of
misplaced tiles heuristic.
NIL
sample-code.fasl