Table of Contents
1 Introduction
Back in 2014, I tried taking Pascal Van Hentenryck's Coursera course on Discreet Optimization. It was well over my head, but I feel like I learned a lot watching the videos and trying unsuccessfully to complete the early assignments. Later I came across {Norvig's Book}.
nil
Much of Van Hentenryck's course is what was once artificial intelligence. The first important topic is search. Although I had written depth first and breadth first search algorithms in Racket for Tim Roughgarden's Alogorithms Design and Analysis course on Coursera, I didn't understand how to manipulate the implementation. {Norvig's Book} has a very clear modular approach to search and provides several techniques to potentially improve its performance.
1.1 A Set of Search Tools
Search can be described as [see {Norvig's Book} section 6.4]:
- A start state
- A goal state
- The successors, or states that can be reached from any other state
- The strategy for determining the order in which we search
2 Common Lisp
This is the base implementation since {Norvig's Book} is informing the design.
<<cl-auto-generated-note>> <<cl-tree-search>> <<cl-successors>> <<cl-depth-first>> <<cl-breadth-first>> <<cl-helpers>>
2.1 tree search
(defun tree-search (states goal-p successors combiner)
"Find a state that satisfies goal-p. Start with states.
and search according to successors and combiner."
(dbg :search "~&;; Search: ~a" states)
(cond
((null states) ;nothing left to search
fail)
((funcall goal-p (first-states)) ;found a goal state
(first states))
(t
(tree-search
(funcall combiner
(funcall successors (first states))
(rest states))
goal-p successors combiner))))
2.2 goal-p
One of the things Common Lisp emphasizes is good names. A good name for a predicate generator is is …depending on how 'is' is defined.
(defun is (value) #'(lambda (x) (eql x value)))
2.3 successors
;;;;;;;;;;;;;;;; ;; SUCCESSORS ;; ;;;;;;;;;;;;;;;; <<cl-inifinite-binary-tree>> <<cl-finite-binary-tree>>
As always, Common Lisp has a way of challenging me. Rather than defining a data set to search, Norvig defines a binary tree with a function. Although now that I think about it, that's how we really want to think about search – we want to think about search over a stream that might be infinite rather than a haystack of fixed size. Even when the stream of possible solutions is bounded, combinatorial explosion produces a solution space that is for practical purposes equivalent to an infinite one.
(defun binary-tree (x) (list (* 2 x) (+ 1 (* 2 x))))
For testing it makes sense to have a finite binary tree as well. Again, the tree is generated with a function (that's the idea of successors), but it prunes the successors that don't meet the criteria. The important point here, is that successor does the pruning. That was hard to see when I was trying to right these functions previously.
(defun finite-binary-tree (n)
"Return a successor function that generates a binary tree with n nodes."
#'(lambda (x)
(remove-if #'(lambda (child) (> child n))
(binary-tree x))))
2.4 depth first search
(defun depth-first-search (start goal-p successors) "Search new states first until goal is reached." (tree-search (list start) goal-p successors #'append))
2.5 breadth first search
The difference between depth first and breadth first search is that earlier successors are searched before later successors. To create this, use a simple analog to append.
(defun prepend (x y) "Prepend y to the start of x." (append y x))
Defining a breadth first search from tree search becomes:
(defun breadth-first-search (start goal-p successors) "Search oldest states first until goal is reached." (tree-search (list start) goal-p successors #'prepend))
2.6 Helpers
;;;;;;;;;;;;; ;; HELPERS ;; ;;;;;;;;;;;;; <<cl-is>> <<cl-prepend>>
2.6.1 auto-generation header
;;; This file was autogenerated using org-babel-tangle ;;; on the literate programming document located in the ;;; root directory of the git repository.
3 Python
<<python-auto-generated-note>> <<python-tree-search>> <<python-successors>> <<python-depth-first>> <<python-breadth-first>> <<python-helpers>>
3.1 tree search
def tree_search(states, goal_p, successors, combiner):
"""Find a state that satisfies goal_p. Start with states and search according to successors and combiner."""
if not states:
return fail
elif goal_p(states[0]):
return states[0]
else:
tree_search(combiner(successors(first states), rest(states)), goal_p, successors, combiner)
3.2 goal p
3.3 successors
<<python-inifinite-binary-tree>> <<python-finite-binary-tree>>
3.4 infinite binary tree
3.5 finite binary tree
3.6 depth first search
3.7 breadth first search
3.8 helpers
<<python-is>> <<python-prepend>>
3.8.1 auto-generation header
"""This file was autogenerated using org-babel-tangle on the literate programming document located in the root directory of the git repository."""