Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Traverse Path - Trees
48 views
Skip to first unread message
evelyn baesa
May 15, 2013, 7:31:22 AM5/15/13
to
How can LISP be used in back-tracking in a tree ?
Pascal J. Bourguignon
May 15, 2013, 1:36:28 PM5/15/13
to
Your problem statement is underspecified.
Backtracking is a notion that applies to a walking algorithm.
There are a lot of different ways to walk a tree.
In away, a walk of a tree that starts from the root and visits all the
nodes going thru their parent-child connections, is characterized
naturally by backtracking: after having visited a subtree, you
"backtrack" to the current node to visit the following subtree.
So for example:
(defstruct node
label left right)
(defun postfix-walk (node visit)
(when (node-left node)
(postfix-walk (node-left node) visit))
#|backtrack|#
(when (node-right node)
(postfix-walk (node-right node) visit))
#|backtrack|#
(funcall visit node))
(postfix-walk (make-node :label 'root
:left (make-node :label 'left
:left (make-node :label 'left-left)
:right (make-node :label 'left-right))
:right (make-node :label 'right))
(lambda (node) (print (node-label node))))
prints:
left-left
left-right
left
right
root
and you can see how the algorithm in postfix-walk "backtracked" from the
left-left node to visit the left-right node, and then backtracked twice
to visit the right node. Another way to make it even more obvious, use
the TRACE CL operator:
cl-user> (trace postfix-walk)
nil
cl-user> (postfix-walk (make-node :label 'root
:left (make-node :label 'left
:left (make-node :label 'left-left)
:right (make-node :label 'left-right))
:right (make-node :label 'right))
'identity)
0> Calling (postfix-walk #S(node :label root :left #S(node :label left :left #S(node :label left-left :left nil :right nil) :right #S(node :label left-right :left nil :right nil)) :right #S(node :label right :left nil :right nil)) identity)
1> Calling (postfix-walk #S(node :label left :left #S(node :label left-left :left nil :right nil) :right #S(node :label left-right :left nil :right nil)) identity)
2> Calling (postfix-walk #S(node :label left-left :left nil :right nil) identity)
<2 postfix-walk returned #S(node :label left-left :left nil :right nil)
2> Calling (postfix-walk #S(node :label left-right :left nil :right nil) identity)
<2 postfix-walk returned #S(node :label left-right :left nil :right nil)
<1 postfix-walk returned #S(node :label left :left #S(node :label left-left :left nil :right nil) :right #S(node :label left-right :left nil :right nil))
1> Calling (postfix-walk #S(node :label right :left nil :right nil) identity)
<1 postfix-walk returned #S(node :label right :left nil :right nil)
<0 postfix-walk returned #S(node :label root :left #S(node :label left :left #S(node :label left-left :left nil :right nil) :right #S(node :label left-right :left nil :right nil)) :right #S(node :label right :left nil :right nil))
you can see how the recursive algorithm backtracks from recursive calls
to continue processing the other parts of the tree.
--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.
You can take the lisper out of the lisp job, but you can't take the lisp out
of the lisper (; -- antifuchs
Backtracking is a notion that applies to a walking algorithm.
There are a lot of different ways to walk a tree.
In away, a walk of a tree that starts from the root and visits all the
nodes going thru their parent-child connections, is characterized
naturally by backtracking: after having visited a subtree, you
"backtrack" to the current node to visit the following subtree.
So for example:
(defstruct node
label left right)
(defun postfix-walk (node visit)
(when (node-left node)
(postfix-walk (node-left node) visit))
#|backtrack|#
(when (node-right node)
(postfix-walk (node-right node) visit))
#|backtrack|#
(funcall visit node))
(postfix-walk (make-node :label 'root
:left (make-node :label 'left
:left (make-node :label 'left-left)
:right (make-node :label 'left-right))
:right (make-node :label 'right))
(lambda (node) (print (node-label node))))
prints:
left-left
left-right
left
right
root
and you can see how the algorithm in postfix-walk "backtracked" from the
left-left node to visit the left-right node, and then backtracked twice
to visit the right node. Another way to make it even more obvious, use
the TRACE CL operator:
cl-user> (trace postfix-walk)
nil
cl-user> (postfix-walk (make-node :label 'root
:left (make-node :label 'left
:left (make-node :label 'left-left)
:right (make-node :label 'left-right))
:right (make-node :label 'right))
'identity)
0> Calling (postfix-walk #S(node :label root :left #S(node :label left :left #S(node :label left-left :left nil :right nil) :right #S(node :label left-right :left nil :right nil)) :right #S(node :label right :left nil :right nil)) identity)
1> Calling (postfix-walk #S(node :label left :left #S(node :label left-left :left nil :right nil) :right #S(node :label left-right :left nil :right nil)) identity)
2> Calling (postfix-walk #S(node :label left-left :left nil :right nil) identity)
<2 postfix-walk returned #S(node :label left-left :left nil :right nil)
2> Calling (postfix-walk #S(node :label left-right :left nil :right nil) identity)
<2 postfix-walk returned #S(node :label left-right :left nil :right nil)
<1 postfix-walk returned #S(node :label left :left #S(node :label left-left :left nil :right nil) :right #S(node :label left-right :left nil :right nil))
1> Calling (postfix-walk #S(node :label right :left nil :right nil) identity)
<1 postfix-walk returned #S(node :label right :left nil :right nil)
<0 postfix-walk returned #S(node :label root :left #S(node :label left :left #S(node :label left-left :left nil :right nil) :right #S(node :label left-right :left nil :right nil)) :right #S(node :label right :left nil :right nil))
you can see how the recursive algorithm backtracks from recursive calls
to continue processing the other parts of the tree.
--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.
You can take the lisper out of the lisp job, but you can't take the lisp out
of the lisper (; -- antifuchs
evelyn baesa
May 15, 2013, 11:24:28 PM5/15/13
to
On Wednesday, May 15, 2013 7:31:22 PM UTC+8, evelyn baesa wrote:
> How can LISP be used in back-tracking in a tree ?
Good day , thank you for your reply. I'm just a little bit curious, what I am trying to express my ideas say for example , the Travelling-Sales Man Problem. How to utilize LISP in back-tracking. As I read some resources , LISP is applied to AI projects, since I am also a beginner in learning LISP, I really appreciate so much whatever knowledge you can impart to me.I have tried one sample activity (the Casting Spels in LISP ) its just like a back-tracking form.
> How can LISP be used in back-tracking in a tree ?
Espen Vestre
May 16, 2013, 3:46:46 AM5/16/13
to
evelyn baesa <evely...@gmail.com> writes:
> Good day , thank you for your reply. I'm just a little bit curious,
> what I am trying to express my ideas say for example , the
> Travelling-Sales Man Problem. How to utilize LISP in back-tracking.
There is no built-in backtracking in Lisp, if that's what you were
> Good day , thank you for your reply. I'm just a little bit curious,
> what I am trying to express my ideas say for example , the
> Travelling-Sales Man Problem. How to utilize LISP in back-tracking.
expecting - you'll have to use other programming languages (Prolog, for
instance) if you want that.
I think you may benefit from reading an introduction to AI programming
with Lisp. It's getting a bit old now, so there may be newer
alternatives that I'm not aware of, but I very much liked Peter Norvig's
'Paradigms of Artificial Intelligence Programming' and used parts of it
when I taught a lisp programming course for computational linguistics at
a university.
http://norvig.com/paip.html
--
(espen)
0 new messages