search.ipynb

   ]
  },
  {
   "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",
    "![simple problem solving agent](images/simple_problem_solving_agent.jpg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "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",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Left\n",
      "Suck\n",
      "Right\n"
     ]
    }
   ],
   "source": [
    "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",
    "\n",
    "a = vacuumAgent(state1)\n",
    "\n",
    "print(a(state6)) \n",
    "print(a(state1))\n",
    "print(a(state3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## SEARCHING ALGORITHMS VISUALIZATION\n",
    "\n",
    "In this section, we have visualizations of the following searching algorithms:\n",
    "\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",
    "9. Greedy Best First Search\n",
    "9. A\\*-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",
   "metadata": {},
   "source": [
    "## 1. BREADTH-FIRST TREE SEARCH\n",
    "\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": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tree_breadth_search_for_vis(problem):\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",
    "    #Adding first node to the queue\n",
    "    frontier = deque([Node(problem.initial)])\n",
    "    \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.popleft()\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",
    "        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",
    "\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",
    "def breadth_first_tree_search(problem):\n",
    "    \"Search the shallowest nodes in the search tree first.\"\n",
    "    iterations, all_node_colors, node = tree_breadth_search_for_vis(problem)\n",
    "    return(iterations, all_node_colors, node)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "all_node_colors = []\n",
    "romania_problem = GraphProblem('Arad', 'Bucharest', 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",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tree_depth_search_for_vis(problem):\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",
    "    #Adding first node to the stack\n",
    "    frontier = [Node(problem.initial)]\n",
    "    \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 stack\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",
    "        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",
    "\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",
    "def depth_first_tree_search(problem):\n",
    "    \"Search the deepest nodes in the search tree first.\"\n",
    "    iterations, all_node_colors, node = tree_depth_search_for_vis(problem)\n",
    "    return(iterations, all_node_colors, node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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_tree_search, \n",
    "               problem=romania_problem)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 3. BREADTH-FIRST GRAPH SEARCH\n",
    "\n",
    "Let's change all the `node_colors` to starting position and define a different problem statement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def breadth_first_search_graph(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 = deque([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.popleft()\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",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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_graph, \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",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def graph_search_for_vis(problem):\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",
    "    \n",
    "    frontier = [(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 stack\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)\n",
    "    return(iterations, all_node_colors, node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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",
   "metadata": {},
   "source": [
    "## 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",
   "execution_count": 22,
   "metadata": {},
   "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",
    "\n",
    "Let's change all the `node_colors` to starting position and define a different problem statement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "def uniform_cost_search_graph(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",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "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_graph, \n",
    "               problem=romania_problem)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 7. DEPTH LIMITED SEARCH\n",
    "\n",
    "Let's change all the 'node_colors' to starting position and define a different problem statement.  \n",
    "Although we have a working implementation, but we need to make changes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def depth_limited_search_graph(problem, limit = -1):\n",
    "    '''\n",
    "    Perform depth first search of graph g.\n",
    "    if limit >= 0, that is the maximum depth of the search.\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 = [Node(problem.initial)]\n",
    "    explored = set()\n",
    "    \n",
    "    cutoff_occurred = False\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",
    "        elif limit >= 0:\n",
    "            cutoff_occurred = True\n",
    "            limit += 1\n",
    "            all_node_color.pop()\n",
    "            iterations -= 1\n",
    "            node_colors[node.state] = \"gray\"\n",
    "\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",
    "            limit -= 1\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 'cutoff' if cutoff_occurred else None\n",
    "\n",
    "\n",
    "def depth_limited_search_for_vis(problem):\n",
    "    \"\"\"Search the deepest nodes in the search tree first.\"\"\"\n",
    "    iterations, all_node_colors, node = depth_limited_search_graph(problem)\n",
    "    return(iterations, all_node_colors, node)     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "all_node_colors = []\n",
    "romania_problem = GraphProblem('Arad', 'Bucharest', romania_map)\n",
    "display_visual(romania_graph_data, user_input=False, \n",
    "               algorithm=depth_limited_search_for_vis, \n",
    "               problem=romania_problem)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 8. ITERATIVE DEEPENING SEARCH\n",
    "\n",
    "Let's change all the 'node_colors' to starting position and define a different problem statement.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "def iterative_deepening_search_for_vis(problem):\n",
    "    for depth in range(sys.maxsize):\n",
    "        iterations, all_node_colors, node=depth_limited_search_for_vis(problem)\n",
    "        if iterations:\n",
    "            return (iterations, all_node_colors, node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "all_node_colors = []\n",
    "romania_problem = GraphProblem('Arad', 'Bucharest', romania_map)\n",
    "display_visual(romania_graph_data, user_input=False, \n",
    "               algorithm=iterative_deepening_search_for_vis, \n",
    "               problem=romania_problem)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 9. GREEDY BEST FIRST SEARCH\n",
    "Let's change all the node_colors to starting position and define a different problem statement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "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",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "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": [
    "## 10. A\\* SEARCH\n",
    "\n",
    "Let's change all the `node_colors` to starting position and define a different problem statement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def astar_search_graph(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"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "all_node_colors = []\n",
    "romania_problem = GraphProblem('Arad', 'Bucharest', romania_map)\n",
    "display_visual(romania_graph_data, user_input=False, \n",
    "               algorithm=astar_search_graph, \n",
    "               problem=romania_problem)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 11. RECURSIVE BEST FIRST SEARCH\n",
    "Let's change all the `node_colors` to starting position and define a different problem statement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "def recursive_best_first_search_for_vis(problem, h=None):\n",
    "    \"\"\"[Figure 3.26] Recursive best-first search\"\"\"\n",
    "    # we use these two variables at the time of visualizations\n",
    "    iterations = 0\n",
    "    all_node_colors = []\n",
    "    node_colors = {k : 'white' for k in problem.graph.nodes()}\n",
    "    \n",
    "    h = memoize(h or problem.h, 'h')\n",
    "    \n",
    "    def RBFS(problem, node, flimit):\n",
    "        nonlocal iterations\n",
    "        def color_city_and_update_map(node, color):\n",
    "            node_colors[node.state] = color\n",
    "            nonlocal iterations\n",
    "            iterations += 1\n",
    "            all_node_colors.append(dict(node_colors))\n",
    "            \n",
    "        if problem.goal_test(node.state):\n",
    "            color_city_and_update_map(node, 'green')\n",
    "            return (iterations, all_node_colors, node), 0  # the second value is immaterial\n",
    "        \n",
    "        successors = node.expand(problem)\n",
    "        if len(successors) == 0:\n",
    "            color_city_and_update_map(node, 'gray')\n",
    "            return (iterations, all_node_colors, None), infinity\n",
    "        \n",
    "        for s in successors:\n",
    "            color_city_and_update_map(s, 'orange')\n",
    "            s.f = max(s.path_cost + h(s), node.f)\n",
    "            \n",
    "        while True:\n",
    "            # Order by lowest f value\n",
    "            successors.sort(key=lambda x: x.f)\n",
    "            best = successors[0]\n",
    "            if best.f > flimit:\n",
    "                color_city_and_update_map(node, 'gray')\n",
    "                return (iterations, all_node_colors, None), best.f\n",
    "            \n",
    "            if len(successors) > 1:\n",
    "                alternative = successors[1].f\n",
    "            else:\n",
    "                alternative = infinity\n",
    "                \n",
    "            node_colors[node.state] = 'gray'\n",
    "            node_colors[best.state] = 'red'\n",
    "            iterations += 1\n",
    "            all_node_colors.append(dict(node_colors))\n",
    "            result, best.f = RBFS(problem, best, min(flimit, alternative))\n",
    "            if result[2] is not None:\n",
    "                color_city_and_update_map(node, 'green')\n",
    "                return result, best.f\n",
    "            else:\n",
    "                color_city_and_update_map(node, 'red')\n",
    "                \n",
    "    node = Node(problem.initial)\n",
    "    node.f = h(node)\n",
    "    \n",
    "    node_colors[node.state] = 'red'\n",
    "    iterations += 1\n",
    "    all_node_colors.append(dict(node_colors))\n",
    "    result, bestf = RBFS(problem, node, infinity)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "all_node_colors = []\n",
    "romania_problem = GraphProblem('Arad', 'Bucharest', romania_map)\n",
    "display_visual(romania_graph_data, user_input=False,\n",
    "               algorithm=recursive_best_first_search_for_vis,\n",
    "               problem=romania_problem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "all_node_colors = []\n",
    "# display_visual(romania_graph_data, user_input=True, algorithm=breadth_first_tree_search)\n",
    "algorithms = {  \"Breadth First Tree Search\": tree_breadth_search_for_vis,\n",
    "                \"Depth First Tree Search\": tree_depth_search_for_vis,\n",
    "                \"Breadth First Search\": breadth_first_search_graph,\n",
    "                \"Depth First Graph Search\": graph_search_for_vis,\n",
    "                \"Best First Graph Search\": best_first_graph_search_for_vis,\n",
    "                \"Uniform Cost Search\": uniform_cost_search_graph,\n",
    "                \"Depth Limited Search\": depth_limited_search_for_vis,\n",
    "                \"Iterative Deepening Search\": iterative_deepening_search_for_vis,\n",
    "                \"Greedy Best First Search\": greedy_best_first_search,\n",
    "                \"A-star Search\": astar_search_graph,\n",
    "                \"Recursive Best First Search\": recursive_best_first_search_for_vis}\n",
    "display_visual(romania_graph_data, algorithm=algorithms, user_input=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## RECURSIVE BEST-FIRST SEARCH\n",
    "Recursive best-first search is a simple recursive algorithm that improves upon heuristic search by reducing the memory requirement.\n",
    "RBFS uses only linear space and it attempts to mimic the operation of standard best-first search.\n",
    "Its structure is similar to recursive depth-first search but it doesn't continue indefinitely down the current path, the `f_limit` variable is used to keep track of the f-value of the best _alternative_ path available from any ancestor of the current node.\n",
    "RBFS remembers the f-value of the best leaf in the forgotten subtree and can decide whether it is worth re-expanding the tree later.\n",
    "<br>\n",
    "However, RBFS still suffers from excessive node regeneration.\n",
    "<br>\n",
    "Let's have a look at the implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
       "   \"http://www.w3.org/TR/html4/strict.dtd\">\n",
       "\n",
       "<html>\n",
       "<head>\n",
       "  <title></title>\n",
       "  <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
       "  <style type=\"text/css\">\n",
       "td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
       "span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
       "pre { line-height: 125%; }\n",
       "body .hll { background-color: #ffffcc }\n",
       "body  { background: #f8f8f8; }\n",
       "body .c { color: #408080; font-style: italic } /* Comment */\n",
       "body .err { border: 1px solid #FF0000 } /* Error */\n",
       "body .k { color: #008000; font-weight: bold } /* Keyword */\n",
       "body .o { color: #666666 } /* Operator */\n",
       "body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
       "body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
       "body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
       "body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
       "body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
       "body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
       "body .gd { color: #A00000 } /* Generic.Deleted */\n",
       "body .ge { font-style: italic } /* Generic.Emph */\n",
       "body .gr { color: #FF0000 } /* Generic.Error */\n",
       "body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
       "body .gi { color: #00A000 } /* Generic.Inserted */\n",
       "body .go { color: #888888 } /* Generic.Output */\n",
       "body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
       "body .gs { font-weight: bold } /* Generic.Strong */\n",
       "body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
       "body .gt { color: #0044DD } /* Generic.Traceback */\n",
       "body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
       "body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
       "body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
       "body .kp { color: #008000 } /* Keyword.Pseudo */\n",
       "body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
       "body .kt { color: #B00040 } /* Keyword.Type */\n",
       "body .m { color: #666666 } /* Literal.Number */\n",
       "body .s { color: #BA2121 } /* Literal.String */\n",
       "body .na { color: #7D9029 } /* Name.Attribute */\n",
       "body .nb { color: #008000 } /* Name.Builtin */\n",
       "body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
       "body .no { color: #880000 } /* Name.Constant */\n",
       "body .nd { color: #AA22FF } /* Name.Decorator */\n",
       "body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
       "body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
       "body .nf { color: #0000FF } /* Name.Function */\n",
       "body .nl { color: #A0A000 } /* Name.Label */\n",
       "body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
       "body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
       "body .nv { color: #19177C } /* Name.Variable */\n",
       "body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
       "body .w { color: #bbbbbb } /* Text.Whitespace */\n",
       "body .mb { color: #666666 } /* Literal.Number.Bin */\n",
       "body .mf { color: #666666 } /* Literal.Number.Float */\n",
       "body .mh { color: #666666 } /* Literal.Number.Hex */\n",
       "body .mi { color: #666666 } /* Literal.Number.Integer */\n",
       "body .mo { color: #666666 } /* Literal.Number.Oct */\n",
       "body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
       "body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
       "body .sc { color: #BA2121 } /* Literal.String.Char */\n",
       "body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
       "body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
       "body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
       "body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
       "body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
       "body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
       "body .sx { color: #008000 } /* Literal.String.Other */\n",
       "body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
       "body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
       "body .ss { color: #19177C } /* Literal.String.Symbol */\n",
       "body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
       "body .fm { color: #0000FF } /* Name.Function.Magic */\n",
       "body .vc { color: #19177C } /* Name.Variable.Class */\n",
       "body .vg { color: #19177C } /* Name.Variable.Global */\n",
       "body .vi { color: #19177C } /* Name.Variable.Instance */\n",
       "body .vm { color: #19177C } /* Name.Variable.Magic */\n",
       "body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
       "\n",
       "  </style>\n",
       "</head>\n",
       "<body>\n",