Newer
Older
"# Solving problems by Searching\n",
"\n",
"This notebook serves as supporting material for topics covered in **Chapter 3 - Solving Problems by Searching** and **Chapter 4 - Beyond Classical Search** from the book *Artificial Intelligence: A Modern Approach.* This notebook uses implementations from [search.py](https://github.com/aimacode/aima-python/blob/master/search.py) module. Let's start by importing everything from search module."
Aman Deep Singh
a validé
"from notebook import psource\n",
"\n",
"# Needed to hide warnings in the matplotlib sections\n",
"import warnings\n",
"warnings.filterwarnings(\"ignore\")"
"## CONTENTS\n",
"\n",
"* Overview\n",
"* Problem\n",
"* Search Algorithms Visualization\n",
"* Breadth-First Tree Search\n",
"* Breadth-First Search\n",
"* Genetic Algorithm"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## OVERVIEW\n",
"Here, we learn about problem solving. Building goal-based agents that can plan ahead to solve problems, in particular, navigation problem/route finding problem. First, we will start the problem solving by precisely defining **problems** and their **solutions**. We will look at several general-purpose search algorithms. Broadly, search algorithms are classified into two types:\n",
"* **Uninformed search algorithms**: Search algorithms which explore the search space without having any information about the problem other than its definition.\n",
"* Examples:\n",
" 1. Breadth First Search\n",
" 2. Depth First Search\n",
" 3. Depth Limited Search\n",
" 4. Iterative Deepening Search\n",
"\n",
"\n",
"* **Informed search algorithms**: These type of algorithms leverage any information (heuristics, path cost) on the problem to search through the search space to find the solution efficiently.\n",
"* Examples:\n",
" 1. Best First Search\n",
" 2. Uniform Cost Search\n",
" 3. A\\* Search\n",
" 4. Recursive Best First Search\n",
"\n",
"*Don't miss the visualisations of these algorithms solving the route-finding problem defined on Romania map at the end of this notebook.*"
"Let's see how we define a Problem. Run the next cell to see how abstract class `Problem` is defined in the search module."
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
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
" \"http://www.w3.org/TR/html4/strict.dtd\">\n",
"\n",
"<html>\n",
"<head>\n",
" <title></title>\n",
" <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
" <style type=\"text/css\">\n",
"td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
"span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
"pre { line-height: 125%; }\n",
"body .hll { background-color: #ffffcc }\n",
"body { background: #f8f8f8; }\n",
"body .c { color: #408080; font-style: italic } /* Comment */\n",
"body .err { border: 1px solid #FF0000 } /* Error */\n",
"body .k { color: #008000; font-weight: bold } /* Keyword */\n",
"body .o { color: #666666 } /* Operator */\n",
"body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
"body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
"body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
"body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
"body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
"body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
"body .gd { color: #A00000 } /* Generic.Deleted */\n",
"body .ge { font-style: italic } /* Generic.Emph */\n",
"body .gr { color: #FF0000 } /* Generic.Error */\n",
"body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
"body .gi { color: #00A000 } /* Generic.Inserted */\n",
"body .go { color: #888888 } /* Generic.Output */\n",
"body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
"body .gs { font-weight: bold } /* Generic.Strong */\n",
"body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
"body .gt { color: #0044DD } /* Generic.Traceback */\n",
"body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
"body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
"body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
"body .kp { color: #008000 } /* Keyword.Pseudo */\n",
"body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
"body .kt { color: #B00040 } /* Keyword.Type */\n",
"body .m { color: #666666 } /* Literal.Number */\n",
"body .s { color: #BA2121 } /* Literal.String */\n",
"body .na { color: #7D9029 } /* Name.Attribute */\n",
"body .nb { color: #008000 } /* Name.Builtin */\n",
"body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
"body .no { color: #880000 } /* Name.Constant */\n",
"body .nd { color: #AA22FF } /* Name.Decorator */\n",
"body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
"body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
"body .nf { color: #0000FF } /* Name.Function */\n",
"body .nl { color: #A0A000 } /* Name.Label */\n",
"body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
"body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
"body .nv { color: #19177C } /* Name.Variable */\n",
"body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
"body .w { color: #bbbbbb } /* Text.Whitespace */\n",
"body .mb { color: #666666 } /* Literal.Number.Bin */\n",
"body .mf { color: #666666 } /* Literal.Number.Float */\n",
"body .mh { color: #666666 } /* Literal.Number.Hex */\n",
"body .mi { color: #666666 } /* Literal.Number.Integer */\n",
"body .mo { color: #666666 } /* Literal.Number.Oct */\n",
"body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
"body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
"body .sc { color: #BA2121 } /* Literal.String.Char */\n",
"body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
"body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
"body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
"body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
"body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
"body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
"body .sx { color: #008000 } /* Literal.String.Other */\n",
"body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
"body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
"body .ss { color: #19177C } /* Literal.String.Symbol */\n",
"body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
"body .fm { color: #0000FF } /* Name.Function.Magic */\n",
"body .vc { color: #19177C } /* Name.Variable.Class */\n",
"body .vg { color: #19177C } /* Name.Variable.Global */\n",
"body .vi { color: #19177C } /* Name.Variable.Instance */\n",
"body .vm { color: #19177C } /* Name.Variable.Magic */\n",
"body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
"\n",
" </style>\n",
"</head>\n",
"<body>\n",
"<h2></h2>\n",
"\n",
"<div class=\"highlight\"><pre><span></span><span class=\"k\">class</span> <span class=\"nc\">Problem</span><span class=\"p\">(</span><span class=\"nb\">object</span><span class=\"p\">):</span>\n",
"\n",
" <span class=\"sd\">"""The abstract class for a formal problem. You should subclass</span>\n",
"<span class=\"sd\"> this and implement the methods actions and result, and possibly</span>\n",
"<span class=\"sd\"> __init__, goal_test, and path_cost. Then you will create instances</span>\n",
"<span class=\"sd\"> of your subclass and solve them with the various search functions."""</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"fm\">__init__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">initial</span><span class=\"p\">,</span> <span class=\"n\">goal</span><span class=\"o\">=</span><span class=\"bp\">None</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""The constructor specifies the initial state, and possibly a goal</span>\n",
"<span class=\"sd\"> state, if there is a unique goal. Your subclass's constructor can add</span>\n",
"<span class=\"sd\"> other arguments."""</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">initial</span> <span class=\"o\">=</span> <span class=\"n\">initial</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">goal</span> <span class=\"o\">=</span> <span class=\"n\">goal</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">actions</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">state</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Return the actions that can be executed in the given</span>\n",
"<span class=\"sd\"> state. The result would typically be a list, but if there are</span>\n",
"<span class=\"sd\"> many actions, consider yielding them one at a time in an</span>\n",
"<span class=\"sd\"> iterator, rather than building them all at once."""</span>\n",
" <span class=\"k\">raise</span> <span class=\"ne\">NotImplementedError</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">result</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">state</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Return the state that results from executing the given</span>\n",
"<span class=\"sd\"> action in the given state. The action must be one of</span>\n",
"<span class=\"sd\"> self.actions(state)."""</span>\n",
" <span class=\"k\">raise</span> <span class=\"ne\">NotImplementedError</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">goal_test</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">state</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Return True if the state is a goal. The default method compares the</span>\n",
"<span class=\"sd\"> state to self.goal or checks for state in self.goal if it is a</span>\n",
"<span class=\"sd\"> list, as specified in the constructor. Override this method if</span>\n",
"<span class=\"sd\"> checking against a single self.goal is not enough."""</span>\n",
" <span class=\"k\">if</span> <span class=\"nb\">isinstance</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">goal</span><span class=\"p\">,</span> <span class=\"nb\">list</span><span class=\"p\">):</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">is_in</span><span class=\"p\">(</span><span class=\"n\">state</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">goal</span><span class=\"p\">)</span>\n",
" <span class=\"k\">else</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">state</span> <span class=\"o\">==</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">goal</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">path_cost</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">c</span><span class=\"p\">,</span> <span class=\"n\">state1</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"n\">state2</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Return the cost of a solution path that arrives at state2 from</span>\n",
"<span class=\"sd\"> state1 via action, assuming cost c to get up to state1. If the problem</span>\n",
"<span class=\"sd\"> is such that the path doesn't matter, this function will only look at</span>\n",
"<span class=\"sd\"> state2. If the path does matter, it will consider c and maybe state1</span>\n",
"<span class=\"sd\"> and action. The default method costs 1 for every step in the path."""</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">c</span> <span class=\"o\">+</span> <span class=\"mi\">1</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">value</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">state</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""For optimization problems, each state has a value. Hill-climbing</span>\n",
"<span class=\"sd\"> and related algorithms try to maximize this value."""</span>\n",
" <span class=\"k\">raise</span> <span class=\"ne\">NotImplementedError</span>\n",
"</pre></div>\n",
"</body>\n",
"</html>\n"
],
"text/plain": [
"<IPython.core.display.HTML object>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"The `Problem` class has six methods.\n",
"\n",
"* `__init__(self, initial, goal)` : This is what is called a `constructor` and is the first method called when you create an instance of the class. `initial` specifies the initial state of our search problem. It represents the start state from where our agent begins its task of exploration to find the goal state(s) which is given in the `goal` parameter.\n",
"\n",
"\n",
"* `actions(self, state)` : This method returns all the possible actions agent can execute in the given state `state`.\n",
"\n",
"\n",
"* `result(self, state, action)` : This returns the resulting state if action `action` is taken in the state `state`. This `Problem` class only deals with deterministic outcomes. So we know for sure what every action in a state would result to.\n",
"\n",
"\n",
"* `goal_test(self, state)` : Given a graph state, it checks if it is a terminal state. If the state is indeed a goal state, value of `True` is returned. Else, of course, `False` is returned.\n",
"\n",
"\n",
"* `path_cost(self, c, state1, action, state2)` : Return the cost of the path that arrives at `state2` as a result of taking `action` from `state1`, assuming total cost of `c` to get up to `state1`.\n",
"\n",
"\n",
"* `value(self, state)` : This acts as a bit of extra information in problems where we try to optimise a value when we cannot do a goal test."
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## NODE\n",
"\n",
"Let's see how we define a Node. Run the next cell to see how abstract class `Node` is defined in the search module."
]
},
{
"cell_type": "code",
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
" \"http://www.w3.org/TR/html4/strict.dtd\">\n",
"\n",
"<html>\n",
"<head>\n",
" <title></title>\n",
" <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
" <style type=\"text/css\">\n",
"td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
"span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
"pre { line-height: 125%; }\n",
"body .hll { background-color: #ffffcc }\n",
"body { background: #f8f8f8; }\n",
"body .c { color: #408080; font-style: italic } /* Comment */\n",
"body .err { border: 1px solid #FF0000 } /* Error */\n",
"body .k { color: #008000; font-weight: bold } /* Keyword */\n",
"body .o { color: #666666 } /* Operator */\n",
"body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
"body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
"body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
"body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
"body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
"body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
"body .gd { color: #A00000 } /* Generic.Deleted */\n",
"body .ge { font-style: italic } /* Generic.Emph */\n",
"body .gr { color: #FF0000 } /* Generic.Error */\n",
"body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
"body .gi { color: #00A000 } /* Generic.Inserted */\n",
"body .go { color: #888888 } /* Generic.Output */\n",
"body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
"body .gs { font-weight: bold } /* Generic.Strong */\n",
"body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
"body .gt { color: #0044DD } /* Generic.Traceback */\n",
"body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
"body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
"body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
"body .kp { color: #008000 } /* Keyword.Pseudo */\n",
"body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
"body .kt { color: #B00040 } /* Keyword.Type */\n",
"body .m { color: #666666 } /* Literal.Number */\n",
"body .s { color: #BA2121 } /* Literal.String */\n",
"body .na { color: #7D9029 } /* Name.Attribute */\n",
"body .nb { color: #008000 } /* Name.Builtin */\n",
"body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
"body .no { color: #880000 } /* Name.Constant */\n",
"body .nd { color: #AA22FF } /* Name.Decorator */\n",
"body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
"body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
"body .nf { color: #0000FF } /* Name.Function */\n",
"body .nl { color: #A0A000 } /* Name.Label */\n",
"body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
"body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
"body .nv { color: #19177C } /* Name.Variable */\n",
"body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
"body .w { color: #bbbbbb } /* Text.Whitespace */\n",
"body .mb { color: #666666 } /* Literal.Number.Bin */\n",
"body .mf { color: #666666 } /* Literal.Number.Float */\n",
"body .mh { color: #666666 } /* Literal.Number.Hex */\n",
"body .mi { color: #666666 } /* Literal.Number.Integer */\n",
"body .mo { color: #666666 } /* Literal.Number.Oct */\n",
"body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
"body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
"body .sc { color: #BA2121 } /* Literal.String.Char */\n",
"body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
"body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
"body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
"body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
"body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
"body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
"body .sx { color: #008000 } /* Literal.String.Other */\n",
"body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
"body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
"body .ss { color: #19177C } /* Literal.String.Symbol */\n",
"body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
"body .fm { color: #0000FF } /* Name.Function.Magic */\n",
"body .vc { color: #19177C } /* Name.Variable.Class */\n",
"body .vg { color: #19177C } /* Name.Variable.Global */\n",
"body .vi { color: #19177C } /* Name.Variable.Instance */\n",
"body .vm { color: #19177C } /* Name.Variable.Magic */\n",
"body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
"\n",
" </style>\n",
"</head>\n",
"<body>\n",
"<h2></h2>\n",
"\n",
"<div class=\"highlight\"><pre><span></span><span class=\"k\">class</span> <span class=\"nc\">Node</span><span class=\"p\">:</span>\n",
"\n",
" <span class=\"sd\">"""A node in a search tree. Contains a pointer to the parent (the node</span>\n",
"<span class=\"sd\"> that this is a successor of) and to the actual state for this node. Note</span>\n",
"<span class=\"sd\"> that if a state is arrived at by two paths, then there are two nodes with</span>\n",
"<span class=\"sd\"> the same state. Also includes the action that got us to this state, and</span>\n",
"<span class=\"sd\"> the total path_cost (also known as g) to reach the node. Other functions</span>\n",
"<span class=\"sd\"> may add an f and h value; see best_first_graph_search and astar_search for</span>\n",
"<span class=\"sd\"> an explanation of how the f and h values are handled. You will not need to</span>\n",
"<span class=\"sd\"> subclass this class."""</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"fm\">__init__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">state</span><span class=\"p\">,</span> <span class=\"n\">parent</span><span class=\"o\">=</span><span class=\"bp\">None</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"o\">=</span><span class=\"bp\">None</span><span class=\"p\">,</span> <span class=\"n\">path_cost</span><span class=\"o\">=</span><span class=\"mi\">0</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Create a search tree Node, derived from a parent by an action."""</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">state</span> <span class=\"o\">=</span> <span class=\"n\">state</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">parent</span> <span class=\"o\">=</span> <span class=\"n\">parent</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">action</span> <span class=\"o\">=</span> <span class=\"n\">action</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">path_cost</span> <span class=\"o\">=</span> <span class=\"n\">path_cost</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">depth</span> <span class=\"o\">=</span> <span class=\"mi\">0</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">parent</span><span class=\"p\">:</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">depth</span> <span class=\"o\">=</span> <span class=\"n\">parent</span><span class=\"o\">.</span><span class=\"n\">depth</span> <span class=\"o\">+</span> <span class=\"mi\">1</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"fm\">__repr__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">):</span>\n",
" <span class=\"k\">return</span> <span class=\"s2\">"<Node {}>"</span><span class=\"o\">.</span><span class=\"n\">format</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">)</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"fm\">__lt__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">node</span><span class=\"p\">):</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">state</span> <span class=\"o\"><</span> <span class=\"n\">node</span><span class=\"o\">.</span><span class=\"n\">state</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">expand</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">problem</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""List the nodes reachable in one step from this node."""</span>\n",
" <span class=\"k\">return</span> <span class=\"p\">[</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">child_node</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"p\">)</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">action</span> <span class=\"ow\">in</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">actions</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">)]</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">child_node</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">problem</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""[Figure 3.10]"""</span>\n",
" <span class=\"nb\">next</span> <span class=\"o\">=</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">result</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"p\">)</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">Node</span><span class=\"p\">(</span><span class=\"nb\">next</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"p\">,</span>\n",
" <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">path_cost</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">path_cost</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">,</span>\n",
" <span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"nb\">next</span><span class=\"p\">))</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">solution</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Return the sequence of actions to go from the root to this node."""</span>\n",
" <span class=\"k\">return</span> <span class=\"p\">[</span><span class=\"n\">node</span><span class=\"o\">.</span><span class=\"n\">action</span> <span class=\"k\">for</span> <span class=\"n\">node</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">path</span><span class=\"p\">()[</span><span class=\"mi\">1</span><span class=\"p\">:]]</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">path</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Return a list of nodes forming the path from the root to this node."""</span>\n",
" <span class=\"n\">node</span><span class=\"p\">,</span> <span class=\"n\">path_back</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"p\">[]</span>\n",
" <span class=\"k\">while</span> <span class=\"n\">node</span><span class=\"p\">:</span>\n",
" <span class=\"n\">path_back</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">node</span><span class=\"p\">)</span>\n",
" <span class=\"n\">node</span> <span class=\"o\">=</span> <span class=\"n\">node</span><span class=\"o\">.</span><span class=\"n\">parent</span>\n",
" <span class=\"k\">return</span> <span class=\"nb\">list</span><span class=\"p\">(</span><span class=\"nb\">reversed</span><span class=\"p\">(</span><span class=\"n\">path_back</span><span class=\"p\">))</span>\n",
"\n",
" <span class=\"c1\"># We want for a queue of nodes in breadth_first_search or</span>\n",
" <span class=\"c1\"># astar_search to have no duplicated states, so we treat nodes</span>\n",
" <span class=\"c1\"># with the same state as equal. [Problem: this may not be what you</span>\n",
" <span class=\"c1\"># want in other contexts.]</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"fm\">__eq__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">other</span><span class=\"p\">):</span>\n",
" <span class=\"k\">return</span> <span class=\"nb\">isinstance</span><span class=\"p\">(</span><span class=\"n\">other</span><span class=\"p\">,</span> <span class=\"n\">Node</span><span class=\"p\">)</span> <span class=\"ow\">and</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">state</span> <span class=\"o\">==</span> <span class=\"n\">other</span><span class=\"o\">.</span><span class=\"n\">state</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"fm\">__hash__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">):</span>\n",
" <span class=\"k\">return</span> <span class=\"nb\">hash</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">)</span>\n",
"</pre></div>\n",
"</body>\n",
"</html>\n"
],
"text/plain": [
"<IPython.core.display.HTML object>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The `Node` class has nine methods.\n",
"\n",
"* `__init__(self, state, parent, action, path_cost)` : This method creates a node. `parent` represents the node that this is a successor of and `action` is the action required to get from the parent node to this node. `path_cost` is the cost to reach current node from parent node.\n",
"\n",
"* `__repr__(self)` : This returns the state of this node.\n",
"\n",
"* `__lt__(self, node)` : Given a `node`, this method returns `True` if the state of current node is less than the state of the `node`. Otherwise it returns `False`.\n",
"\n",
"* `expand(self, problem)` : This method lists all the neighbouring(reachable in one step) nodes of current node. \n",
"* `child_node(self, problem, action)` : Given an `action`, this method returns the immediate neighbour that can be reached with that `action`.\n",
"\n",
"* `solution(self)` : This returns the sequence of actions required to reach this node from the root node. \n",
"\n",
"* `path(self)` : This returns a list of all the nodes that lies in the path from the root to this node.\n",
"\n",
"* `__eq__(self, other)` : This method returns `True` if the state of current node is equal to the other node. Else it returns `False`.\n",
"\n",
"* `__hash__(self)` : This returns the hash of the state of current node."
]
},
"We will use the abstract class `Problem` to define our real **problem** named `GraphProblem`. You can see how we define `GraphProblem` by running the next cell."
{
"cell_type": "code",
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
" \"http://www.w3.org/TR/html4/strict.dtd\">\n",
"\n",
"<html>\n",
"<head>\n",
" <title></title>\n",
" <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
" <style type=\"text/css\">\n",
"td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
"span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
"pre { line-height: 125%; }\n",
"body .hll { background-color: #ffffcc }\n",
"body { background: #f8f8f8; }\n",
"body .c { color: #408080; font-style: italic } /* Comment */\n",
"body .err { border: 1px solid #FF0000 } /* Error */\n",
"body .k { color: #008000; font-weight: bold } /* Keyword */\n",
"body .o { color: #666666 } /* Operator */\n",
"body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
"body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
"body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
"body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
"body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
"body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
"body .gd { color: #A00000 } /* Generic.Deleted */\n",
"body .ge { font-style: italic } /* Generic.Emph */\n",
"body .gr { color: #FF0000 } /* Generic.Error */\n",
"body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
"body .gi { color: #00A000 } /* Generic.Inserted */\n",
"body .go { color: #888888 } /* Generic.Output */\n",
"body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
"body .gs { font-weight: bold } /* Generic.Strong */\n",
"body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
"body .gt { color: #0044DD } /* Generic.Traceback */\n",
"body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
"body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
"body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
"body .kp { color: #008000 } /* Keyword.Pseudo */\n",
"body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
"body .kt { color: #B00040 } /* Keyword.Type */\n",
"body .m { color: #666666 } /* Literal.Number */\n",
"body .s { color: #BA2121 } /* Literal.String */\n",
"body .na { color: #7D9029 } /* Name.Attribute */\n",
"body .nb { color: #008000 } /* Name.Builtin */\n",
"body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
"body .no { color: #880000 } /* Name.Constant */\n",
"body .nd { color: #AA22FF } /* Name.Decorator */\n",
"body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
"body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
"body .nf { color: #0000FF } /* Name.Function */\n",
"body .nl { color: #A0A000 } /* Name.Label */\n",
"body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
"body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
"body .nv { color: #19177C } /* Name.Variable */\n",
"body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
"body .w { color: #bbbbbb } /* Text.Whitespace */\n",
"body .mb { color: #666666 } /* Literal.Number.Bin */\n",
"body .mf { color: #666666 } /* Literal.Number.Float */\n",
"body .mh { color: #666666 } /* Literal.Number.Hex */\n",
"body .mi { color: #666666 } /* Literal.Number.Integer */\n",
"body .mo { color: #666666 } /* Literal.Number.Oct */\n",
"body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
"body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
"body .sc { color: #BA2121 } /* Literal.String.Char */\n",
"body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
"body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
"body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
"body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
"body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
"body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
"body .sx { color: #008000 } /* Literal.String.Other */\n",
"body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
"body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
"body .ss { color: #19177C } /* Literal.String.Symbol */\n",
"body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
"body .fm { color: #0000FF } /* Name.Function.Magic */\n",
"body .vc { color: #19177C } /* Name.Variable.Class */\n",
"body .vg { color: #19177C } /* Name.Variable.Global */\n",
"body .vi { color: #19177C } /* Name.Variable.Instance */\n",
"body .vm { color: #19177C } /* Name.Variable.Magic */\n",
"body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
"\n",
" </style>\n",
"</head>\n",
"<body>\n",
"<h2></h2>\n",
"\n",
"<div class=\"highlight\"><pre><span></span><span class=\"k\">class</span> <span class=\"nc\">GraphProblem</span><span class=\"p\">(</span><span class=\"n\">Problem</span><span class=\"p\">):</span>\n",
"\n",
" <span class=\"sd\">"""The problem of searching a graph from one node to another."""</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"fm\">__init__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">initial</span><span class=\"p\">,</span> <span class=\"n\">goal</span><span class=\"p\">,</span> <span class=\"n\">graph</span><span class=\"p\">):</span>\n",
" <span class=\"n\">Problem</span><span class=\"o\">.</span><span class=\"fm\">__init__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">initial</span><span class=\"p\">,</span> <span class=\"n\">goal</span><span class=\"p\">)</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">graph</span> <span class=\"o\">=</span> <span class=\"n\">graph</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">actions</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">A</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""The actions at a graph node are just its neighbors."""</span>\n",
" <span class=\"k\">return</span> <span class=\"nb\">list</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">graph</span><span class=\"o\">.</span><span class=\"n\">get</span><span class=\"p\">(</span><span class=\"n\">A</span><span class=\"p\">)</span><span class=\"o\">.</span><span class=\"n\">keys</span><span class=\"p\">())</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">result</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">state</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""The result of going to a neighbor is just that neighbor."""</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">action</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">path_cost</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">cost_so_far</span><span class=\"p\">,</span> <span class=\"n\">A</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"n\">B</span><span class=\"p\">):</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">cost_so_far</span> <span class=\"o\">+</span> <span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">graph</span><span class=\"o\">.</span><span class=\"n\">get</span><span class=\"p\">(</span><span class=\"n\">A</span><span class=\"p\">,</span> <span class=\"n\">B</span><span class=\"p\">)</span> <span class=\"ow\">or</span> <span class=\"n\">infinity</span><span class=\"p\">)</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">find_min_edge</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Find minimum value of edges."""</span>\n",
" <span class=\"n\">m</span> <span class=\"o\">=</span> <span class=\"n\">infinity</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">d</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">graph</span><span class=\"o\">.</span><span class=\"n\">dict</span><span class=\"o\">.</span><span class=\"n\">values</span><span class=\"p\">():</span>\n",
" <span class=\"n\">local_min</span> <span class=\"o\">=</span> <span class=\"nb\">min</span><span class=\"p\">(</span><span class=\"n\">d</span><span class=\"o\">.</span><span class=\"n\">values</span><span class=\"p\">())</span>\n",
" <span class=\"n\">m</span> <span class=\"o\">=</span> <span class=\"nb\">min</span><span class=\"p\">(</span><span class=\"n\">m</span><span class=\"p\">,</span> <span class=\"n\">local_min</span><span class=\"p\">)</span>\n",
"\n",
" <span class=\"k\">return</span> <span class=\"n\">m</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">h</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">node</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""h function is straight-line distance from a node's state to goal."""</span>\n",
" <span class=\"n\">locs</span> <span class=\"o\">=</span> <span class=\"nb\">getattr</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">graph</span><span class=\"p\">,</span> <span class=\"s1\">'locations'</span><span class=\"p\">,</span> <span class=\"bp\">None</span><span class=\"p\">)</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">locs</span><span class=\"p\">:</span>\n",
" <span class=\"k\">if</span> <span class=\"nb\">type</span><span class=\"p\">(</span><span class=\"n\">node</span><span class=\"p\">)</span> <span class=\"ow\">is</span> <span class=\"nb\">str</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span> <span class=\"nb\">int</span><span class=\"p\">(</span><span class=\"n\">distance</span><span class=\"p\">(</span><span class=\"n\">locs</span><span class=\"p\">[</span><span class=\"n\">node</span><span class=\"p\">],</span> <span class=\"n\">locs</span><span class=\"p\">[</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">goal</span><span class=\"p\">]))</span>\n",
"\n",
" <span class=\"k\">return</span> <span class=\"nb\">int</span><span class=\"p\">(</span><span class=\"n\">distance</span><span class=\"p\">(</span><span class=\"n\">locs</span><span class=\"p\">[</span><span class=\"n\">node</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">],</span> <span class=\"n\">locs</span><span class=\"p\">[</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">goal</span><span class=\"p\">]))</span>\n",
" <span class=\"k\">else</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">infinity</span>\n",
"</pre></div>\n",
"</body>\n",
"</html>\n"
],
"text/plain": [
"<IPython.core.display.HTML object>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"Now it's time to define our problem. We will define it by passing `initial`, `goal`, `graph` to `GraphProblem`. So, our problem is to find the goal state starting from the given initial state on the provided graph. Have a look at our romania_map, which is an Undirected Graph containing a dict of nodes as keys and neighbours as values."
"metadata": {
"collapsed": true
},
"romania_map = UndirectedGraph(dict(\n",
" Arad=dict(Zerind=75, Sibiu=140, Timisoara=118),\n",
" Bucharest=dict(Urziceni=85, Pitesti=101, Giurgiu=90, Fagaras=211),\n",
" Craiova=dict(Drobeta=120, Rimnicu=146, Pitesti=138),\n",
" Drobeta=dict(Mehadia=75),\n",
" Eforie=dict(Hirsova=86),\n",
" Fagaras=dict(Sibiu=99),\n",
" Hirsova=dict(Urziceni=98),\n",
" Iasi=dict(Vaslui=92, Neamt=87),\n",
" Lugoj=dict(Timisoara=111, Mehadia=70),\n",
" Oradea=dict(Zerind=71, Sibiu=151),\n",
" Pitesti=dict(Rimnicu=97),\n",
" Rimnicu=dict(Sibiu=80),\n",
" Urziceni=dict(Vaslui=142)))\n",
"\n",
"romania_map.locations = dict(\n",
" Arad=(91, 492), Bucharest=(400, 327), Craiova=(253, 288),\n",
" Drobeta=(165, 299), Eforie=(562, 293), Fagaras=(305, 449),\n",
" Giurgiu=(375, 270), Hirsova=(534, 350), Iasi=(473, 506),\n",
" Lugoj=(165, 379), Mehadia=(168, 339), Neamt=(406, 537),\n",
" Oradea=(131, 571), Pitesti=(320, 368), Rimnicu=(233, 410),\n",
" Sibiu=(207, 457), Timisoara=(94, 410), Urziceni=(456, 350),\n",
" Vaslui=(509, 444), Zerind=(108, 531))"
]
},
{
"cell_type": "markdown",
"metadata": {
"It is pretty straightforward to understand this `romania_map`. The first node **Arad** has three neighbours named **Zerind**, **Sibiu**, **Timisoara**. Each of these nodes are 75, 140, 118 units apart from **Arad** respectively. And the same goes with other nodes.\n",
"\n",
"And `romania_map.locations` contains the positions of each of the nodes. We will use the straight line distance (which is different from the one provided in `romania_map`) between two cities in algorithms like A\\*-search and Recursive Best First Search.\n",
"\n",
"**Define a problem:**\n",
"Hmm... say we want to start exploring from **Arad** and try to find **Bucharest** in our romania_map. So, this is how we do it."
"metadata": {
"collapsed": true
},
"outputs": [],
"romania_problem = GraphProblem('Arad', 'Bucharest', romania_map)"
"### Romania Map Visualisation\n",
"Let's have a visualisation of Romania map [Figure 3.2] from the book and see how different searching algorithms perform / how frontier expands in each search algorithm for a simple problem named `romania_problem`."
"Have a look at `romania_locations`. It is a dictionary defined in search module. We will use these location values to draw the romania graph using **networkx**."
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"{'Arad': (91, 492), 'Bucharest': (400, 327), 'Craiova': (253, 288), 'Drobeta': (165, 299), 'Eforie': (562, 293), 'Fagaras': (305, 449), 'Giurgiu': (375, 270), 'Hirsova': (534, 350), 'Iasi': (473, 506), 'Lugoj': (165, 379), 'Mehadia': (168, 339), 'Neamt': (406, 537), 'Oradea': (131, 571), 'Pitesti': (320, 368), 'Rimnicu': (233, 410), 'Sibiu': (207, 457), 'Timisoara': (94, 410), 'Urziceni': (456, 350), 'Vaslui': (509, 444), 'Zerind': (108, 531)}\n"
]
}
],
"source": [
"romania_locations = romania_map.locations\n",
"print(romania_locations)"
]
},
{
"cell_type": "markdown",
"Let's start the visualisations by importing necessary modules. We use networkx and matplotlib to show the map in the notebook and we use ipywidgets to interact with the map to see how the searching algorithm works."
"metadata": {
"collapsed": true
},
"source": [
"%matplotlib inline\n",
"import networkx as nx\n",
"import matplotlib.pyplot as plt\n",
"from matplotlib import lines\n",
"\n",
"from ipywidgets import interact\n",
"import ipywidgets as widgets\n",
"from IPython.display import display\n",
"import time"
{
"cell_type": "markdown",
"source": [
"Let's get started by initializing an empty graph. We will add nodes, place the nodes in their location as shown in the book, add edges to the graph."
]
},
"metadata": {
"collapsed": true
},
"source": [
"# initialise a graph\n",
"G = nx.Graph()\n",
"\n",
"# use this while labeling nodes in the map\n",
"node_labels = dict()\n",
"# use this to modify colors of nodes while exploring the graph.\n",
"# This is the only dict we send to `show_map(node_colors)` while drawing the map\n",
"node_colors = dict()\n",
"for n, p in romania_locations.items():\n",
" # add nodes from romania_locations\n",
" G.add_node(n)\n",
" # add nodes to node_labels\n",
" node_labels[n] = n\n",
" # node_colors to color nodes while exploring romania map\n",
" node_colors[n] = \"white\"\n",
"# we'll save the initial node colors to a dict to use later\n",
"initial_node_colors = dict(node_colors)\n",
" \n",
"node_label_pos = { k:[v[0],v[1]-10] for k,v in romania_locations.items() }\n",
"# use this while labeling edges\n",
"edge_labels = dict()\n",
"\n",
"# add edges between cities in romania map - UndirectedGraph defined in search.py\n",
"for node in romania_map.nodes():\n",
" connections = romania_map.get(node)\n",
" for connection in connections.keys():\n",
" distance = connections[connection]\n",
" G.add_edge(node, connection)\n",
" # add distances to edge_labels\n",
" edge_labels[(node, connection)] = distance"
]
},
{
"cell_type": "markdown",
"We have completed building our graph based on romania_map and its locations. It's time to display it here in the notebook. This function `show_map(node_colors)` helps us do that. We will be calling this function later on to display the map at each and every interval step while searching, using variety of algorithms from the book."
{
"cell_type": "code",
"execution_count": null,
"metadata": {
},
"outputs": [],
"source": [
"def show_map(node_colors):\n",
" # set the size of the plot\n",
" plt.figure(figsize=(18,13))\n",
" # draw the graph (both nodes and edges) with locations from romania_locations\n",
" nx.draw(G, pos = romania_locations, node_color = [node_colors[node] for node in G.nodes()])\n",
"\n",
" # draw labels for nodes\n",
" node_label_handles = nx.draw_networkx_labels(G, pos = node_label_pos, labels = node_labels, font_size = 14)\n",
" # add a white bounding box behind the node labels\n",
" [label.set_bbox(dict(facecolor='white', edgecolor='none')) for label in node_label_handles.values()]\n",
"\n",
" # add edge lables to the graph\n",
" nx.draw_networkx_edge_labels(G, pos = romania_locations, edge_labels=edge_labels, font_size = 14)\n",
" \n",
" # add a legend\n",
" white_circle = lines.Line2D([], [], color=\"white\", marker='o', markersize=15, markerfacecolor=\"white\")\n",
" orange_circle = lines.Line2D([], [], color=\"orange\", marker='o', markersize=15, markerfacecolor=\"orange\")\n",
" red_circle = lines.Line2D([], [], color=\"red\", marker='o', markersize=15, markerfacecolor=\"red\")\n",
" gray_circle = lines.Line2D([], [], color=\"gray\", marker='o', markersize=15, markerfacecolor=\"gray\")\n",
" green_circle = lines.Line2D([], [], color=\"green\", marker='o', markersize=15, markerfacecolor=\"green\")\n",
" plt.legend((white_circle, orange_circle, red_circle, gray_circle, green_circle),\n",
" ('Un-explored', 'Frontier', 'Currently Exploring', 'Explored', 'Final Solution'),\n",
" numpoints=1,prop={'size':16}, loc=(.8,.75))\n",
" \n",
" # show the plot. No need to use in notebooks. nx.draw will show the graph itself.\n",
" plt.show()"
]
},
{
"cell_type": "markdown",
"source": [
"We can simply call the function with node_colors dictionary object to display it."
]
},
{
"cell_type": "code",
"execution_count": null,
"source": [
"show_map(node_colors)"
]
},
{
"cell_type": "markdown",
"source": [
"Voila! You see, the romania map as shown in the Figure[3.2] in the book. Now, see how different searching algorithms perform with our problem statements."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## SIMPLE PROBLEM SOLVING AGENT PROGRAM\n",
"\n",
"Let us now define a Simple Problem Solving Agent Program. Run the next cell to see how the abstract class `SimpleProblemSolvingAgentProgram` is defined in the search module."
]
},
{
"cell_type": "code",
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
" \"http://www.w3.org/TR/html4/strict.dtd\">\n",
"\n",
"<html>\n",
"<head>\n",
" <title></title>\n",
" <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
" <style type=\"text/css\">\n",
"td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
"span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
"pre { line-height: 125%; }\n",
"body .hll { background-color: #ffffcc }\n",
"body { background: #f8f8f8; }\n",
"body .c { color: #408080; font-style: italic } /* Comment */\n",
"body .err { border: 1px solid #FF0000 } /* Error */\n",
"body .k { color: #008000; font-weight: bold } /* Keyword */\n",
"body .o { color: #666666 } /* Operator */\n",
"body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
"body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
"body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
"body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
"body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
"body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
"body .gd { color: #A00000 } /* Generic.Deleted */\n",
"body .ge { font-style: italic } /* Generic.Emph */\n",
"body .gr { color: #FF0000 } /* Generic.Error */\n",
"body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
"body .gi { color: #00A000 } /* Generic.Inserted */\n",
"body .go { color: #888888 } /* Generic.Output */\n",
"body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
"body .gs { font-weight: bold } /* Generic.Strong */\n",
"body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
"body .gt { color: #0044DD } /* Generic.Traceback */\n",
"body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
"body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
"body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
"body .kp { color: #008000 } /* Keyword.Pseudo */\n",
"body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
"body .kt { color: #B00040 } /* Keyword.Type */\n",
"body .m { color: #666666 } /* Literal.Number */\n",
"body .s { color: #BA2121 } /* Literal.String */\n",
"body .na { color: #7D9029 } /* Name.Attribute */\n",
"body .nb { color: #008000 } /* Name.Builtin */\n",
"body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
"body .no { color: #880000 } /* Name.Constant */\n",
"body .nd { color: #AA22FF } /* Name.Decorator */\n",
"body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
"body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
"body .nf { color: #0000FF } /* Name.Function */\n",
"body .nl { color: #A0A000 } /* Name.Label */\n",
"body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
"body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
"body .nv { color: #19177C } /* Name.Variable */\n",
"body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
"body .w { color: #bbbbbb } /* Text.Whitespace */\n",
"body .mb { color: #666666 } /* Literal.Number.Bin */\n",
"body .mf { color: #666666 } /* Literal.Number.Float */\n",
"body .mh { color: #666666 } /* Literal.Number.Hex */\n",
"body .mi { color: #666666 } /* Literal.Number.Integer */\n",
"body .mo { color: #666666 } /* Literal.Number.Oct */\n",
"body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
"body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
"body .sc { color: #BA2121 } /* Literal.String.Char */\n",
"body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
"body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
"body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
"body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
"body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
"body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
"body .sx { color: #008000 } /* Literal.String.Other */\n",
"body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
"body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
"body .ss { color: #19177C } /* Literal.String.Symbol */\n",
"body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
"body .fm { color: #0000FF } /* Name.Function.Magic */\n",
"body .vc { color: #19177C } /* Name.Variable.Class */\n",
"body .vg { color: #19177C } /* Name.Variable.Global */\n",
"body .vi { color: #19177C } /* Name.Variable.Instance */\n",
"body .vm { color: #19177C } /* Name.Variable.Magic */\n",
"body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
"\n",
" </style>\n",
"</head>\n",
"<body>\n",
"<h2></h2>\n",
"\n",
"<div class=\"highlight\"><pre><span></span><span class=\"k\">class</span> <span class=\"nc\">SimpleProblemSolvingAgentProgram</span><span class=\"p\">:</span>\n",
"\n",
" <span class=\"sd\">"""Abstract framework for a problem-solving agent. [Figure 3.1]"""</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"fm\">__init__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">initial_state</span><span class=\"o\">=</span><span class=\"bp\">None</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""State is an abstract representation of the state</span>\n",
"<span class=\"sd\"> of the world, and seq is the list of actions required</span>\n",
"<span class=\"sd\"> to get to a particular state from the initial state(root)."""</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">state</span> <span class=\"o\">=</span> <span class=\"n\">initial_state</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">seq</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"fm\">__call__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">percept</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""[Figure 3.1] Formulate a goal and problem, then</span>\n",
"<span class=\"sd\"> search for a sequence of actions to solve it."""</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">state</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">update_state</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">,</span> <span class=\"n\">percept</span><span class=\"p\">)</span>\n",
" <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">seq</span><span class=\"p\">:</span>\n",
" <span class=\"n\">goal</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">formulate_goal</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">)</span>\n",
" <span class=\"n\">problem</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">formulate_problem</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">,</span> <span class=\"n\">goal</span><span class=\"p\">)</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">seq</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">search</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"p\">)</span>\n",
" <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">seq</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">None</span>\n",