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",
"* 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."
"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."
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
{
"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",
"execution_count": 7,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"%psource Node"
]
},
{
"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 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 methods lists all the neighbouring(reachable in one step) nodes of current node. \n",
"\n",
"* `child_node(self, problem, action)` : Given an `action`, this methods 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",
"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."
"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."
"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."
"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."
]
},
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
"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",
"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."
]
},
{
"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",
"* `__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",
"* `update_state(self, percept)`: This method updates the `state` of the agent based on its `percept`.\n",
"\n",
"* `formulate_goal(self, state)`: Given a `state` of the agent, this method formulates the `goal` for it.\n",
"\n",
"* `formulate_problem(self, state, goal)`: It is used in problem formulation given a `state` and a `goal` for the `agent`.\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."
{
"cell_type": "code",
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
"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
},
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
"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",
883
884
885
886
887
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
"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
},
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
"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": {