;;;; Rebecca Orton
;;;; Project 2
;;;; Fall 2000 Artificial Intelligence Class
;;;; Professor Marcus Maloof
;;;; Number 4 - Using each algorithm, attempt to find the shortest
;;;; path between the following initial and goal cities:
;;;; Run Initial State Goal State
;;;; 1 Brest Marseille
;;;; 2 Montpellier Calais
;;;; 3 Strasbourg Bordeaux
;;;; 4 Paris Grenoble
;;;; 5 Grenoble Paris
;;;; 6 Brest Grenoble
;;;; 7 Grenoble Brest
;;;; bfs to Marseille from Brest
;;;; 12 visited, 9 expanded, 10 stored.
;;;; (BREST RENNES PARIS DIJON LYON LIMOGES
;;;; TOULOUSE MONTPELLIER AVIGNON MARSEILLE)
;;;; - not optimal path
;;;; bfs to Calais from Montpellier
;;;; 12 visited, 7 expanded, 8 stored.
;;;; (MONTPELLIER AVIGNON LYON DIJON STRASBOURG NANCY CALAIS)
;;;; - not optimal path
;;;; bfs to Bordeaux from Strasbourg
;;;; 7 visited, 4 expanded, 5 stored.
;;;; (STRASBOURG DIJON LYON LIMOGES BORDEAUX)
;;;; - an optimal path
;;;; bfs to Grenoble from Paris
;;;; 5 visited, 3 expanded, 4 stored.
;;;; (PARIS DIJON LYON GRENOBLE)
;;;; - an optimal path
;;;; bfs to Paris from Grenoble
;;;; 10 visited, 6 expanded, 7 stored.
;;;; (GRENOBLE AVIGNON MONTPELLIER TOULOUSE LIMOGES PARIS)
;;;; - not optimal path
;;;; bfs to Grenoble from Brest
;;;; 7 visited, 5 expanded, 6 stored.
;;;; (BREST RENNES PARIS DIJON LYON GRENOBLE)
;;;; - an optimal path
;;;; bfs to Brest from Grenoble
;;;; 26 visited, 14 expanded, 15 stored.
;;;; (GRENOBLE AVIGNON MONTPELLIER TOULOUSE
;;;; LIMOGES LYON DIJON STRASBOURG NANCY
;;;; CALAIS PARIS CAEN RENNES BREST
;;;; - not optimal path
;;;; hcs to Marseille from Brest
;;;; 4 visited, 3 expanded, 4 stored.
;;;; (BREST RENNES NANTES RENNES)
;;;; - not a successful path
;;;; hcs to Calais from Montpellier
;;;; 4 visited, 3 expanded, 4 stored.
;;;; (MONTPELLIER AVIGNON MARSEILLE AVIGNON)
;;;; - not a successful path
;;;; hcs to Bordeaux from Strasbourg
;;;; 3 visited, 2 expanded, 3 stored.
;;;; (STRASBOURG NANCY STRASBOURG)
;;;; - not a successful path
;;;; hcs to Grenoble from Paris
;;;; 4 visited, 3 expanded, 4 stored.
;;;; (PARIS CAEN CALAIS CAEN)
;;;; - not a successful path
;;;; hcs to Paris from Grenoble
;;;; 3 visited, 2 expanded, 3 stored.
;;;; (GRENOBLE LYON GRENOBLE)
;;;; - not a successful path
;;;; hcs to Grenoble from Brest
;;;; 4 visited, 3 expanded, 4 stored.
;;;; (BREST RENNES NANTES RENNES)
;;;; - not a successful path
;;;; hcs to Brest from Grenoble
;;;; 3 visited, 2 expanded, 3 stored.
;;;; (GRENOBLE LYON GRENOBLE)
;;;; - not a successful path
;;;; bnb to Marseille from Brest
;;;; 30 visited, 29 expanded, 1650 stored.
;;;; (MARSEILLE 99 AVIGNON 216 LYON 389 LIMOGES 329
;;;; NANTES 107 RENNES 244 BREST 0)
;;;; - optimal path
;;;; bnb to Calais from Montpellier
;;;; 25 visited, 23 expanded, 556 stored.
;;;; (CALAIS 297 PARIS 313 DIJON 192 LYON 216
;;;; AVIGNON 121 MONTPELLIER 0)
;;;; - optimal path
;;;; bnb to Bordeaux from Strasbourg
;;;; 28 visited, 24 expanded, 940 stored.
;;;; (BORDEAUX 220 LIMOGES 396 PARIS 372 NANCY 145 STRASBOURG 0)
;;;; - optimal path
;;;; bnb to Grenoble from Paris
;;;; 16 visited, 14 expanded, 228 stored.
;;;; (GRENOBLE 104 LYON 192 DIJON 313 PARIS 0)
;;;; - optimal path
;;;; bnb to Paris from Grenoble
;;;; 13 visited, 10 expanded, 70 stored.
;;;; (PARIS 313 DIJON 192 LYON 104 GRENOBLE 0)
;;;; - optimal path
;;;; bnb to Grenoble from Brest
;;;; 21 visited, 20 expanded, 641 stored.
;;;; (GRENOBLE 104 LYON 389 LIMOGES 329 NANTES 107
;;;; RENNES 244 BREST 0)
;;;; - optimal path
;;;; bnb to Brest from Grenoble
;;;; 30 visited, 27 expanded, 1207 stored.
;;;; (BREST 244 RENNES 107 NANTES 329 LIMOGES 389
;;;; LYON 104 GRENOBLE 0)
;;;; optimal path
;;;; Number 5 - For each algorithm, over the seven runs:
;;;; a. What was the average number of nodes entered?
;;;; (i.e. visited)?
;;;; b. What was the average number of nodes expanded?
;;;; c. What was the average number of nodes maintained
;;;; (i.e. stored)?
;;;; d. How often did it find the optimum?
;;;;
;;;; Place these results in comments at the top of your
;;;; source file.
;;;; Breadth First Search visited an average of 11 nodes.
;;;; Breadth First Search expanded an average of 7 nodes.
;;;; Breadth First Search stored an average of 8 nodes.
;;;; Breadth First Search found 3 optimal paths out of 7
;;;; successful paths.
;;;; Hill-Climbing Search visited an average of 4 nodes.
;;;; Hill-Climbing Search expanded an average of 3 nodes.
;;;; Hill-Climbing Search stored an average of 4 nodes.
;;;; Hill-Climbing Search found 0 optimal paths out of 7
;;;; unsuccessful attempts.
;;;; Branch and Bound Search visited an average of 23 nodes.
;;;; Branch and Bound Search expanded an average of 21 nodes.
;;;; Branch and Bound Search stored an average of 756 nodes.
;;;; Branch and Bound Search found 7 optimal paths out of 7
;;;; successful paths.
;;;; Number 1 - In Lisp, encode the following weighted graph.
;;;; The graph is encoded as a 'neighbor property of each
;;;; city symbol.
(setf (get 'Paris 'neighbors) '(Dijon 313
Nancy 372
Calais 297
Caen 241
Rennes 348
Limoges 396))
(setf (get 'Limoges 'neighbors) '(Lyon 389
Toulouse 313
Bordeaux 220
Nantes 329
Paris 396))
(setf (get 'Nancy 'neighbors) '(Calais 534
Strasbourg 145
Dijon 201
Paris 372))
(setf (get 'Dijon 'neighbors) '(Lyon 192
Strasbourg 335
Nancy 201
Paris 313))
(setf (get 'Strasbourg 'neighbors) '(Dijon 335
Nancy 145))
(setf (get 'Lyon 'neighbors) '(Dijon 192
Limoges 389
Avignon 216
Grenoble 104))
(setf (get 'Grenoble 'neighbors) '(Avignon 227
Lyon 104))
(setf (get 'Avignon 'neighbors) '(Marseille 99
Montpellier 121
Lyon 216
Grenoble 227))
(setf (get 'Marseille 'neighbors) '(Avignon 99
Nice 188))
(setf (get 'Nice 'neighbors) '(Marseille 188))
(setf (get 'Montpellier 'neighbors) '(Avignon 121
Toulouse 240))
(setf (get 'Toulouse 'neighbors) '(Montpellier 240
Limoges 313
Bordeaux 253))
(setf (get 'Bordeaux 'neighbors) '(Nantes 329
Limoges 220
Toulouse 253))
(setf (get 'Nantes 'neighbors) '(Bordeaux 329
Limoges 329
Rennes 107))
(setf (get 'Rennes 'neighbors) '(Paris 348
Nantes 107
Brest 244
Caen 176))
(setf (get 'Brest 'neighbors) '(Rennes 244))
(setf (get 'Caen 'neighbors) '(Paris 241
Calais 120
Rennes 176))
(setf (get 'Calais 'neighbors) '(Paris 297
Caen 120
Nancy 534))
(defun get-city-weight (city-node city-sym)
(cond ((null city-node) nil)
((null city-sym) nil)
((not (atom city-node)) nil)
((not (symbolp city-sym)) nil)
(t (second (member city-node
(get city-sym 'neighbors))))))
;;;; Number 2 - Use the following latitudes and longitudes for
;;;; the cities to write a function that returns the estimated
;;;; distance between two cities.
(setf (get 'Paris 'coordinates) '(48 51 00 N
2 20 00 E))
(setf (get 'Caen 'coordinates) '(49 15 00 N
0 20 00 W))
(setf (get 'Calais 'coordinates) '(50 57 36 N
1 57 00 E))
(setf (get 'Dijon 'coordinates) '(47 21 00 N
5 02 00 E))
(setf (get 'Lyon 'coordinates) '(45 44 00 N
4 52 00 E))
(setf (get 'Grenoble 'coordinates) '(45 21 36 N
5 19 12 E))
(setf (get 'Avignon 'coordinates) '(43 50 00 N
4 45 00 E))
(setf (get 'Marseille 'coordinates) '(43 18 00 N
5 25 00 E))
(setf (get 'Nice 'coordinates) '(43 42 00 N
7 21 00 E))
(setf (get 'Montpellier 'coordinates) '(43 38 00 N
3 53 00 E))
(setf (get 'Toulouse 'coordinates) '(43 37 00 N
1 27 00 E))
(setf (get 'Bordeaux 'coordinates) '(44 50 00 N
0 37 00 W))
(setf (get 'Limoges 'coordinates) '(45 30 00 N
1 10 00 W))
(setf (get 'Rennes 'coordinates) '(48 07 00 N
1 02 00 W))
(setf (get 'Brest 'coordinates) '(48 24 00 N
4 30 00 W))
(setf (get 'Strasbourg 'coordinates) '(48 32 24 N
7 37 34 E))
(setf (get 'Nancy 'coordinates) '(48 50 00 N
6 10 00 E))
(setf (get 'Nantes 'coordinates) '(47 15 00 N
1 30 00 W))
(defun convert-to-secs (degrees minutes seconds)
(cond ((null degrees) nil)
((null minutes) nil)
((null seconds) nil)
((not (integerp degrees)) nil)
((not (integerp minutes)) nil)
((not (integerp seconds)) nil)
(t (+ (* degrees 60 60) (* minutes 60) seconds))))
(defun sqr (x)
(cond ((null x) nil)
((not (integerp x)) nil)
(t(* x x))))
(defun distance (x1 y1 x2 y2)
(cond ((null x1) nil)
((null y1) nil)
((null x2) nil)
((null y2) nil)
((not (integerp x1)) nil)
((not (integerp y1)) nil)
((not (integerp x2)) nil)
((not (integerp y2)) nil)
(t(sqrt (+ (sqr (- x1 x2))
(sqr (- y1 y2)))))))
(defun get-x-coor (coordinates)
(cond ((null coordinates) nil)
((not (listp coordinates)) nil)
(t(progn
(setq x (convert-to-secs (first coordinates)
(second coordinates)
(third coordinates)))
(if (or (eq 'S (fourth coordinates))
(eq 'W (fourth coordinates))) (setq x (* -1 x))
x)
))))
(defun get-y-coor (coordinates)
(cond ((null coordinates) nil)
((not (listp coordinates)) nil)
(t(progn
(setq y (convert-to-secs (fifth coordinates)
(sixth coordinates)
(seventh coordinates)))
(if (or (eq 'E (eighth coordinates))
(eq 'S (eighth coordinates))) (setq y (* -1 y))
y)
))))
(defun get-city-distance (city-sym1 city-sym2)
(cond ((null city-sym1) nil)
((null city-sym2) nil)
((not (symbolp city-sym1)) nil)
((not (symbolp city-sym2)) nil)
(t(progn
(setq city1-coor (get city-sym1 'coordinates))
(setq city2-coor (get city-sym2 'coordinates))
(setq x1 (get-x-coor city1-coor))
(setq y1 (get-y-coor city1-coor))
(setq x2 (get-x-coor city2-coor))
(setq y2 (get-y-coor city2-coor))
(distance x1 y1 x2 y2)
)
)
)
)
;;;; Number 3
;;;; Implement
;;;; a. one uninformed search algorithm (i.e. depth-first or
;;;; breadth-first search),
;;;; b. one informed search algorithm (i.e. hill-climbing or
;;;; best-first search, and
;;;; c. one admissible search algorithm (i.e. branch-and-bound
;;;; or A*).
(setf (get 'Paris 'city-name) 'Paris)
(setf (get 'Caen 'city-name) 'Caen)
(setf (get 'Calais 'city-name) 'Calais)
(setf (get 'Dijon 'city-name) 'Dijon)
(setf (get 'Lyon 'city-name) 'Lyon)
(setf (get 'Grenoble 'city-name) 'Grenoble)
(setf (get 'Avignon 'city-name) 'Avignon)
(setf (get 'Marseille 'city-name) 'Marseille)
(setf (get 'Nice 'city-name) 'Nice)
(setf (get 'Montpellier 'city-name) 'Montpellier)
(setf (get 'Toulouse 'city-name) 'Toulouse)
(setf (get 'Bordeaux 'city-name) 'Bordeaux)
(setf (get 'Limoges 'city-name) 'Limoges)
(setf (get 'Rennes 'city-name) 'Rennes)
(setf (get 'Brest 'city-name) 'Brest)
(setf (get 'Strasbourg 'city-name) 'Strasbourg)
(setf (get 'Nancy 'city-name) 'Nancy)
(setf (get 'Nantes 'city-name) 'Nantes)
(defun get-neighbors (city-node)
(cond ((null city-node) nil)
((eq 'Paris city-node) (get 'Paris 'neighbors))
((eq 'Caen city-node) (get 'Caen 'neighbors))
((eq 'Calais city-node) (get 'Calais 'neighbors))
((eq 'Dijon city-node) (get 'Dijon 'neighbors))
((eq 'Lyon city-node) (get 'Lyon 'neighbors))
((eq 'Grenoble city-node) (get 'Grenoble 'neighbors))
((eq 'Avignon city-node) (get 'Avignon 'neighbors))
((eq 'Marseille city-node) (get 'Marseille 'neighbors))
((eq 'Nice city-node) (get 'Nice 'neighbors))
((eq 'Montpellier city-node) (get 'Montpellier 'neighbors))
((eq 'Toulouse city-node) (get 'Toulouse 'neighbors))
((eq 'Bordeaux city-node) (get 'Bordeaux 'neighbors))
((eq 'Limoges city-node) (get 'Limoges 'neighbors))
((eq 'Rennes city-node) (get 'Rennes 'neighbors))
((eq 'Brest city-node) (get 'Brest 'neighbors))
((eq 'Strasbourg city-node) (get 'Strasbourg 'neighbors))
((eq 'Nancy city-node) (get 'Nancy 'neighbors))
((eq 'Nantes city-node) (get 'Nantes 'neighbors))
)
)
(defun eol-t (a-list)
(if (null (cdr (cdr a-list))) 't))
(defun insert-node-in-order (node-item node-metric sort-list)
(cond ((null node-item) sort-list)
((null sort-list) (list node-item node-metric))
((member node-item sort-list :test #'equal) sort-list)
((< node-metric (second sort-list))
(append (list node-item node-metric) sort-list)
)
((null (fourth sort-list))
(append sort-list (list node-item node-metric))
)
((< node-metric (fourth sort-list))
(append
(list (first sort-list) (second sort-list))
(list node-item node-metric)
(cdr (cdr sort-list))
)
)
(t (append
(list (first sort-list) (second sort-list))
(insert-node-in-order node-item
node-metric
(cdr (cdr sort-list))
)
)
)
))
(defun sort-nodes (a-set sort-list)
(cond ((null a-set) sort-list)
(t(progn
(setq sort-list
(insert-node-in-order (first a-set)
(second a-set)
sort-list
)
)
(sort-nodes (cdr (cdr a-set)) sort-list)
)
)
))
(defun sort-set (a-set)
(sort-nodes a-set ()))
;;;; Reminder - The function eval-min is a supporting function for
;;;; the hill-climbing function below
(defun eval-min (start-list min-value min-node)
(cond ((null start-list) nil)
((null min-value) nil)
((null min-node) nil)
((not (listp start-list)) nil)
((not (integerp min-value)) nil)
((not (integerp (car (cdr start-list)))) nil)
(t (if (> min-value (car (cdr start-list)))
(progn
(setq min-value (car (cdr start-list)))
(setq min-node (car start-list))
(if (null (cdr (cdr start-list)))
(list min-node min-value)
(eval-min (cdr (cdr start-list))
min-value
min-node)
)
)
(if (null (cdr (cdr start-list)))
(list min-node min-value)
(eval-min (cdr (cdr start-list))
min-value
min-node)
)
))))
(defun eval-min-set (a-set)
(cond ((null a-set) nil)
((not (listp a-set)) nil)
(t(eval-min a-set 99999 'min-node))))
(defun eval-cost (start-list cost-value)
(cond ((null start-list) nil)
((null cost-value) nil)
((not (listp start-list)) nil)
((not (integerp cost-value)) nil)
((not (integerp (car (cdr start-list)))) nil)
(t (progn
(setq cost-value (+ cost-value
(car (cdr start-list))))
(if (null (cdr (cdr start-list)))
cost-value
(eval-cost (cdr (cdr start-list))
cost-value)
)
))))
(defun create-set (node path)
(cond ((null node) nil)
((not (listp node)) nil)
((not (listp path)) nil)
(t (append (list (append node path))
(list (eval-cost (append node path) 0)))
)))
(defun update-sets (node node-item set-list)
(cond ((null node) nil)
((null node-item) nil)
((null set-list) nil)
((not (eq node-item (car (car set-list))))
(append (list (first set-list)
(second set-list))
(update-sets node
node-item
(cdr (cdr set-list)))))
((member (car node) (car set-list))
(append (list (first set-list)
(second set-list))
(update-sets node
node-item
(cdr (cdr set-list)))))
(t (append (create-set node (car set-list))
(update-sets node
node-item
(cdr (cdr set-list)))))))
(defun add-sets (start-list node-item search-sets-list)
(cond ((null start-list) nil)
((null node-item) nil)
((null search-sets-list) nil)
((not (listp start-list)) nil)
((not (listp search-sets-list)) nil)
(t(append (update-sets
(append (list (car start-list))
(list (car (cdr start-list))))
node-item
search-sets-list)
(add-sets (cdr (cdr start-list))
node-item
search-sets-list)
))))
(defun trim-sets (node-item set-list)
(cond ((null node-item) nil)
((null set-list) nil)
((eq node-item (car (car set-list)))
(trim-sets node-item
(cdr (cdr set-list))))
(t(append (list (first set-list)
(second set-list))
(trim-sets node-item
(cdr (cdr set-list))
)
)
)))
(defun get-node-from-set (sorted-set)
(cond ((null sorted-set) nil)
((not (listp sorted-set)) nil)
(t(list (first (car sorted-set))
(second (car sorted-set))
))))
(defun get-node (city city-list)
(cond ((null city) nil)
((null city-list) nil)
(t (list (first (member city city-list))
(second (member city city-list))
))))
(defun get-metric (city neighbor)
(cond ((null city) nil)
((null neighbor) nil)
((not (atom city)) nil)
((not (atom neighbor)) nil)
((null (second (member neighbor
(get-neighbors city)))) 0)
(t(second (member neighbor (get-neighbors city)))
)))
(defun count-states (list-set)
(cond ((null list-set) 0)
((not (null (car list-set)))
(+ 1 (count-states (cdr (cdr list-set)))))))
;;; Bfs is an abbreviation for breadth first search function below.
(defun bfs (goal-node
start-list
visited-ctr
expanded-ctr
stored-ctr
a-path)
(cond ((null goal-node) nil)
((null start-list) nil)
((null visited-ctr) nil)
((null expanded-ctr) nil)
((null stored-ctr) nil)
((not (integerp visited-ctr)) nil)
((not (integerp expanded-ctr)) nil)
((not (integerp stored-ctr)) nil)
((not (symbolp goal-node)) nil)
((not (listp start-list)) nil)
((null (get goal-node 'city-name)) nil)
((member (car start-list) a-path)
(bfs goal-node
(cdr (cdr start-list))
(setq visited-ctr (+ 1 visited-ctr))
expanded-ctr
stored-ctr
a-path))
((member (get goal-node 'city-name) start-list)
(progn
(setq visited-ctr (+ 1 visited-ctr))
(setq stored-ctr (+ 1 stored-ctr))
(princ visited-ctr) (princ " visited, ")
(princ expanded-ctr)(princ " expanded, ")
(princ stored-ctr) (princ " stored.")
(print " ")
(setq a-path
(append a-path
(list (get goal-node 'city-name))))
))
(t (or (bfs goal-node
(get-neighbors (car start-list))
(setq visited-ctr (+ 1 visited-ctr))
(setq expanded-ctr (+ 1 expanded-ctr))
(setq stored-ctr (+ 1 stored-ctr))
(append a-path
(list (car start-list))))
(bfs goal-node
(cdr (cdr start-list))
(setq visited-ctr (+ 1 visited-ctr))
expanded-ctr
stored-ctr
a-path)
))))
;;;; The hill climbing search function below is abbreviated hcs.
(defun hcs (goal-node
start-list
visited-ctr
expanded-ctr
stored-ctr
a-path)
(cond ((null goal-node) nil)
((null start-list) nil)
((null visited-ctr) nil)
((null expanded-ctr) nil)
((null stored-ctr) nil)
((not (integerp visited-ctr)) nil)
((not (integerp expanded-ctr)) nil)
((not (integerp stored-ctr)) nil)
((not (symbolp goal-node)) nil)
((not (listp start-list)) nil)
((null (get goal-node 'city-name)) nil)
((member (car start-list) a-path)
(progn
(setq visited-ctr (+ 1 visited-ctr))
(setq stored-ctr (+ 1 stored-ctr))
(princ visited-ctr) (princ " visited, ")
(princ expanded-ctr)(princ " expanded, ")
(princ stored-ctr) (princ " stored.")
(print " ")
(setq a-path (append a-path
(list (car start-list))))
))
((member (get goal-node 'city-name) start-list)
(progn
(setq visited-ctr (+ 1 visited-ctr))
(setq stored-ctr (+ 1 stored-ctr))
(princ visited-ctr) (princ " visited, ")
(princ expanded-ctr)(princ " expanded, ")
(princ stored-ctr) (princ " stored.")
(print " ")
(setq a-path
(append a-path
(list (get goal-node 'city-name))))
))
(t (hcs goal-node
(eval-min (get-neighbors (car start-list))
9999
'min-node)
(setq visited-ctr (+ 1 visited-ctr))
(setq expanded-ctr (+ 1 expanded-ctr))
(setq stored-ctr (+ 1 stored-ctr))
(append a-path
(list (car start-list)))
))))
;;; The branch and bound search function is abbreviated bnb below.
(defun bnb (goal-node
start-list
visited-ctr
expanded-ctr
stored-ctr
a-path
search-sets)
(cond ((null goal-node) nil)
((null start-list) nil)
((null visited-ctr) nil)
((null expanded-ctr) nil)
((null stored-ctr) nil)
((null a-path) nil)
((null search-sets) nil)
((not (integerp visited-ctr)) nil)
((not (integerp expanded-ctr)) nil)
((not (integerp stored-ctr)) nil)
((not (symbolp goal-node)) nil)
((not (listp start-list)) nil)
((not (listp a-path)) nil)
((not (listp search-sets)) nil)
((null (get goal-node 'city-name)) nil)
((member (get goal-node 'city-name) start-list)
(progn
(setq visited-ctr (+ 1 visited-ctr))
(setq stored-ctr (+ 1 stored-ctr))
(princ visited-ctr) (princ " visited, ")
(princ expanded-ctr)(princ " expanded, ")
(princ stored-ctr) (princ " stored.")
(print " ")
(print a-path)
(print " ")
)
)
((member (get goal-node 'city-name)
(get-neighbors (car start-list)))
(progn
(setq search-sets
(trim-sets (car start-list)
(sort-set
(add-sets
(get-node
(get goal-node 'city-name)
(get-neighbors
(car start-list)
)
)
(car start-list)
search-sets
)
)
)
)
(bnb goal-node
(get-node-from-set search-sets)
(setq visited-ctr (+ 1 visited-ctr))
(setq expanded-ctr (+ 1 expanded-ctr))
(setq stored-ctr
(+ 1
stored-ctr
(count-states search-sets)
)
)
(car (sort-set search-sets))
search-sets
)
)
)
((not (member (car (sort-set
(get-neighbors
(car start-list))))
a-path))
(progn
(setq search-sets
(trim-sets (car start-list)
(sort-set
(add-sets
(sort-set
(get-neighbors
(car start-list)
)
)
(car start-list)
search-sets
)
)
)
)
(bnb goal-node
(get-node-from-set search-sets)
(setq visited-ctr (+ 1 visited-ctr))
(setq expanded-ctr (+ 1 expanded-ctr))
(setq stored-ctr
(+ 1
stored-ctr
(count-states search-sets)
)
)
(car search-sets)
search-sets
)
)
)
((and (member (car (sort-set
(get-neighbors
(car start-list)
)
)
)
a-path
)
(not (eol-t (get-neighbors
(car start-list)
)
)
)
)
(progn
(setq search-sets
(trim-sets (car start-list)
(sort-set
(add-sets
(cdr (cdr
(sort-set
(get-neighbors
(car start-list)
)
)
)
)
(car start-list)
search-sets
)
)
)
)
(bnb goal-node
(get-node-from-set search-sets)
(setq visited-ctr (+ 1 visited-ctr))
(setq expanded-ctr (+ 1 expanded-ctr))
(setq stored-ctr
(+ 1
stored-ctr
(count-states search-sets)
)
)
(car search-sets)
search-sets
)
)
)
(t(bnb goal-node
(get-node-from-set
(cdr (cdr
(sort-set search-sets))))
(setq visited-ctr (+ 1 visited-ctr))
expanded-ctr
stored-ctr
(car (cdr (cdr
(sort-set search-sets))))
(cdr (cdr (sort-set search-sets)))
)
)
))
;
(load "Lisptst2.txt")
;
