I must implement , in Lisp , a depth-search algorithm in an implict graph (namely a graph where I have the starting node, the goal node, and the successor function ,f, that give a node create his successors). There is a depth limit d. The algorithm must return a path (obviously cannot be minimal).

My problem is how manage the loop .

My first question is: If I use this following stupid method work it?

I have 2 list. The first is a LIFO ((I call it list1) when I insert in the head the succesor nodes. Evry time I expand the node in the head.

In the second list (I call it list2) I keep a list where put all nodes already met and every time that I expand a node I check if successor nodes obtained are in the list above (list2). For the nodes that are in it (in list2) I don't insert in list1.

This method sucks because in the worst case i must keep in list2 all nodes of the graph and I must search at every expansion if some successor nodes are in the list2. (for example, this method certainly works with breadth-first search) But at least it works? Or I would risk to cut relevant paths ?

Second question is: How can I implement it efficiently (pseudocode, or simply idea)?

Thanks in advance

  • You want a Set rather than a List for the visited nodes. Common set representations are Red–Black Trees or Hash Tables. – amon Jul 8 '15 at 13:33

Use recursion:

;; you might want to implement sets using hash tables
(defun make-set (&rest elements)
(defun set-empty-p (s)
  (null s))
(defun set-union (s1 s2)
  (union s1 s2))
(defun depth-search (start end next max-depth
                     &key (seen (make-set start))
                       (depth 0) (path (list start)))
  ;; untested!
  (when (eq start end)
    (return path))
  (when (= depth max-depth)
    (return t))                 ; no path
  (let ((candidates (set-difference (funcall next start) seen)))
    (loop for candidate in candidates
      for path = (depth-search candidate end next max-depth
                               :seen (set-union seen (make-set candidate))
                               :depth (1+ depth) :path (cons candidate path))
      do (when (listp path) (return path))
      finally (return t))))
  • Thanks for the reply. But I believe that with this implementation are stored in "seen" all nodes already seen losing the advantage of depth-search: linear memory. The problem is avoidable in some way? – Nicola Jul 8 '15 at 16:08
  • I don't think you can avoid marking nodes as seen – sds Jul 8 '15 at 16:10
  • @Nicola If you don't want to use a separate set, you need to redefine nodes so that they have a visited flag (e.g. CLOS slot, property lists). You'd need to clean up the flag when returning from depth-search. – coredump Aug 21 '15 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.