search.ipynb

   ],
   "source": [
    "astar_search(puzzle, linear).solution()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['LEFT', 'UP', 'UP', 'LEFT', 'DOWN', 'RIGHT', 'DOWN', 'RIGHT']"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "astar_search(puzzle, manhattan).solution()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['LEFT', 'UP', 'UP', 'LEFT', 'DOWN', 'RIGHT', 'DOWN', 'RIGHT']"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "astar_search(puzzle, sqrt_manhattan).solution()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['LEFT', 'UP', 'UP', 'LEFT', 'DOWN', 'RIGHT', 'DOWN', 'RIGHT']"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "astar_search(puzzle, max_heuristic).solution()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Even though all the heuristic functions give the same solution, the difference lies in the computation time.\n",
    "<br>\n",
    "This might make all the difference in a scenario where high computational efficiency is required.\n",
    "<br>\n",
    "Let's define a few puzzle states and time `astar_search` for every heuristic function.\n",
    "We will use the %%timeit magic for this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "puzzle_1 = EightPuzzle((2, 4, 3, 1, 5, 6, 7, 8, 0))\n",
    "puzzle_2 = EightPuzzle((1, 2, 3, 4, 5, 6, 0, 7, 8))\n",
    "puzzle_3 = EightPuzzle((1, 2, 3, 4, 5, 7, 8, 6, 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The default heuristic function is the same as the `linear` heuristic function, but we'll still check both."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "11.3 ms ± 2.28 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "astar_search(puzzle_1)\n",
    "astar_search(puzzle_2)\n",
    "astar_search(puzzle_3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10.7 ms ± 591 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "astar_search(puzzle_1, linear)\n",
    "astar_search(puzzle_2, linear)\n",
    "astar_search(puzzle_3, linear)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8.44 ms ± 870 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "astar_search(puzzle_1, manhattan)\n",
    "astar_search(puzzle_2, manhattan)\n",
    "astar_search(puzzle_3, manhattan)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "91.7 ms ± 1.89 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "astar_search(puzzle_1, sqrt_manhattan)\n",
    "astar_search(puzzle_2, sqrt_manhattan)\n",
    "astar_search(puzzle_3, sqrt_manhattan)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8.53 ms ± 601 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "astar_search(puzzle_1, max_heuristic)\n",
    "astar_search(puzzle_2, max_heuristic)\n",
    "astar_search(puzzle_3, max_heuristic)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can infer that the `manhattan` heuristic function works the fastest.\n",
    "<br>\n",
    "`sqrt_manhattan` has an extra `sqrt` operation which makes it quite a lot slower than the others.\n",
    "<br>\n",
    "`max_heuristic` should have been a bit slower as it calls two functions, but in this case, those values were already calculated which saved some time.\n",
    "Feel free to play around with these functions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## HILL CLIMBING\n",
    "\n",
    "Hill Climbing is a heuristic search used for optimization problems.\n",
    "Given a large set of inputs and a good heuristic function, it tries to find a sufficiently good solution to the problem. \n",
    "This solution may or may not be the global optimum.\n",
    "The algorithm is a variant of generate and test algorithm. \n",
    "<br>\n",
    "As a whole, the algorithm works as follows:\n",
    "- Evaluate the initial state.\n",
    "- If it is equal to the goal state, return.\n",
    "- Find a neighboring state (one which is heuristically similar to the current state)\n",
    "- Evaluate this state. If it is closer to the goal state than before, replace the initial state with this state and repeat these steps.\n",
    "<br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "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",
       "<h2></h2>\n",
       "\n",
       "<div class=\"highlight\"><pre><span></span><span class=\"k\">def</span> <span class=\"nf\">hill_climbing</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"p\">):</span>\n",
       "    <span class=\"sd\">&quot;&quot;&quot;From the initial node, keep choosing the neighbor with highest value,</span>\n",
       "<span class=\"sd\">    stopping when no neighbor is better. [Figure 4.2]&quot;&quot;&quot;</span>\n",
       "    <span class=\"n\">current</span> <span class=\"o\">=</span> <span class=\"n\">Node</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">initial</span><span class=\"p\">)</span>\n",
       "    <span class=\"k\">while</span> <span class=\"bp\">True</span><span class=\"p\">:</span>\n",
       "        <span class=\"n\">neighbors</span> <span class=\"o\">=</span> <span class=\"n\">current</span><span class=\"o\">.</span><span class=\"n\">expand</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"n\">neighbors</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">break</span>\n",
       "        <span class=\"n\">neighbor</span> <span class=\"o\">=</span> <span class=\"n\">argmax_random_tie</span><span class=\"p\">(</span><span class=\"n\">neighbors</span><span class=\"p\">,</span>\n",
       "                                     <span class=\"n\">key</span><span class=\"o\">=</span><span class=\"k\">lambda</span> <span class=\"n\">node</span><span class=\"p\">:</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">value</span><span class=\"p\">(</span><span class=\"n\">node</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">))</span>\n",
       "        <span class=\"k\">if</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">value</span><span class=\"p\">(</span><span class=\"n\">neighbor</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">)</span> <span class=\"o\">&lt;=</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">value</span><span class=\"p\">(</span><span class=\"n\">current</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">):</span>\n",
       "            <span class=\"k\">break</span>\n",
       "        <span class=\"n\">current</span> <span class=\"o\">=</span> <span class=\"n\">neighbor</span>\n",
       "    <span class=\"k\">return</span> <span class=\"n\">current</span><span class=\"o\">.</span><span class=\"n\">state</span>\n",
       "</pre></div>\n",
       "</body>\n",
       "</html>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "psource(hill_climbing)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will find an approximate solution to the traveling salespersons problem using this algorithm.\n",
    "<br>\n",
    "We need to define a class for this problem.\n",
    "<br>\n",
    "`Problem` will be used as a base class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class TSP_problem(Problem):\n",
    "\n",
    "    \"\"\" subclass of Problem to define various functions \"\"\"\n",
    "\n",
    "    def two_opt(self, state):\n",
    "        \"\"\" Neighbour generating function for Traveling Salesman Problem \"\"\"\n",
    "        neighbour_state = state[:]\n",
    "        left = random.randint(0, len(neighbour_state) - 1)\n",
    "        right = random.randint(0, len(neighbour_state) - 1)\n",
    "        if left > right:\n",
    "            left, right = right, left\n",
    "        neighbour_state[left: right + 1] = reversed(neighbour_state[left: right + 1])\n",
    "        return neighbour_state\n",
    "\n",
    "    def actions(self, state):\n",
    "        \"\"\" action that can be excuted in given state \"\"\"\n",
    "        return [self.two_opt]\n",
    "\n",
    "    def result(self, state, action):\n",
    "        \"\"\"  result after applying the given action on the given state \"\"\"\n",
    "        return action(state)\n",
    "\n",
    "    def path_cost(self, c, state1, action, state2):\n",
    "        \"\"\" total distance for the Traveling Salesman to be covered if in state2  \"\"\"\n",
    "        cost = 0\n",
    "        for i in range(len(state2) - 1):\n",
    "            cost += distances[state2[i]][state2[i + 1]]\n",
    "        cost += distances[state2[0]][state2[-1]]\n",
    "        return cost\n",
    "\n",
    "    def value(self, state):\n",
    "        \"\"\" value of path cost given negative for the given state \"\"\"\n",
    "        return -1 * self.path_cost(None, None, None, state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will use cities from the Romania map as our cities for this problem.\n",
    "<br>\n",
    "A list of all cities and a dictionary storing distances between them will be populated."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Arad', 'Bucharest', 'Craiova', 'Drobeta', 'Eforie', 'Fagaras', 'Giurgiu', 'Hirsova', 'Iasi', 'Lugoj', 'Mehadia', 'Neamt', 'Oradea', 'Pitesti', 'Rimnicu', 'Sibiu', 'Timisoara', 'Urziceni', 'Vaslui', 'Zerind']\n"
     ]
    }
   ],
   "source": [
    "distances = {}\n",
    "all_cities = []\n",
    "\n",
    "for city in romania_map.locations.keys():\n",
    "    distances[city] = {}\n",
    "    all_cities.append(city)\n",
    "    \n",
    "all_cities.sort()\n",
    "print(all_cities)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we need to populate the individual lists inside the dictionary with the manhattan distance between the cities."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "for name_1, coordinates_1 in romania_map.locations.items():\n",
    "        for name_2, coordinates_2 in romania_map.locations.items():\n",
    "            distances[name_1][name_2] = np.linalg.norm(\n",
    "                [coordinates_1[0] - coordinates_2[0], coordinates_1[1] - coordinates_2[1]])\n",
    "            distances[name_2][name_1] = np.linalg.norm(\n",
    "                [coordinates_1[0] - coordinates_2[0], coordinates_1[1] - coordinates_2[1]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The way neighbours are chosen currently isn't suitable for the travelling salespersons problem.\n",
    "We need a neighboring state that is similar in total path distance to the current state.\n",
    "<br>\n",
    "We need to change the function that finds neighbors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def hill_climbing(problem):\n",
    "    \n",
    "    \"\"\"From the initial node, keep choosing the neighbor with highest value,\n",
    "    stopping when no neighbor is better. [Figure 4.2]\"\"\"\n",
    "    \n",
    "    def find_neighbors(state, number_of_neighbors=100):\n",
    "        \"\"\" finds neighbors using two_opt method \"\"\"\n",
    "        \n",
    "        neighbors = []\n",
    "        \n",
    "        for i in range(number_of_neighbors):\n",
    "            new_state = problem.two_opt(state)\n",
    "            neighbors.append(Node(new_state))\n",
    "            state = new_state\n",
    "            \n",
    "        return neighbors\n",
    "\n",
    "    # as this is a stochastic algorithm, we will set a cap on the number of iterations\n",
    "    iterations = 10000\n",
    "    \n",
    "    current = Node(problem.initial)\n",
    "    while iterations:\n",
    "        neighbors = find_neighbors(current.state)\n",
    "        if not neighbors:\n",
    "            break\n",
    "        neighbor = argmax_random_tie(neighbors,\n",
    "                                     key=lambda node: problem.value(node.state))\n",
    "        if problem.value(neighbor.state) <= problem.value(current.state):\n",
    "            current.state = neighbor.state\n",
    "        iterations -= 1\n",
    "        \n",
    "    return current.state"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An instance of the TSP_problem class will be created."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tsp = TSP_problem(all_cities)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now generate an approximate solution to the problem by calling `hill_climbing`.\n",
    "The results will vary a bit each time you run it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Arad',\n",
       " 'Timisoara',\n",
       " 'Lugoj',\n",
       " 'Mehadia',\n",
       " 'Drobeta',\n",
       " 'Craiova',\n",
       " 'Pitesti',\n",
       " 'Giurgiu',\n",
       " 'Bucharest',\n",
       " 'Urziceni',\n",
       " 'Eforie',\n",
       " 'Hirsova',\n",
       " 'Vaslui',\n",
       " 'Iasi',\n",
       " 'Neamt',\n",
       " 'Fagaras',\n",
       " 'Rimnicu',\n",
       " 'Sibiu',\n",
       " 'Oradea',\n",
       " 'Zerind']"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hill_climbing(tsp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The solution looks like this.\n",
    "It is not difficult to see why this might be a good solution.\n",
    "<br>\n",
    "![title](images/hillclimb-tsp.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## SIMULATED ANNEALING\n",
    "\n",
    "The intuition behind Hill Climbing was developed from the metaphor of climbing up the graph of a function to find its peak. \n",
    "There is a fundamental problem in the implementation of the algorithm however.\n",
    "To find the highest hill, we take one step at a time, always uphill, hoping to find the highest point, \n",
    "but if we are unlucky to start from the shoulder of the second-highest hill, there is no way we can find the highest one. \n",
    "The algorithm will always converge to the local optimum.\n",
    "Hill Climbing is also bad at dealing with functions that flatline in certain regions.\n",
    "If all neighboring states have the same value, we cannot find the global optimum using this algorithm.\n",
    "<br>\n",
    "<br>\n",
    "Let's now look at an algorithm that can deal with these situations.\n",
    "<br>\n",
    "Simulated Annealing is quite similar to Hill Climbing, \n",
    "but instead of picking the _best_ move every iteration, it picks a _random_ move. \n",
    "If this random move brings us closer to the global optimum, it will be accepted, \n",
    "but if it doesn't, the algorithm may accept or reject the move based on a probability dictated by the _temperature_. \n",
    "When the `temperature` is high, the algorithm is more likely to accept a random move even if it is bad.\n",
    "At low temperatures, only good moves are accepted, with the occasional exception.\n",
    "This allows exploration of the state space and prevents the algorithm from getting stuck at the local optimum.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "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",
       "<h2></h2>\n",
       "\n",
       "<div class=\"highlight\"><pre><span></span><span class=\"k\">def</span> <span class=\"nf\">simulated_annealing</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"p\">,</span> <span class=\"n\">schedule</span><span class=\"o\">=</span><span class=\"n\">exp_schedule</span><span class=\"p\">()):</span>\n",
       "    <span class=\"sd\">&quot;&quot;&quot;[Figure 4.5] CAUTION: This differs from the pseudocode as it</span>\n",
       "<span class=\"sd\">    returns a state instead of a Node.&quot;&quot;&quot;</span>\n",
       "    <span class=\"n\">current</span> <span class=\"o\">=</span> <span class=\"n\">Node</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">initial</span><span class=\"p\">)</span>\n",
       "    <span class=\"k\">for</span> <span class=\"n\">t</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">sys</span><span class=\"o\">.</span><span class=\"n\">maxsize</span><span class=\"p\">):</span>\n",
       "        <span class=\"n\">T</span> <span class=\"o\">=</span> <span class=\"n\">schedule</span><span class=\"p\">(</span><span class=\"n\">t</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">if</span> <span class=\"n\">T</span> <span class=\"o\">==</span> <span class=\"mi\">0</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">return</span> <span class=\"n\">current</span><span class=\"o\">.</span><span class=\"n\">state</span>\n",
       "        <span class=\"n\">neighbors</span> <span class=\"o\">=</span> <span class=\"n\">current</span><span class=\"o\">.</span><span class=\"n\">expand</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"n\">neighbors</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">return</span> <span class=\"n\">current</span><span class=\"o\">.</span><span class=\"n\">state</span>\n",
       "        <span class=\"n\">next_choice</span> <span class=\"o\">=</span> <span class=\"n\">random</span><span class=\"o\">.</span><span class=\"n\">choice</span><span class=\"p\">(</span><span class=\"n\">neighbors</span><span class=\"p\">)</span>\n",
       "        <span class=\"n\">delta_e</span> <span class=\"o\">=</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">value</span><span class=\"p\">(</span><span class=\"n\">next_choice</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">)</span> <span class=\"o\">-</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">value</span><span class=\"p\">(</span><span class=\"n\">current</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">if</span> <span class=\"n\">delta_e</span> <span class=\"o\">&gt;</span> <span class=\"mi\">0</span> <span class=\"ow\">or</span> <span class=\"n\">probability</span><span class=\"p\">(</span><span class=\"n\">math</span><span class=\"o\">.</span><span class=\"n\">exp</span><span class=\"p\">(</span><span class=\"n\">delta_e</span> <span class=\"o\">/</span> <span class=\"n\">T</span><span class=\"p\">)):</span>\n",
       "            <span class=\"n\">current</span> <span class=\"o\">=</span> <span class=\"n\">next_choice</span>\n",
       "</pre></div>\n",
       "</body>\n",
       "</html>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "psource(simulated_annealing)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The temperature is gradually decreased over the course of the iteration.\n",
    "This is done by a scheduling routine.\n",
    "The current implementation uses exponential decay of temperature, but we can use a different scheduling routine instead.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "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",
       "<h2></h2>\n",
       "\n",
       "<div class=\"highlight\"><pre><span></span><span class=\"k\">def</span> <span class=\"nf\">exp_schedule</span><span class=\"p\">(</span><span class=\"n\">k</span><span class=\"o\">=</span><span class=\"mi\">20</span><span class=\"p\">,</span> <span class=\"n\">lam</span><span class=\"o\">=</span><span class=\"mf\">0.005</span><span class=\"p\">,</span> <span class=\"n\">limit</span><span class=\"o\">=</span><span class=\"mi\">100</span><span class=\"p\">):</span>\n",
       "    <span class=\"sd\">&quot;&quot;&quot;One possible schedule function for simulated annealing&quot;&quot;&quot;</span>\n",
       "    <span class=\"k\">return</span> <span class=\"k\">lambda</span> <span class=\"n\">t</span><span class=\"p\">:</span> <span class=\"p\">(</span><span class=\"n\">k</span> <span class=\"o\">*</span> <span class=\"n\">math</span><span class=\"o\">.</span><span class=\"n\">exp</span><span class=\"p\">(</span><span class=\"o\">-</span><span class=\"n\">lam</span> <span class=\"o\">*</span> <span class=\"n\">t</span><span class=\"p\">)</span> <span class=\"k\">if</span> <span class=\"n\">t</span> <span class=\"o\">&lt;</span> <span class=\"n\">limit</span> <span class=\"k\">else</span> <span class=\"mi\">0</span><span class=\"p\">)</span>\n",
       "</pre></div>\n",
       "</body>\n",
       "</html>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "psource(exp_schedule)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we'll define a peak-finding problem and try to solve it using Simulated Annealing.\n",
    "Let's define the grid and the initial state first.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "initial = (0, 0)\n",
    "grid = [[3, 7, 2, 8], [5, 2, 9, 1], [5, 3, 3, 1]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We want to allow only four directions, namely `N`, `S`, `E` and `W`.\n",
    "Let's use the predefined `directions4` dictionary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'E': (1, 0), 'N': (0, 1), 'S': (0, -1), 'W': (-1, 0)}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "directions4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Define a problem with these parameters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "problem = PeakFindingProblem(initial, grid, directions4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll run `simulated_annealing` a few times and store the solutions in a set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "solutions = {problem.value(simulated_annealing(problem)) for i in range(100)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max(solutions)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hence, the maximum value is 9."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's find the peak of a two-dimensional gaussian distribution.\n",
    "We'll use the `gaussian_kernel` function from notebook.py to get the distribution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "grid = gaussian_kernel()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's use the `heatmap` function from notebook.py to plot this."
   ]
  },
  {