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."
"outputs": [
{
"ename": "FileNotFoundError",
"evalue": "[Errno 2] No such file or directory: '/home/apurv/aima-python/aima-data/orings.csv'",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mFileNotFoundError\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m<ipython-input-1-2d1266992fea>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;32mfrom\u001b[0m \u001b[0msearch\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0;34m*\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0;32mfrom\u001b[0m \u001b[0mnotebook\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mpsource\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 3\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;31m# Needed to hide warnings in the matplotlib sections\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mwarnings\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;32m~/aima-python/notebook.py\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mfrom\u001b[0m \u001b[0mgames\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mTicTacToe\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0malphabeta_player\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mrandom_player\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mFig52Extended\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0minfinity\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32mfrom\u001b[0m \u001b[0mlogic\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mparse_definite_clause\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mstandardize_variables\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0munify\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msubst\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mfrom\u001b[0m \u001b[0mlearning\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mDataSet\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 7\u001b[0m \u001b[0;32mfrom\u001b[0m \u001b[0mIPython\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdisplay\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mHTML\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdisplay\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 8\u001b[0m \u001b[0;32mfrom\u001b[0m \u001b[0mcollections\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mCounter\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdefaultdict\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;32m~/aima-python/learning.py\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m 1105\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 1106\u001b[0m orings = DataSet(name='orings', target='Distressed',\n\u001b[0;32m-> 1107\u001b[0;31m attrnames=\"Rings Distressed Temp Pressure Flightnum\")\n\u001b[0m\u001b[1;32m 1108\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 1109\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;32m~/aima-python/learning.py\u001b[0m in \u001b[0;36m__init__\u001b[0;34m(self, examples, attrs, attrnames, target, inputs, values, distance, name, source, exclude)\u001b[0m\n\u001b[1;32m 96\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mexamples\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mparse_csv\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mexamples\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 97\u001b[0m \u001b[0;32melif\u001b[0m \u001b[0mexamples\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 98\u001b[0;31m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mexamples\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mparse_csv\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mopen_data\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mname\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0;34m'.csv'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mread\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 99\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 100\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mexamples\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mexamples\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;32m~/aima-python/utils.py\u001b[0m in \u001b[0;36mopen_data\u001b[0;34m(name, mode)\u001b[0m\n\u001b[1;32m 414\u001b[0m \u001b[0maima_file\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mos\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpath\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mjoin\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0maima_root\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m*\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'aima-data'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mname\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 415\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 416\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mopen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0maima_file\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 417\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 418\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;31mFileNotFoundError\u001b[0m: [Errno 2] No such file or directory: '/home/apurv/aima-python/aima-data/orings.csv'"
]
}
],
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",
"* A\\* 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."
"execution_count": null,
"metadata": {
"collapsed": true
},
"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."
"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",
"execution_count": null,
"metadata": {
"collapsed": true
},
"%psource GraphProblem"
"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."
"execution_count": null,
"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."
"execution_count": null,
"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": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"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."
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"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."
]
},
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
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
"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",
"\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",
"\n",
"# we'll save the initial node colors to a dict to use later\n",
"initial_node_colors = dict(node_colors)\n",
" \n",
"# positions for node labels\n",
"node_label_pos = { k:[v[0],v[1]-10] for k,v in romania_locations.items() }\n",
"\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",
"\n",
" # add edges to the graph\n",
" G.add_edge(node, connection)\n",
" # add distances to edge_labels\n",
" edge_labels[(node, connection)] = distance"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"# initialise a graph\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."
]
},
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
{
"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",
"execution_count": 5,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"%psource SimpleProblemSolvingAgentProgram"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The SimpleProblemSolvingAgentProgram class has six methods: \n",
"\n",
"* `__init__(self, intial_state=None)`: This is the `contructor` of the class and is the first method to be called when the class is instantiated. It takes in a keyword argument, `initial_state` which is initially `None`. The argument `intial_state` represents the state from which the agent starts. \n",
"\n",
"\n",
"* `__call__(self, percept)`: This method updates the `state` of the agent based on its `percept` using the `update_state` method. It then formulates a `goal` with the help of `formulate_goal` method and a `problem` using the `formulate_problem` method and returns a sequence of actions to solve it (using the `search` method).\n",
"\n",
"\n",
"* `update_state(self, percept)`: This method updates the `state` of the agent based on its `percept`. \n",
"\n",
"\n",
"* `formulate_goal(self, state)`: Given a `state` of the agent, this method formulates the `goal` for it.\n",
"\n",
"\n",
"* `formulate_problem(self, state, goal)`: It is used in problem formulation given a `state` and a `goal` for the `agent`.\n",
"\n",
"\n",
"* `search(self, problem)`: This method is used to search a sequence of `actions` to solve a `problem`."
]
},
{
"cell_type": "markdown",
"## SEARCHING ALGORITHMS VISUALIZATION\n",
"In this section, we have visualizations of the following searching algorithms:\n",
"1. Breadth First Tree Search - Implemented\n",
"2. Depth First Tree Search - Implemented\n",
"3. Depth First Graph Search - Implemented\n",
"4. Breadth First Search - Implemented\n",
"5. Best First Graph Search - Implemented\n",
"6. Uniform Cost Search - Implemented\n",
"7. Depth Limited Search\n",
"8. Iterative Deepening Search\n",
"9. A\\*-Search - Implemented\n",
"10. Recursive Best First Search\n",
"\n",
"We add the colors to the nodes to have a nice visualisation when displaying. So, these are the different colors we are using in these visuals:\n",
"* Un-explored nodes - <font color='black'>white</font>\n",
"* Frontier nodes - <font color='orange'>orange</font>\n",
"* Currently exploring node - <font color='red'>red</font>\n",
"* Already explored nodes - <font color='gray'>gray</font>\n",
"Now, we will define some helper methods to display interactive buttons and sliders when visualising search algorithms."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def final_path_colors(problem, solution):\n",
" \"returns a node_colors dict of the final path provided the problem and solution\"\n",
" \n",
" # get initial node colors\n",
" final_colors = dict(initial_node_colors)\n",
" # color all the nodes in solution and starting node to green\n",
" final_colors[problem.initial] = \"green\"\n",
" for node in solution:\n",
" final_colors[node] = \"green\" \n",
" return final_colors\n",
"\n",
"\n",
"def display_visual(user_input, algorithm=None, problem=None):\n",
" if user_input == False:\n",
" def slider_callback(iteration):\n",
" # don't show graph for the first time running the cell calling this function\n",
" try:\n",
" show_map(all_node_colors[iteration])\n",
" except:\n",
" pass\n",
" def visualize_callback(Visualize):\n",
" if Visualize is True:\n",
" button.value = False\n",
" \n",
" global all_node_colors\n",
" \n",
" iterations, all_node_colors, node = algorithm(problem)\n",
" solution = node.solution()\n",
" all_node_colors.append(final_path_colors(problem, solution))\n",
" \n",
" slider.max = len(all_node_colors) - 1\n",
" \n",
" for i in range(slider.max + 1):\n",
" slider.value = i\n",
" \n",
" slider = widgets.IntSlider(min=0, max=1, step=1, value=0)\n",
" slider_visual = widgets.interactive(slider_callback, iteration = slider)\n",
" display(slider_visual)\n",
" button = widgets.ToggleButton(value = False)\n",
" button_visual = widgets.interactive(visualize_callback, Visualize = button)\n",
" display(button_visual)\n",
" \n",
" if user_input == True:\n",
" node_colors = dict(initial_node_colors)\n",
" if algorithm == None:\n",
" algorithms = {\"Breadth First Tree Search\": breadth_first_tree_search,\n",
" \"Depth First Tree Search\": depth_first_tree_search,\n",
" \"Breadth First Search\": breadth_first_search,\n",
" \"Depth First Graph Search\": depth_first_graph_search,\n",
" \"Uniform Cost Search\": uniform_cost_search,\n",
" \"A-star Search\": astar_search}\n",
" algo_dropdown = widgets.Dropdown(description = \"Search algorithm: \",\n",
" options = sorted(list(algorithms.keys())),\n",
" value = \"Breadth First Tree Search\")\n",
" display(algo_dropdown)\n",
" \n",
" def slider_callback(iteration):\n",
" # don't show graph for the first time running the cell calling this function\n",
" try:\n",
" show_map(all_node_colors[iteration])\n",
" except:\n",
" pass\n",
" def visualize_callback(Visualize):\n",
" if Visualize is True:\n",
" button.value = False\n",
" \n",
" problem = GraphProblem(start_dropdown.value, end_dropdown.value, romania_map)\n",
" global all_node_colors\n",
" \n",
" if algorithm == None:\n",
" user_algorithm = algorithms[algo_dropdown.value]\n",
" \n",
"# print(user_algorithm)\n",
"# print(problem)\n",
" \n",
" iterations, all_node_colors, node = user_algorithm(problem)\n",
" solution = node.solution()\n",
" all_node_colors.append(final_path_colors(problem, solution))\n",
" slider.max = len(all_node_colors) - 1\n",
" \n",
" for i in range(slider.max + 1):\n",
" slider.value = i\n",
"# time.sleep(.5)\n",
" start_dropdown = widgets.Dropdown(description = \"Start city: \",\n",
" options = sorted(list(node_colors.keys())), value = \"Arad\")\n",
" display(start_dropdown)\n",
" end_dropdown = widgets.Dropdown(description = \"Goal city: \",\n",
" options = sorted(list(node_colors.keys())), value = \"Fagaras\")\n",
" display(end_dropdown)\n",
" \n",
" button = widgets.ToggleButton(value = False)\n",
" button_visual = widgets.interactive(visualize_callback, Visualize = button)\n",
" display(button_visual)\n",
" \n",
" slider = widgets.IntSlider(min=0, max=1, step=1, value=0)\n",
" slider_visual = widgets.interactive(slider_callback, iteration = slider)\n",
" display(slider_visual)"
]
},
{
"cell_type": "markdown",
"## BREADTH-FIRST TREE SEARCH\n",
"We have a working implementation in search module. But as we want to interact with the graph while it is searching, we need to modify the implementation. Here's the modified breadth first tree search."
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"collapsed": true
},
"source": [
"def tree_search(problem, frontier):\n",
" \"\"\"Search through the successors of a problem to find a goal.\n",
" The argument frontier should be an empty queue.\n",
" Don't worry about repeated paths to a state. [Figure 3.7]\"\"\"\n",
" \n",
" # we use these two variables at the time of visualisations\n",
" iterations = 0\n",
" all_node_colors = []\n",
" node_colors = dict(initial_node_colors)\n",
" \n",
" frontier.append(Node(problem.initial))\n",
" node_colors[Node(problem.initial).state] = \"orange\"\n",
" iterations += 1\n",
" all_node_colors.append(dict(node_colors))\n",
" \n",
" while frontier:\n",
" node = frontier.pop()\n",
" \n",
" # modify the currently searching node to red\n",
" node_colors[node.state] = \"red\"\n",
" iterations += 1\n",
" all_node_colors.append(dict(node_colors))\n",
" \n",
" if problem.goal_test(node.state):\n",
" # modify goal node to green after reaching the goal\n",
" node_colors[node.state] = \"green\"\n",
" iterations += 1\n",
" all_node_colors.append(dict(node_colors))\n",
" return(iterations, all_node_colors, node)\n",
" frontier.extend(node.expand(problem))\n",
" \n",
" for n in node.expand(problem):\n",
" node_colors[n.state] = \"orange\"\n",
" iterations += 1\n",
" all_node_colors.append(dict(node_colors))\n",
" # modify the color of explored nodes to gray\n",
" node_colors[node.state] = \"gray\"\n",
" iterations += 1\n",
" all_node_colors.append(dict(node_colors))\n",
" return None\n",
"\n",
"def breadth_first_tree_search(problem):\n",
" \"Search the shallowest nodes in the search tree first.\"\n",
" iterations, all_node_colors, node = tree_search(problem, FIFOQueue())\n",
" return(iterations, all_node_colors, node)"
]
},
{
"cell_type": "markdown",
"Now, we use ipywidgets to display a slider, a button and our romania map. By sliding the slider we can have a look at all the intermediate steps of a particular search algorithm. By pressing the button **Visualize**, you can see all the steps without interacting with the slider. These two helper functions are the callback functions which are called when we interact with the slider and the button.\n",
"\n"
]
},
{
"cell_type": "code",
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"application/vnd.jupyter.widget-view+json": {
"model_id": "d55324f7343a4c71a9a2d4da6d037037"
}
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"application/vnd.jupyter.widget-view+json": {
"model_id": "b07a3813dd724c51a9b37f646cf2be25"
}
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"all_node_colors = []\n",
"romania_problem = GraphProblem('Arad', 'Fagaras', romania_map)\n",
"display_visual(user_input = False, algorithm = breadth_first_tree_search, problem = romania_problem)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Depth-First Tree Search:\n",
"Now let's discuss another searching algorithm, Depth-First Tree Search."
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": true
},
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
"source": [
"def depth_first_tree_search(problem):\n",
" \"Search the deepest nodes in the search tree first.\"\n",
" # This algorithm might not work in case of repeated paths\n",
" # and may run into an infinite while loop.\n",
" iterations, all_node_colors, node = tree_search(problem, Stack())\n",
" return(iterations, all_node_colors, node)"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"application/vnd.jupyter.widget-view+json": {
"model_id": "523b10cf84e54798a044ee714b864b52"
}
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"application/vnd.jupyter.widget-view+json": {
"model_id": "aecea953f6a448c192ac8e173cf46e35"
}
},
"metadata": {},
"output_type": "display_data"
}
],
"all_node_colors = []\n",
"romania_problem = GraphProblem('Arad', 'Oradea', romania_map)\n",
"display_visual(user_input = False, algorithm = depth_first_tree_search, problem = romania_problem)"
]
},
{
"cell_type": "markdown",
"metadata": {
"## BREADTH-FIRST SEARCH\n",
"Let's change all the node_colors to starting position and define a different problem statement."
]
},
{
"cell_type": "code",
"execution_count": 17,
},
"outputs": [],
"source": [
"def breadth_first_search(problem):\n",
" \"[Figure 3.11]\"\n",
" \n",
" # we use these two variables at the time of visualisations\n",
" iterations = 0\n",
" all_node_colors = []\n",
" node_colors = dict(initial_node_colors)\n",
" \n",
" node = Node(problem.initial)\n",
" \n",
" node_colors[node.state] = \"red\"\n",
" iterations += 1\n",
" all_node_colors.append(dict(node_colors))\n",
" \n",
" if problem.goal_test(node.state):\n",
" node_colors[node.state] = \"green\"\n",
" iterations += 1\n",
" all_node_colors.append(dict(node_colors))\n",
" return(iterations, all_node_colors, node)\n",
" \n",
" frontier = FIFOQueue()\n",
" frontier.append(node)\n",
" \n",
" # modify the color of frontier nodes to blue\n",
" node_colors[node.state] = \"orange\"\n",
" iterations += 1\n",
" all_node_colors.append(dict(node_colors))\n",
" \n",
" explored = set()\n",
" while frontier:\n",
" node = frontier.pop()\n",
" node_colors[node.state] = \"red\"\n",
" iterations += 1\n",
" all_node_colors.append(dict(node_colors))\n",
" \n",
" explored.add(node.state) \n",
" \n",
" for child in node.expand(problem):\n",
" if child.state not in explored and child not in frontier:\n",
" if problem.goal_test(child.state):\n",
" node_colors[child.state] = \"green\"\n",
" iterations += 1\n",
" all_node_colors.append(dict(node_colors))\n",
" return(iterations, all_node_colors, child)\n",
" frontier.append(child)\n",
"\n",
" node_colors[child.state] = \"orange\"\n",
" iterations += 1\n",
" all_node_colors.append(dict(node_colors))\n",
" \n",
" node_colors[node.state] = \"gray\"\n",
" iterations += 1\n",
" all_node_colors.append(dict(node_colors))\n",
" return None"
]
},
{
"cell_type": "code",
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"application/vnd.jupyter.widget-view+json": {
"model_id": "735a3dea191a42b6bd97fdfd337ea3e7"
}
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"application/vnd.jupyter.widget-view+json": {
"model_id": "ef445770d70a4b7c9d1544b98a55ca4d"
}
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"all_node_colors = []\n",
"romania_problem = GraphProblem('Arad', 'Bucharest', romania_map)\n",
"display_visual(user_input = False, algorithm = breadth_first_search, problem = romania_problem)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Depth-First Graph Search: \n",
"Although we have a working implementation in search module, we have to make a few changes in the algorithm to make it suitable for visualization."
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"collapsed": true
},
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
"source": [
"def graph_search(problem, frontier):\n",
" \"\"\"Search through the successors of a problem to find a goal.\n",
" The argument frontier should be an empty queue.\n",
" If two paths reach a state, only use the first one. [Figure 3.7]\"\"\"\n",
" # we use these two variables at the time of visualisations\n",
" iterations = 0\n",
" all_node_colors = []\n",
" node_colors = dict(initial_node_colors)\n",
" \n",
" frontier.append(Node(problem.initial))\n",
" explored = set()\n",
" \n",
" # modify the color of frontier nodes to orange\n",
" node_colors[Node(problem.initial).state] = \"orange\"\n",
" iterations += 1\n",
" all_node_colors.append(dict(node_colors))\n",
" \n",
" while frontier:\n",
" # Popping first node of queue\n",
" node = frontier.pop()\n",
" \n",
" # modify the currently searching node to red\n",
" node_colors[node.state] = \"red\"\n",
" iterations += 1\n",
" all_node_colors.append(dict(node_colors))\n",
" \n",
" if problem.goal_test(node.state):\n",
" # modify goal node to green after reaching the goal\n",
" node_colors[node.state] = \"green\"\n",
" iterations += 1\n",
" all_node_colors.append(dict(node_colors))\n",
" return(iterations, all_node_colors, node)\n",
" \n",
" explored.add(node.state)\n",
" frontier.extend(child for child in node.expand(problem)\n",
" if child.state not in explored and\n",
" child not in frontier)\n",
" \n",
" for n in frontier:\n",
" # modify the color of frontier nodes to orange\n",
" node_colors[n.state] = \"orange\"\n",
" iterations += 1\n",
" all_node_colors.append(dict(node_colors))\n",
"\n",
" # modify the color of explored nodes to gray\n",
" node_colors[node.state] = \"gray\"\n",
" iterations += 1\n",
" all_node_colors.append(dict(node_colors))\n",
" \n",
" return None\n",
"\n",
"\n",
"def depth_first_graph_search(problem):\n",
" \"\"\"Search the deepest nodes in the search tree first.\"\"\"\n",
" iterations, all_node_colors, node = graph_search(problem, Stack())\n",
" return(iterations, all_node_colors, node)"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"application/vnd.jupyter.widget-view+json": {
"model_id": "61149ffbc02846af97170f8975d4f11d"
}
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"application/vnd.jupyter.widget-view+json": {
"model_id": "90b1f8f77fdb4207a3570fbe88a0bdf6"
}
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"all_node_colors = []\n",
"romania_problem = GraphProblem('Arad', 'Bucharest', romania_map)\n",
"display_visual(user_input = False, algorithm = depth_first_graph_search, problem = romania_problem)"
"cell_type": "markdown",
"Let's change all the node_colors to starting position and define a different problem statement."