{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [3. Searching for Solutions](http://artint.info/2e/html/ArtInt2e.Ch3.html)\n",
    "\n",
    "## About\n",
    "This chapter casts the problem of an agent deciding how to solve a goal as the problem of searching to find a path in a graph.\n",
    "\n",
    "You can run each cell by selecting it and pressing *Ctrl+Enter* in Windows or *Shift+Return* in MacOS. Alternatively, you can click the *Play* button in the toolbar, to the left of the stop button. For more information, check out our AISpace2 [Tutorial](https://aispace2.github.io/AISpace2/tutorial.html).\n",
    "\n",
    "Feel free to modify our codes either in this notebook or somewhere outside (e.g. python files in `/aipython/`). If you want to modify our codes outside, you might find [this](https://aispace2.github.io/AISpace2/tutorial.html#tutorial-faq-why-update-aipython-not-reflect) helpful for how your changes can take effect.\n",
    "\n",
    "You need to run the following command to import our pre-defined problems. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Run this to import pre-defined problems\n",
    "from aipython.searchProblem import search_simple1, search_simple2, search_cyclic_delivery, search_acyclic_delivery, search_tree, search_extended_tree, search_cyclic, search_vancouver_neighbour, search_misleading_heuristic, search_multiple_path_pruning, search_module_4_graph, search_module_5_graph, search_bicycle_courier_acyclic, search_bicycle_courier_cyclic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can also define your own problems ([how?](https://aispace2.github.io/AISpace2/tutorial.html#tutorial-search-construct-yourself)). \n",
    "\n",
    "You need to run the following command to import utilities that support your self-defined problems."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Run this to import utilities that support self-defined problems \n",
    "from aipython.searchProblem import Arc, Search_problem_from_explicit_graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [3.5.2 Depth-First Search](http://artint.info/2e/html/ArtInt2e.Ch3.S5.SS2.html)\n",
    "\n",
    "- [Implementation Details](http://artint.info/AIPython/aipython.pdf#page=39) (page 39)\n",
    "\n",
    "In depth-first search, the frontier acts like a LIFO (last-in, first-out) stack of paths. This means that the path selected and removed from the frontier at any time is the last path that was added. Depth-first search is appropriate when space is restricted, or when there are many solutions. On the other hand, depth-first search is not appropriate if it is possible to get stuck into infinite paths or if solutions exist at shallow depths."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from aipython.searchGeneric import Searcher\n",
    "\n",
    "s = Searcher(problem=search_simple2)\n",
    "\n",
    "# Visualization options\n",
    "# For more explanation please visit: https://aispace2.github.io/AISpace2/tutorial.html#tutorial-common-visualization-options\n",
    "s.sleep_time = 0.2 # The time, in seconds, between each step in auto solving\n",
    "s.line_width = 2.0 # The thickness of edges\n",
    "s.text_size = 13 # The fontsize of the text\n",
    "s.detail_level = 2 # 0=no text, 1=truncated text, 2=full text\n",
    "s.show_edge_costs = True\n",
    "s.show_node_heuristics = False\n",
    "# Controls the layout engine used. Either \"force\" for force layout, or \"tree\".\n",
    "s.layout_method = \"force\"\n",
    "# s.layout_method = \"tree\"\n",
    "\n",
    "# Display the widget\n",
    "display(s)\n",
    "s.search()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [3.6.1 A\\* Search](http://artint.info/2e/html/ArtInt2e.Ch3.S6.SS1.html)\n",
    "- [Implementation Details](http://artint.info/AIPython/aipython.pdf#page=41) (page 41)\n",
    "\n",
    "A\\* search uses both path cost and heuristic information in its selection of which path to expand. For each path on the frontier, A\\* uses an estimate of the total path cost from the start node to a goal node constrained to follow that path initially. The estimated total path cost is the sum of the cost of the path found $\\text{c⁢o⁢s⁢t}⁢(p)$ and the heuristic function $h(p)$, which estimates the cost from the end of $p$ to the goal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from aipython.searchGeneric import AStarSearcher\n",
    "\n",
    "s_astar = AStarSearcher(problem=search_simple1)\n",
    "\n",
    "# Visualization options\n",
    "# For more explanation please visit: https://aispace2.github.io/AISpace2/tutorial.html#tutorial-common-visualization-options\n",
    "s_astar.sleep_time = 0.2 # The time, in seconds, between each step in auto solving\n",
    "s_astar.line_width = 2.0 # The thickness of edges\n",
    "s_astar.text_size = 13 # The fontsize of the text\n",
    "s_astar.detail_level = 2 # 0=no text, 1=truncated text, 2=full text\n",
    "s_astar.show_edge_costs = True\n",
    "s_astar.show_node_heuristics = True\n",
    "\n",
    "# Display the widget\n",
    "display(s_astar)\n",
    "s_astar.search()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [3.7.2 A\\* Search with Multiple Path Pruning](http://artint.info/2e/html/ArtInt2e.Ch3.S7.SS2.html)\n",
    "- [Implementation Details](http://artint.info/AIPython/aipython.pdf#page=43) (page 43)\n",
    "\n",
    "There is often more than one path to a node. If only one path is required, a search algorithm can prune from the frontier any path that leads to a node to which it has already found a path. Multiple-path pruning is implemented by maintaining an explored set (traditionally called closed list) of nodes that are at the end of paths that have been expanded. The explored set is initially empty. When a path $⟨n_0,…,n_k⟩$ is selected , if $n_k$ is already in the explored set, the path can be discarded. Otherwise, $n_k$ is added to the explored set, and the algorithm proceeds as before."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from aipython.searchMPP import SearcherMPP\n",
    "\n",
    "s_mpp = SearcherMPP(problem=search_simple1)\n",
    "\n",
    "# Visualization options\n",
    "# For more explanation please visit: https://aispace2.github.io/AISpace2/tutorial.html#tutorial-common-visualization-options\n",
    "s_mpp.sleep_time = 0.2 # The time, in seconds, between each step in auto solving\n",
    "s_mpp.line_width = 2.0 # The thickness of edges\n",
    "s_mpp.text_size = 13 # The fontsize of the text\n",
    "s_mpp.detail_level = 1 # 0=no text, 1=truncated text, 2=full text\n",
    "s_mpp.show_edge_costs = True\n",
    "s_mpp.show_node_heuristics = True\n",
    "\n",
    "# Display the widget\n",
    "display(s_mpp)\n",
    "s_mpp.search()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [3.8.1 Branch-and-bound Search](http://artint.info/2e/html/ArtInt2e.Ch3.S8.SS1.html)\n",
    "- [Implementation Details](http://artint.info/AIPython/aipython.pdf#page=44) (page 44)\n",
    "\n",
    "Depth-first branch-and-bound search is a way to combine the space saving of depth-first search with heuristic information for finding optimal paths. It is particularly applicable when there are many paths to a goal. As in A\\* search, the heuristic function h$⁢(n)$ is non-negative and less than or equal to the cost of a lowest-cost path from n to a goal node.\n",
    "\n",
    "The idea of a branch-and-bound search is to maintain the lowest cost $b$ (\"bound\") of a path to a goal found so far. If the search encounters a path $p$ such that $\\text{c⁢o⁢s⁢t}⁢(p)+h⁢(p)≥b$, path $p$ can be pruned. If a non-pruned path to a goal is found, it must be better than the previous best path. This new solution is remembered and b⁢o⁢u⁢n⁢d is set to the cost of this new solution. The searcher then proceeds to search for a better solution.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from aipython.searchBranchAndBound import DF_branch_and_bound\n",
    "\n",
    "s_dfbb = DF_branch_and_bound(problem=search_simple1)\n",
    "\n",
    "# Visualization options\n",
    "# For more explanation please visit: https://aispace2.github.io/AISpace2/tutorial.html#tutorial-common-visualization-options\n",
    "s_dfbb.sleep_time = 0.2 # The time, in seconds, between each step in auto solving\n",
    "s_dfbb.line_width = 2.0 # The thickness of edges\n",
    "s_dfbb.text_size = 13 # The fontsize of the text\n",
    "s_dfbb.detail_level = 2 # 0=no text, 1=truncated text, 2=full text\n",
    "s_dfbb.show_edge_costs = True\n",
    "s_dfbb.show_node_heuristics = True\n",
    "\n",
    "# Display the widget\n",
    "display(s_dfbb)\n",
    "s_dfbb.search()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}