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."
"from notebook import psource, show_map, final_path_colors, display_visual\n",
"\n",
"# Needed to hide warnings in the matplotlib sections\n",
"import warnings\n",
"warnings.filterwarnings(\"ignore\")"
"## CONTENTS\n",
"\n",
"* Overview\n",
"* Problem\n",
"* Simple Problem Solving Agent\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 a specific kind of problem solving - building goal-based agents that can plan ahead to solve problems. In particular, we examine navigation problem/route finding problem. We must begin by precisely defining **problems** and their **solutions**. We will look at several general-purpose search algorithms.\n",
"\n",
"Search algorithms can be 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",
"* **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",
"*Don't miss the visualisations of these algorithms solving the route-finding problem defined on Romania map at the end of this notebook.*"
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For visualisations, 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. These are imported as required in `notebook.py`."
]
},
{
"cell_type": "code",
"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"
]
},
"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": {},
"outputs": [],
"source": [
"The `Problem` class has six methods.\n",
"\n",
"* `__init__(self, initial, goal)` : This is what is called a `constructor`. It is the first method called when you create an instance of the class as `Problem(initial, goal)`. The variable `initial` specifies the initial state $s_0$ of the search problem. It represents the beginning state. From here, 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)` : Return a boolean for a given state - `True` if it is a goal state, else `False`.\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",
"execution_count": null,
"metadata": {},
"outputs": [],
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The `Node` class has nine methods. The first is the `__init__` method.\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",
"The next 4 methods are specific `Node`-related functions.\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",
"The remaining 4 methods override standards Python functionality for representing an object as a string, the less-than ($<$) operator, the equal-to ($=$) operator, and the `hash` function.\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",
"* `__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": {},
"outputs": [],
"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",
"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. \n",
"\n",
"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**."
"source": [
"romania_locations = romania_map.locations\n",
"print(romania_locations)"
]
},
{
"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
},
"# node colors, node positions and node label positions\n",
"node_colors = {node: 'white' for node in romania_map.locations.keys()}\n",
"node_positions = romania_map.locations\n",
"node_label_pos = { k:[v[0],v[1]-10] for k,v in romania_map.locations.items() }\n",
"edge_weights = {(k, k2) : v2 for k, v in romania_map.graph_dict.items() for k2, v2 in v.items()}\n",
"romania_graph_data = { 'graph_dict' : romania_map.graph_dict,\n",
" 'node_colors': node_colors,\n",
" 'node_positions': node_positions,\n",
" 'node_label_positions': node_label_pos,\n",
" 'edge_weights': edge_weights\n",
" }"
]
},
{
"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": "markdown",
"source": [
"We can simply call the function with node_colors dictionary object to display it."
]
},
{
"cell_type": "code",
"metadata": {
"scrolled": true
},
"source": [
"show_map(romania_graph_data)"
]
},
{
"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": null,
"metadata": {},
"outputs": [],
"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 `initial_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",
"metadata": {},
"source": [
"Let us now define a Simple Problem Solving Agent Program. We will create a simple `vacuumAgent` class which will inherit from the abstract class `SimpleProblemSolvingAgentProgram` and overrides its methods. We will create a simple intelligent vacuum agent which can be in any one of the following states. It will move to any other state depending upon the current state as shown in the picture by arrows:\n",
"\n",
""
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
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
446
447
448
449
450
451
452
453
454
"outputs": [],
"source": [
"class vacuumAgent(SimpleProblemSolvingAgentProgram):\n",
" def update_state(self, state, percept):\n",
" return percept\n",
"\n",
" def formulate_goal(self, state):\n",
" goal = [state7, state8]\n",
" return goal \n",
"\n",
" def formulate_problem(self, state, goal):\n",
" problem = state\n",
" return problem \n",
" \n",
" def search(self, problem):\n",
" if problem == state1:\n",
" seq = [\"Suck\", \"Right\", \"Suck\"]\n",
" elif problem == state2:\n",
" seq = [\"Suck\", \"Left\", \"Suck\"]\n",
" elif problem == state3:\n",
" seq = [\"Right\", \"Suck\"]\n",
" elif problem == state4:\n",
" seq = [\"Suck\"]\n",
" elif problem == state5:\n",
" seq = [\"Suck\"]\n",
" elif problem == state6:\n",
" seq = [\"Left\", \"Suck\"]\n",
" return seq"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now, we will define all the 8 states and create an object of the above class. Then, we will pass it different states and check the output:"
]
},
{
"cell_type": "code",
"state1 = [(0, 0), [(0, 0), \"Dirty\"], [(1, 0), [\"Dirty\"]]]\n",
"state2 = [(1, 0), [(0, 0), \"Dirty\"], [(1, 0), [\"Dirty\"]]]\n",
"state3 = [(0, 0), [(0, 0), \"Clean\"], [(1, 0), [\"Dirty\"]]]\n",
"state4 = [(1, 0), [(0, 0), \"Clean\"], [(1, 0), [\"Dirty\"]]]\n",
"state5 = [(0, 0), [(0, 0), \"Dirty\"], [(1, 0), [\"Clean\"]]]\n",
"state6 = [(1, 0), [(0, 0), \"Dirty\"], [(1, 0), [\"Clean\"]]]\n",
"state7 = [(0, 0), [(0, 0), \"Clean\"], [(1, 0), [\"Clean\"]]]\n",
"state8 = [(1, 0), [(0, 0), \"Clean\"], [(1, 0), [\"Clean\"]]]\n",
"a = vacuumAgent(state1)\n",
"print(a(state6)) \n",
"print(a(state1))\n",
"print(a(state3))"
{
"cell_type": "markdown",
"## SEARCHING ALGORITHMS VISUALIZATION\n",
"In this section, we have visualizations of the following searching algorithms:\n",
"1. Breadth First Tree Search\n",
"2. Depth First Tree Search\n",
"3. Breadth First Search\n",
"4. Depth First Graph Search\n",
"5. Best First Graph Search\n",
"6. Uniform Cost Search\n",
"7. Depth Limited Search\n",
"8. Iterative Deepening Search\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>"
]
},
{
"cell_type": "markdown",
"## 1. 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",
"metadata": {
"collapsed": true
},
"source": [
"def tree_search_for_vis(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 = {k : 'white' for k in problem.graph.nodes()}\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_for_vis(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",
"metadata": {},
"source": [
"all_node_colors = []\n",
"romania_problem = GraphProblem('Arad', 'Fagaras', romania_map)\n",
"a, b, c = breadth_first_tree_search(romania_problem)\n",
"display_visual(romania_graph_data, user_input=False, \n",
" algorithm=breadth_first_tree_search, \n",
" problem=romania_problem)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 2. Depth-First Tree Search:\n",
"Now let's discuss another searching algorithm, Depth-First Tree Search."
]
},
{
"cell_type": "code",
"metadata": {
"collapsed": true
},
"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_for_vis(problem, Stack())\n",
" return(iterations, all_node_colors, node)"
]
},
{
"cell_type": "code",
"metadata": {},
"all_node_colors = []\n",
"romania_problem = GraphProblem('Arad', 'Oradea', romania_map)\n",
"display_visual(romania_graph_data, user_input=False, \n",
" algorithm=depth_first_tree_search, \n",
" problem=romania_problem)"
]
},
{
"cell_type": "markdown",
"metadata": {
"## 3. BREADTH-FIRST GRAPH SEARCH\n",
"Let's change all the `node_colors` to starting position and define a different problem statement."
]
},
{
"cell_type": "code",
},
"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 = {k : 'white' for k in problem.graph.nodes()}\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",
"metadata": {},
"source": [
"all_node_colors = []\n",
"romania_problem = GraphProblem('Arad', 'Bucharest', romania_map)\n",
"display_visual(romania_graph_data, user_input=False, \n",
" algorithm=breadth_first_search, \n",
" problem=romania_problem)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 4. 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",
"metadata": {
"collapsed": true
},
"def graph_search_for_vis(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 = {k : 'white' for k in problem.graph.nodes()}\n",
741
742
743
744
745
746
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
780
781
782
783
784
785
786
" \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_for_vis(problem, Stack())\n",
" return(iterations, all_node_colors, node)"
]
},
{
"cell_type": "code",
"metadata": {},
"source": [
"all_node_colors = []\n",
"romania_problem = GraphProblem('Arad', 'Bucharest', romania_map)\n",
"display_visual(romania_graph_data, user_input=False, \n",
" algorithm=depth_first_graph_search, \n",
" problem=romania_problem)"
"cell_type": "markdown",
"## 5. BEST FIRST SEARCH\n",
"\n",
"Let's change all the `node_colors` to starting position and define a different problem statement."
]
},
{
"cell_type": "code",
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def best_first_graph_search_for_vis(problem, f):\n",
" \"\"\"Search the nodes with the lowest f scores first.\n",
" You specify the function f(node) that you want to minimize; for example,\n",
" if f is a heuristic estimate to the goal, then we have greedy best\n",
" first search; if f is node.depth then we have breadth-first search.\n",
" There is a subtlety: the line \"f = memoize(f, 'f')\" means that the f\n",
" values will be cached on the nodes as they are computed. So after doing\n",
" a best first search you can examine the f values of the path returned.\"\"\"\n",
" \n",
" # we use these two variables at the time of visualisations\n",
" iterations = 0\n",
" all_node_colors = []\n",
" node_colors = {k : 'white' for k in problem.graph.nodes()}\n",
" \n",
" f = memoize(f, 'f')\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 = PriorityQueue(min, f)\n",
" frontier.append(node)\n",
" \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",
" \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",
" explored.add(node.state)\n",
" for child in node.expand(problem):\n",
" if child.state not in explored and child not in frontier:\n",
" frontier.append(child)\n",
" node_colors[child.state] = \"orange\"\n",
" iterations += 1\n",
" all_node_colors.append(dict(node_colors))\n",
" elif child in frontier:\n",
" incumbent = frontier[child]\n",
" if f(child) < f(incumbent):\n",
" del frontier[incumbent]\n",
" frontier.append(child)\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": "markdown",
"metadata": {},
"source": [
"## 6. UNIFORM COST SEARCH\n",
"Let's change all the `node_colors` to starting position and define a different problem statement."
"metadata": {
"collapsed": true
},
"def uniform_cost_search(problem):\n",
" \"[Figure 3.14]\"\n",
" #Uniform Cost Search uses Best First Search algorithm with f(n) = g(n)\n",
" iterations, all_node_colors, node = best_first_graph_search_for_vis(problem, lambda node: node.path_cost)\n",
" return(iterations, all_node_colors, node)\n"
"cell_type": "code",
"all_node_colors = []\n",
"romania_problem = GraphProblem('Arad', 'Bucharest', romania_map)\n",
"display_visual(romania_graph_data, user_input=False, \n",
" algorithm=uniform_cost_search, \n",
" problem=romania_problem)"
"cell_type": "markdown",
"metadata": {},
"Let's change all the node_colors to starting position and define a different problem statement."
]
},
{
"cell_type": "code",
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def greedy_best_first_search(problem, h=None):\n",
" \"\"\"Greedy Best-first graph search is an informative searching algorithm with f(n) = h(n).\n",
" You need to specify the h function when you call best_first_search, or\n",
" else in your Problem subclass.\"\"\"\n",
" h = memoize(h or problem.h, 'h')\n",
" iterations, all_node_colors, node = best_first_graph_search_for_vis(problem, lambda n: h(n))\n",
" return(iterations, all_node_colors, node)\n"
]
},
{
"cell_type": "code",
"metadata": {},
"all_node_colors = []\n",
"romania_problem = GraphProblem('Arad', 'Bucharest', romania_map)\n",
"display_visual(romania_graph_data, user_input=False, \n",
" algorithm=greedy_best_first_search, \n",
" problem=romania_problem)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's change all the `node_colors` to starting position and define a different problem statement."
]
},
{
"cell_type": "code",
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def astar_search(problem, h=None):\n",
" \"\"\"A* search is best-first graph search with f(n) = g(n)+h(n).\n",
" You need to specify the h function when you call astar_search, or\n",
" else in your Problem subclass.\"\"\"\n",
" h = memoize(h or problem.h, 'h')\n",
" iterations, all_node_colors, node = best_first_graph_search_for_vis(problem, \n",
" lambda n: n.path_cost + h(n))\n",
" return(iterations, all_node_colors, node)\n"
"source": [
"all_node_colors = []\n",
"romania_problem = GraphProblem('Arad', 'Bucharest', romania_map)\n",