Date: 3/09 | Title: Program #2 tip -- how to get started |
Here's a quick guide to get you started on program#2.
Because you can work on so many different aspects of the
provided problem, it may not be entirely clear where to
begin. Following the steps given below will give you a head-start:
- Node vs. state:
The first matter is to distinguish between a node and a
state. A node is a super-structure, containing extra
information in addition to the game-board's state.
Look carefully the arguments of the function. If you see
state, provide a state. If you see node, provide
a node.
- Implement (expand ....):
First, implement a simple expand function, where a node
is taken as an argument. The result is a list of child nodes.
For each operator in 'up, 'down, 'left, 'right,
you should go through a series of tests before actually
expanding:
- Is the operator applicable?
- Is the resulting state a duplicate state?
- Does the child node go over the depth- or
the f-limit? (only applies to
DLS, IDS, and IDA*; ignore this at first).
Collect the new nodes by running (apply-op ...)
and putting those into a list:
(setq return-list nil)
...
... run checks ...
; apply operator, and use cons to paste it to the return-list
(setq return-list (cons (apply-op ....) return-list))
...
Finally, return that list as a result of (expand ....).
- Using the expand function, either get dfs or bfs to work.
BFS is easier to test. Modify dfs-core to use your expand
function and to take in initial state as necessary.
Provide input that would only take 2 to 3 moves to reach the
goal. Start from the goal state, and move the blank 2 to 3 times,
and use that resulting state as the initial state.
- For example, if (0 2 3 7 1 8 4 5 6) was the initial
state,
- Your initial node would be:
( (0 2 3 7 1 8 4 5 6)
0 ; let's assume we're doing uninformed search
0 ; depth is 0
() ; no operator applied yet
)
- When you run expand on the initial node above,
you should get a list of two nodes:
(
( (2 0 3 7 1 8 4 5 6)
0; ignore this for now
1; one operator has been applied so far
(RIGHT)
); this is your first node, resulting from moving right.
( (7 2 3 0 1 8 4 5 6)
0; ignore this for now
1; one operator has been applied so far
(DOWN)
); this is your second node, resulting from moving down.
) ; end of expanded node list
This is the list that needs to be returned by your expand
function. In your core routine, this list will be appended
to your existing node list.
Note that since I added the comments above, so the actual result
would be more like:
(((2 0 3 7 1 8 4 5 6) 0 1 (RIGHT)) ((7 2 3 0 1 8 4 5 6) 0 1 (DOWN)))
|
Date: 2/13 | Title: Compiling Lisp code |
To optimize and speed up execution, you should compile your program
code. You can do this in CMUCL by running the (compile-file
<filename>) function. See below for an example, where I am
compiling function(s) in the file fibo.l. The file contained the
definition for the (fibo ..) function. Of course you can have multiple
function definitions in the file, and all of those will be compiled.
Again, * is the
lisp prompt, and my inputs to lisp are in bold.
* (compile-file "fibo.l")
; Python version 1.1, VM version UltraSparc/Solaris 7 on 09 SEP 04 10:49:52 am.
; Compiling: /user/choe/web_project/420/fibo.l 09 SEP 04 10:44:02 am
; Converted FIBO.
; Compiling DEFUN FIBO:
; Byte Compiling Top-Level Form:
; fibo.sparcf written.
; Compilation finished in 0:00:00.
#p"/user/choe/web_project/420/fibo.sparcf"
NIL
NIL
* (load "fibo.sparcf")
; Loading #p"/user/choe/web_project/420/fibo.sparcf".
T
* (fibo 20)
10946
*
Note that you need to first compile it, and the note what the resulting
compiled file is (the one highlighted in red above),
and then finally (load ...) that.
|
Date: 2/09 | Title: Program #1 tip |
You can use one of these possibilities for (deriv-eval ...).
First, do (deriv ...), in all cases. Then, do either of the
following:
- Recursively evaluate, terminating when you bump
into the given variable or a number.
Return the value or the number itself.
- Use (subst ...) and then (eval ...).
- Use a combination of (setq ...), (list ...), and
(eval ...).
Hint:
(setq y 20)
(setq x 'y)
(eval (list '+ x x))
|
Date: 1/31 | Title: Typo in prog1.pdf slides |
> I noticed that asking for the derivative of (/ x x)
> returns
> (/ (+ x x) (* x x))
Naturally, that was a typo:
The "+" in the middle should be a "-":
d(f/g) g * df/dx - f * dg/dx
----- = -----------------------
dx g^2
> which follows the derivdiv formula, but is incorrect. (*side note* Do
> you know how this exception is justified in calculus?) Also, should we
> account for (/ 1 x)? Thanks again.
Yes, you should account for (/ 1 x).
I updated the prog1.pdf slide.
|