-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsearchProblem.py
259 lines (231 loc) · 8.11 KB
/
searchProblem.py
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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
# searchProblem.py - representations of search problems
# AIFCA Python3 code Version 0.8.1 Documentation at http://aipython.org
# Artificial Intelligence: Foundations of Computational Agents
# http://artint.info
# Copyright David L Poole and Alan K Mackworth 2017.
# This work is licensed under a Creative Commons
# Attribution-NonCommercial-ShareAlike 4.0 International License.
# See: http://creativecommons.org/licenses/by-nc-sa/4.0/deed.en
class Search_problem(object):
"""A search problem consists of:
* a start node
* a neighbors function that gives the neighbors of a node
* a specification of a goal
* a (optional) heuristic function.
The methods must be overridden to define a search problem."""
def start_node(self):
"""returns start node"""
raise NotImplementedError("start_node") # abstract method
def is_goal(self,node):
"""is True if node is a goal"""
raise NotImplementedError("is_goal") # abstract method
def neighbors(self,node):
"""returns a list of the arcs for the neighbors of node"""
raise NotImplementedError("neighbors") # abstract method
def heuristic(self,n):
"""Gives the heuristic value of node n.
Returns 0 if not overridden."""
return 0
class Arc(object):
"""An arc has a from_node and a to_node node and a (non-negative) cost"""
def __init__(self, from_node, to_node, cost=1, action=None):
assert cost >= 0, ("Cost cannot be negative for"+
str(from_node)+"->"+str(to_node)+", cost: "+str(cost))
self.from_node = from_node
self.to_node = to_node
self.action = action
self.cost=cost
def __repr__(self):
"""string representation of an arc"""
if self.action:
return str(self.from_node)+" --"+str(self.action)+"--> "+str(self.to_node)
else:
return str(self.from_node)+" --> "+str(self.to_node)
class Search_problem_from_explicit_graph(Search_problem):
"""A search problem consists of:
* a list or set of nodes
* a list or set of arcs
* a start node
* a list or set of goal nodes
* a dictionary that maps each node into its heuristic value.
"""
def __init__(self, nodes, arcs, start=None, goals=set(), hmap={}):
self.neighs = {}
self.nodes = nodes
for node in nodes:
self.neighs[node]=[]
self.arcs = arcs
for arc in arcs:
self.neighs[arc.from_node].append(arc)
self.start = start
self.goals = goals
self.hmap = hmap
def start_node(self):
"""returns start node"""
return self.start
def is_goal(self,node):
"""is True if node is a goal"""
return node in self.goals
def neighbors(self,node):
"""returns the neighbors of node"""
return self.neighs[node]
def heuristic(self,node):
"""Gives the heuristic value of node n.
Returns 0 if not overridden in the hmap."""
if node in self.hmap:
return self.hmap[node]
else:
return 0
def __repr__(self):
"""returns a string representation of the search problem"""
res=""
for arc in self.arcs:
res += str(arc)+". "
return res
def neighbor_nodes(self,node):
"""returns an iterator over the neighbors of node"""
return (path.to_node for path in self.neighs[node])
class Path(object):
"""A path is either a node or a path followed by an arc"""
def __init__(self,initial,arc=None):
"""initial is either a node (in which case arc is None) or
a path (in which case arc is an object of type Arc)"""
self.initial = initial
self.arc=arc
if arc is None:
self.cost=0
else:
self.cost = initial.cost+arc.cost
def end(self):
"""returns the node at the end of the path"""
if self.arc is None:
return self.initial
else:
return self.arc.to_node
def nodes(self):
"""enumerates the nodes for the path.
This starts at the end and enumerates nodes in the path backwards."""
current = self
while current.arc is not None:
yield current.arc.to_node
current = current.initial
yield current.initial
def initial_nodes(self):
"""enumerates the nodes for the path before the end node.
This starts at the end and enumerates nodes in the path backwards."""
if self.arc is not None:
for nd in self.initial.nodes(): yield nd # could be "yield from"
def __repr__(self):
"""returns a string representation of a path"""
if self.arc is None:
return str(self.initial)
elif self.arc.action:
return (str(self.initial)+"\n --"+str(self.arc.action)
+"--> "+str(self.arc.to_node))
else:
return str(self.initial)+" --> "+str(self.arc.to_node)
problem1 = Search_problem_from_explicit_graph(
{'a','b','c','d','g'},
[Arc('a','b',1), Arc('a','c',3), Arc('b','d',3), Arc('b','c',1),
Arc('c','d',1), Arc('c','g',3), Arc('d','g',1)],
start = 'a',
goals = {'g'})
problem2 = Search_problem_from_explicit_graph(
{'a','b','c','d','e','g','h','j'},
[Arc('a','b',1), Arc('b','c',3), Arc('b','d',1), Arc('d','e',3),
Arc('d','g',1), Arc('a','h',3), Arc('h','j',1)],
start = 'a',
goals = {'g'})
problem3 = Search_problem_from_explicit_graph(
{'a','b','c','d','e','g','h','j'},
[],
start = 'g',
goals = {'k','g'})
acyclic_delivery_problem = Search_problem_from_explicit_graph(
{'mail','ts','o103','o109','o111','b1','b2','b3','b4','c1','c2','c3',
'o125','o123','o119','r123','storage'},
[Arc('ts','mail',6),
Arc('o103','ts',8),
Arc('o103','b3',4),
Arc('o103','o109',12),
Arc('o109','o119',16),
Arc('o109','o111',4),
Arc('b1','c2',3),
Arc('b1','b2',6),
Arc('b2','b4',3),
Arc('b3','b1',4),
Arc('b3','b4',7),
Arc('b4','o109',7),
Arc('c1','c3',8),
Arc('c2','c3',6),
Arc('c2','c1',4),
Arc('o123','o125',4),
Arc('o123','r123',4),
Arc('o119','o123',9),
Arc('o119','storage',7)],
start = 'o103',
goals = {'r123'},
hmap = {
'mail' : 26,
'ts' : 23,
'o103' : 21,
'o109' : 24,
'o111' : 27,
'o119' : 11,
'o123' : 4,
'o125' : 6,
'r123' : 0,
'b1' : 13,
'b2' : 15,
'b3' : 17,
'b4' : 18,
'c1' : 6,
'c2' : 10,
'c3' : 12,
'storage' : 12
}
)
cyclic_delivery_problem = Search_problem_from_explicit_graph(
{'mail','ts','o103','o109','o111','b1','b2','b3','b4','c1','c2','c3',
'o125','o123','o119','r123','storage'},
[ Arc('ts','mail',6), Arc('mail','ts',6),
Arc('o103','ts',8), Arc('ts','o103',8),
Arc('o103','b3',4),
Arc('o103','o109',12), Arc('o109','o103',12),
Arc('o109','o119',16), Arc('o119','o109',16),
Arc('o109','o111',4), Arc('o111','o109',4),
Arc('b1','c2',3),
Arc('b1','b2',6), Arc('b2','b1',6),
Arc('b2','b4',3), Arc('b4','b2',3),
Arc('b3','b1',4), Arc('b1','b3',4),
Arc('b3','b4',7), Arc('b4','b3',7),
Arc('b4','o109',7),
Arc('c1','c3',8), Arc('c3','c1',8),
Arc('c2','c3',6), Arc('c3','c2',6),
Arc('c2','c1',4), Arc('c1','c2',4),
Arc('o123','o125',4), Arc('o125','o123',4),
Arc('o123','r123',4), Arc('r123','o123',4),
Arc('o119','o123',9), Arc('o123','o119',9),
Arc('o119','storage',7), Arc('storage','o119',7)],
start = 'o103',
goals = {'r123'},
hmap = {
'mail' : 26,
'ts' : 23,
'o103' : 21,
'o109' : 24,
'o111' : 27,
'o119' : 11,
'o123' : 4,
'o125' : 6,
'r123' : 0,
'b1' : 13,
'b2' : 15,
'b3' : 17,
'b4' : 18,
'c1' : 6,
'c2' : 10,
'c3' : 12,
'storage' : 12
}
)