1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
|
; Winston & Horn (3rd Edition) Chapter 19
; First set up the network
(setf (get 's 'neighbors) '(a d)
(get 'a 'neighbors) '(s b d)
(get 'b 'neighbors) '(a c e)
(get 'c 'neighbors) '(b)
(get 'd 'neighbors) '(s a e)
(get 'e 'neighbors) '(b d f)
(get 'f 'neighbors) '(e))
(setf (get 's 'coordinates) '(0 3)
(get 'a 'coordinates) '(4 6)
(get 'b 'coordinates) '(7 6)
(get 'c 'coordinates) '(11 6)
(get 'd 'coordinates) '(3 0)
(get 'e 'coordinates) '(6 0)
(get 'f 'coordinates) '(11 3))
; The extend function is used everywhere to provide a new queue
(defun extend (path)
(print (reverse path)) ; for observing what is happening
(mapcar #'(lambda (new-node) (cons new-node path))
(remove-if #'(lambda (neighbor) (member neighbor path))
(get (first path) 'neighbors))))
; depth first search
(defun depth-first (start finish &optional (queue (list (list start))))
(cond ((endp queue) nil) ; Queue empty?
((eq finish (first (first queue))) ; finish found?
(reverse (first queue)))
(t (depth-first
start
finish
(append (extend (first queue))
(rest queue))))))
; breadth first search
(defun breadth-first (start finish &optional (queue (list (list start))))
(cond ((endp queue) nil) ; Queue empty?
((eq finish (first (first queue))) ; finish found?
(reverse (first queue)))
(t (breadth-first
start
finish
(append (rest queue)
(extend (first queue)))))))
; best first search
(defun best-first (start finish &optional (queue (list (list start))))
(cond ((endp queue) nil) ; Queue empty?
((eq finish (first (first queue))) ; finish found?
(reverse (first queue)))
(t (best-first
start
finish
(sort (append (extend (first queue))
(rest queue))
#'(lambda (p1 p2) (closerp p1 p2 finish)))))))
(defun square (x) (* x x))
(defun straight-line-distance (node-1 node-2)
(let ((coord-1 (get node-1 'coordinates))
(coord-2 (get node-2 'coordinates)))
(sqrt (float (+ (square (- (first coord-1) (first coord-2)))
(square (- (second coord-1) (second coord-2))))))))
(defun closerp (path-1 path-2 target-node)
(< (straight-line-distance (first path-1) target-node)
(straight-line-distance (first path-2) target-node)))
; hill climb search
(defun hill-climb (start finish &optional (queue (list (list start))))
(cond ((endp queue) nil) ; Queue empty?
((eq finish (first (first queue))) ; finish found?
(reverse (first queue)))
(t (hill-climb
start
finish
(append (sort (extend (first queue))
#'(lambda (p1 p2)
(closerp p1 p2 finish)))
(rest queue))))))
; branch and bound search (shortest length guarenteed)
(defun branch-and-bound (start finish &optional (queue (list (list start))))
(cond ((endp queue) nil) ; Queue empty?
((eq finish (first (first queue))) ; finish found?
(reverse (first queue)))
(t (branch-and-bound
start
finish
(sort (append (extend (first queue))
(rest queue))
#'shorterp)))))
(defun shorterp (path-1 path-2)
(< (path-length path-1) (path-length path-2)))
(defun path-length (path)
(if (endp (rest path))
0
(+ (straight-line-distance (first path) (second path))
(path-length (rest path)))))
; pert chart searching (problem 19-7)
(setf (get 's 'successors) '(a d)
(get 'a 'successors) '(b d)
(get 'b 'successors) '(c e)
(get 'c 'successors) '()
(get 'd 'successors) '(e)
(get 'e 'successors) '(f)
(get 'f 'successors) '())
(setf (get 's 'time-consumed) 3
(get 'a 'time-consumed) 2
(get 'b 'time-consumed) 4
(get 'c 'time-consumed) 3
(get 'd 'time-consumed) 3
(get 'e 'time-consumed) 2
(get 'f 'time-consumed) 1)
(defun pextend (path)
(mapcar #'(lambda (new-node) (cons new-node path))
(remove-if #'(lambda (successor) (member successor path))
(get (first path) 'successors))))
(defun all-paths (start &optional (queue (list (list start))))
(let ((extended (pextend (first queue))))
(cond ((endp extended)
(mapcar #'reverse queue))
(t (all-paths
start
(sort (append extended (rest queue))
#'first-path-incomplete-p))))))
(defun first-path-incomplete-p (p1 p2)
(not (endp (pextend p1))))
; Pert chart searching (problem 19-8)
(defun time-consumed (path)
(if (endp path)
0
(+ (get (first path) 'time-consumed)
(time-consumed (rest path)))))
(defun longerp (p1 p2) (> (time-consumed p1) (time-consumed p2)))
(defun critical-path (start &optional (queue (list (list start))))
(let ((extended (pextend (first queue))))
(cond ((endp extended)
(reverse (first (sort queue #'longerp))))
(t (critical-path
start
(sort (append extended (rest queue))
#'first-path-incomplete-p))))))
|
