Hi. I�m programming the best first search algorith in Lisp. It�s the
first time I use Lisp an d I`m having some problems:
I�d like to put the f-value (heuristic) in the node and I�ve thougth
that it would be right to use a property called like 'value or something
like that. But I`ve realized that properties are only used for atoms, so
a node isn�t an atom. Could anyone of you advice me about how to
implement this?. Is it possible to use properties?.
Pete wrote:
> Hi. I�m programming the best first search algorith in Lisp. It�s the
> first time I use Lisp an d I`m having some problems:
>
> I�d like to put the f-value (heuristic) in the node and I�ve thougth
> that it would be right to use a property called like 'value or something
> like that. But I`ve realized that properties are only used for atoms, so
> a node isn�t an atom. Could anyone of you advice me about how to
> implement this?. Is it possible to use properties?.
Sorry to sound ignorant, but what is the best first search?
Chris
Chris Croft-White <·····@cam.ac.uk> wrote in message
·····················@cam.ac.uk...
> Pete wrote:
>
> > Hi. I�m programming the best first search algorith in Lisp. It�s the
> > first time I use Lisp an d I`m having some problems:
> >
> > I�d like to put the f-value (heuristic) in the node and I�ve thougth
> > that it would be right to use a property called like 'value or something
> > like that. But I`ve realized that properties are only used for atoms, so
> > a node isn�t an atom. Could anyone of you advice me about how to
> > implement this?. Is it possible to use properties?.
>
> Sorry to sound ignorant, but what is the best first search?
>
A kind of heuristic search. The choice of direction in search space is
carried out based on some evaluation of alternatives. A* and other gradient
methods are good examples.
--
Eugene.
Chris Croft-White wrote:
>
> Pete wrote:
>
> > Hi. I�m programming the best first search algorith in Lisp. It�s the
> > first time I use Lisp an d I`m having some problems:
> >
> > I�d like to put the f-value (heuristic) in the node and I�ve thougth
> > that it would be right to use a property called like 'value or something
> > like that. But I`ve realized that properties are only used for atoms, so
> > a node isn�t an atom.
Properties are only used for symbols. How about a node structure,
with a value field?
> > Could anyone of you advice me about how to
> > implement this?. Is it possible to use properties?.
>
> Sorry to sound ignorant, but what is the best first search?
You start off with an agenda containing the start node.
You take the node on the agenda with the optimum value of
the heuristic function. The nodes you get are then put on
the agenda, and the process repeats until you reach the goal.
> Chris
Le Hibou (ma propre opinion)
--
" |
Ceci n'est pas une pipe.
"
-- Daniel B. Case.
Pete <·········@cajamurcia.es> writes:
> Hi. I´m programming the best first search algorith in Lisp. It´s the
> first time I use Lisp an d I`m having some problems:
>
> I´d like to put the f-value (heuristic) in the node and I´ve thougth
> that it would be right to use a property called like 'value or something
> like that. But I`ve realized that properties are only used for atoms, so
> a node isn´t an atom. Could anyone of you advice me about how to
> implement this?. Is it possible to use properties?.
No, property lists are bound to symbols, and since your nodes aren't
symbols, you can't use the usual property lists (and you probably
shouldn't use them anyway, even if you could). IMHO you can either
1.) Store the value directly in the node. If your nodes are
structures or objects, use an additional slot in the node. This
is especially useful if the calculated values are persistent in
nature, i.e. they can be reused in future invocations of the
function, and have a useful live-time as long as the node/tree.
2.) Use an external datastructure to keep track of the mapping between
nodes and values, probably a hash-table. This is especially
useful if the calculated values are transient in nature, i.e. are
only useful during one call of the function. In this case you can
use an internal hash-table and internal getter/setter functions
with static scope.
Both solutions can be made to look alike:
1)
(defstruct node
contents
left
right
value) ;; Possibly supply a default-value for value
(defun my-function (top-node)
;; Do the Work, and use (node-value node) to get values and
;; (setf (node-value node) new-value) to set values...
t)
2)
(defun my-function (top-node)
(let ((ht (make-hash-table :test #'eql))) ; The Hash-Table
(labels ((node-value (node) (gethash node ht)) ; The getter
((setf node-value) (newval node) ; The setf setter
(setf (gethash node ht) newval))
(process-node (node)
;; The real work-horse function, which performs the
;; recursive search, using (node-value node) to get
;; values and (setf (node-value node) new-value) to
;; set values. This must be done as an internal
;; function, so that all recursive invocations use
;; the same hash-table (ht) to store/retrieve values
t))
;; Now we pass the bucket to process-node on the top-node
(process-node top-node))))
Regs, Pierre.
--
Pierre Mai <····@acm.org> PGP and GPG keys at your nearest Keyserver
"One smaller motivation which, in part, stems from altruism is Microsoft-
bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]
"Pierre R. Mai" wrote:
...
> (defstruct node
> contents
> left
> right
> value) ;; Possibly supply a default-value for value
If there is a need to implement a very large tree (like database indices
when fetched in the memory), space is going to be a concern in that it
may not be possible to afford 2 x 4 bytes for left and right. In this
case, an array of structs could be created, where left and right are
indices, and see if the implementation stores unboxed structs and
unboxed slots in the array unboxed.
Robert
On 23 Oct 1999 19:08:32 +0200, ····@acm.org (Pierre R. Mai) wrote:
> (let ((ht (make-hash-table :test #'eql))) ; The Hash-Table
^^^^^^^^^^^
Isn't this redundant?
Paolo
--
EncyCMUCLopedia * Extensive collection of CMU Common Lisp documentation
http://cvs2.cons.org:8000/cmucl/doc/EncyCMUCLopedia/
·······@mclink.it (Paolo Amoroso) writes:
> On 23 Oct 1999 19:08:32 +0200, ····@acm.org (Pierre R. Mai) wrote:
>
> > (let ((ht (make-hash-table :test #'eql))) ; The Hash-Table
> ^^^^^^^^^^^
> Isn't this redundant?
Yes it is. But I like to include this in "template" code that is
posted to the group, so that readers are reminded to think about which
test would be apropriate in their case. I also like to document test
predicates that are persistent parts of datastructures in this way,
instead of leaving them implicit. OTOH I don't care about this with
functions that don't store the predicate (e.g. the sequence
functions). Probably my own idiosyncratic way.
Regs, Pierre.
--
Pierre Mai <····@acm.org> PGP and GPG keys at your nearest Keyserver
"One smaller motivation which, in part, stems from altruism is Microsoft-
bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]
Pete <·········@cajamurcia.es> writes:
> I�d like to put the f-value (heuristic) in the node and I�ve thougth
> that it would be right to use a property called like 'value or something
> like that. But I`ve realized that properties are only used for atoms, so
> a node isn�t an atom. Could anyone of you advice me about how to
> implement this?. Is it possible to use properties?.
Your best bet is probably to represent the nodes as _structures_
defined by DEFSTRUCT or DEFCLASS.
Read up on these.
Stig Hemmer,
Jack of a Few Trades.