Solving Travelling Salesperson problem by using Simulated Annealing

tsp_simulated_annealing.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Travelling Salesperson Problem using Simulated Annealing\n",
    "#### By Pravesh Koirala"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "\n",
    "TSP is a famous problem in computer science. Simply stated, given a list of cities, TSP asks whether it is possible to visit each of the cities exactly ones so as to minimize the overall distance of travel? There's more to TSP than is stated. For details, one can start from [Wikipedia](https://en.wikipedia.org/wiki/Travelling_salesman_problem)\n",
    "\n",
    "It is impossible to solve TSP for very large number of cities as the complexity increases exponentially. But TSP can be solved to obtain an \"accetable\" solution by using heuristics in a reasonable time. \n",
    "\n",
    "In this notebook, we will use Simulated Annealing to solve TSP."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Define the system\n",
    "\n",
    "There will be N number of points where each point defines a city to visit. We will choose our starting city randomly and then walk through all of the cities and return to the starting point such that no intermediate nodes are visited twice.\n",
    "\n",
    "e.g.\n",
    "Suppose four points A(0,0), B(1,-1), C(1, 1) and D(0,1)\n",
    "\n",
    "A walk can be ABCDA or ACBDA or ADCBA.. the start and end point both being A."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Simulated annealing\n",
    "\n",
    "The algorithm that we use here is called simulated annealing. It is a meta heuristics algorithm that can often provide solution to search problems having a very large search space. Simulated Annealing is not guranteed to converge i.e. provide an optimum solution. However, for problems like TSP where a sub-optimal solution is acceptable, simulated annealing works perfectly.\n",
    "\n",
    "### Neighboring state\n",
    "\n",
    "SA begins with an initial state. Each state has a certain configuration and cost. New state can be generated by varying the configuration of a previous state. Thusly generated new state is called a neighboring state of the original state. For example, the walk above i.e. ABCDA is one state. If we vary the order of any two cities, it becomes a new state. So, ACBDA is a neighboring state of ABCDA achieved by swapping states B and C.\n",
    "\n",
    "### Accepting new state\n",
    "\n",
    "As is mentioned, each state has a cost function that gives how much desirable the state is. If, a neighbor state has low cost than that of the original state, the neighbor state is more desirable and is thus selected as new solution.\n",
    "\n",
    "However, it often happens that no neighboring state of an original state is more desirable than that state. Such an state is called a **minima**. If, the minima is desirable than any other possible states of the system, then that is called a **Global minima**. But if it is not, then such minima is called a **Local minima**. In optimization problems such as TSP, we avoid the local minima as much as possible. For that to happen, we have to sometimes compromise i.e. we have to accept a neighbor of the state even if the neighbor is less desirable than original state.\n",
    "\n",
    "The probability that we will choose a less desirable neighboring state is often called **acceptance probability** which is the function of the cost difference between the state and its neighbor and an additional parameter called **Temperature**. Concretely, the acceptance probability is calculated as \n",
    "\n",
    "$$\\Large \\begin {equation} p = e^{-\\Delta c \\over T} \\end {equation}$$\n",
    "\n",
    "Where, c is the cost difference and T is the temperature.\n",
    "\n",
    "As can be seen, the temperature is a parameter that, if increased, increases the probability of accepting sub optimal neighboring states. While this is perfectly alright at the start of the algorithm, we want to make it difficult to accept less desirable neighboring states as the algorithm progresses. For this reason, we will decrease the temperature of the system as the algorithm progresses (once every 500 iteration in this example)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Programming the system\n",
    "\n",
    "### Point class\n",
    "A point class essentially emulates a city. It is a (x,y) tuple in euclidean space that has some utility functions like distance (which gives its euclidean cost with another point).\n",
    "\n",
    "### Walk class\n",
    "A walk is a list of points such that the first and last points of the list are the same and the rest of the points appear exactly once in the walk.\n",
    "\n",
    "The cost function of the walk if the sum of distance between each two consecutive points in the list. For example, if the walk is \"ABCA\" then the cost of the walk is the sum of distance between AB, BC, and CA"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Point:\n",
    "    def __init__(self, x, y):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        \n",
    "    def __eq__(self, p):\n",
    "        return self.x == p.x and self.y == p.y\n",
    "    \n",
    "    def distance(self, p):\n",
    "        return ((self.x - p.x)**2 + (self.y - p.y)**2) ** 0.5\n",
    "    \n",
    "    def __str__(self):\n",
    "        return \"(%d, %d)\" % (self.x, self.y)\n",
    "\n",
    "class Walk:\n",
    "    def __init__(self, list_points):\n",
    "        self.l = list_points\n",
    "    \n",
    "    def cost(self):\n",
    "        if hasattr(self, \"_cost\"): \n",
    "            return self._cost\n",
    "        c = 0\n",
    "        for i in range(len(self.l)-1):\n",
    "            c += self.l[i].distance(self.l[i+1])\n",
    "        \n",
    "        self._cost = c\n",
    "        return c\n",
    "    \n",
    "    def __str__(self):\n",
    "        return \"\\n\".join([str(i) for i in self.l])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem variables\n",
    "\n",
    "**Number of cities : N**\n",
    "This is the number of points that are going to be in our problem.\n",
    "\n",
    "**The grid : g**\n",
    "What the grid variable means is.. any point (x,y) must lie inside the grid. That is to say, $0 \\leq x \\leq g$ and $0 \\leq y \\leq g$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# define number of initial points\n",
    "N = 15\n",
    "# define the rectangular grid\n",
    "g = 20 # 20x20 grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Initialization\n",
    "\n",
    "For SA, we need an initial state. We achieve this by the *getRandomWalk* function. This function calls *getRandomPoint* function repeatedly to get _N_ unique points in the grid. Once the list is obtained, a new *Walk* object can be created by first appending the first element of the list to the last and then passing the resulting list to the Walk class.\n",
    "\n",
    "This Walk object acts as our initial state. This state can be visualized by plotting it with Matplotlib."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Cost of initial state: 161.91\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "random.seed(100)\n",
    "\n",
    "def getRandomPoint(initial_points):\n",
    "    if not initial_points: initial_points = []\n",
    "    while True:\n",
    "        x = random.randint(0, g-1)\n",
    "        y = random.randint(0, g-1)\n",
    "        p = Point(x, y)\n",
    "        if any([x == p for x in initial_points]):\n",
    "            continue\n",
    "        return p\n",
    "\n",
    "def getRandomWalk():\n",
    "    initial_points = []\n",
    "    for i in range(N):\n",
    "        p = getRandomPoint(initial_points)\n",
    "        initial_points.append(p)\n",
    "    initial_points.append(initial_points[0])\n",
    "    return Walk(initial_points)\n",
    "\n",
    "current_walk = getRandomWalk()\n",
    "\n",
    "print \"Cost of initial state: %.2f\" % current_walk.cost()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXIAAAEACAYAAACuzv3DAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XtYlWW6+PEvIAdFQ0DFQ2EKjgfGrFEhd1qEWmnb086c\nmt2kgqK2R6ffrsaxmMQmrZl0mqlGQ0RL93SwctJijVooU04matp4RMRTZiGCIB4AgfX7g4MLWMA6\nvMfF/bkuLxfvYr3vA611d3u/9/M8IIQQQgghhBBCCCGEEEIIIYQQQgghhBBCCKGoW4DtwCHgIDCv\n5ngI8BlwDNgKdNRldEIIIVrUFbi95nF7IBvoD/wR+E3N8fnAy9oPTQghhCs+BkYBR4GwmmNda74W\nQghhcLcCp4EOwEWb414NvhZCCGFA7YG9wMSarxsG7kJthyOEEKJWGwe+xxf4CFhHdWkFII/qksqP\nQDfgfMMXRUREWHNzcxUaphBCtBq5QKQzL/Bu4XkvIA04DPzZ5vgmYGrN46ncCPA3RpKbi9VqlT8K\n/Vm4cKHuY/CkP/L7lN+nUf8AEc4EcWg5I78LeAz4N7Cv5tgCqrtU1gMJwClgirMXFkIIoYyWAvkO\nms7aRyk8FiGEEC5oqbQiDCI2NlbvIXgU+X0qS36f+vJS8dzWmnqPEEIIB3l5eYGTsVkyciGEMDkJ\n5EIIYXKO9JELF2VYLHy4ciWUl4OfH5MTExk5dqzewxI6k/eFUJoEcpVkWCysSUpibFlZ3bE1SUkA\n8qFtxeR9IdQgNztVMmfiREbk5DQ6vrGsjMS779ZhRMIIVn7xBRP8/Rsd39GnD8s/bjSvTrRCrtzs\nlIxcLeXldg/7BgQQEBLCtQsXKC0o4Fp+PtdLSuqeb9OuHW07dyagUyfadupEQOfO1X/XfO3t66vV\nTyBU0P7YMbjYeI05axPvFyEcIYFcLX5+dg/fFBnJXUuX1jtWUVpaF9RLL1y48feFC1z+7jsu7NvH\ntQsXKCsooE1gYL1AX/u47uuaY7433VT7f3ZhJE38j9irifeLEI6QQK6SyYmJjWqh6f7+xCcmNvre\nNgEBtO/Rg/Y9ejR7TmtVFWXFxZTm51dn9DVB/2peHoUHD9bL8ivLyggIDaWtbUZvm+nb/O0jQUQT\n53bsoGd+Pp8A42yON/W+EMJRUiNXUYbFwkcrV2ItL8fLz4+HNOxOaC7Lt31cl+XblHHsZfkBnTrh\nFxQkWb6Lzm7bRlZyMiP+8hf+/cMPur0vhPG5UiOXQN7KNZXlX7tw4cax2iy/tLQus5cs33GnN29m\n75IlxK5YQUhUlN7DEQYngVyoypEsv7SggNILFxpl+Q2DfmvJ8k9s3Mi3r75KbEoKwX376j0cYQIS\nyIUhNJvl1wb9hlm+baD3kCw/Z/16DqWkcG9qKkG9e+s9HGESEsiF6Xhqln907Vqy160jLi2NDuHh\nuo5FmIvhAvnsCRNk+rFQhJGy/Jam2B9KTSV3wwZGpqUR2L27kr8G0QoYLpD/bcAALP7+TH/xRQnm\nQjNqZvn2ptjXvsfjxozhwBtvcGbrVuLS0mjXpYuOvwVhVoYM5CDTj4UxuZLl/y03l0nt2jU6144+\nfZg5fDg/fPUVcampBISG6vATCU9g2Cn6ZRcuYLVada9bCmHLy9ubgOBgAoKD6fiTnzT7vbVZ/qeP\nPgoFBY2ev5STQ56/PyNXr8a/Y0e1hiyEXZqsR37pu++wTJpE7oYNVNr8k1QIs6idfesbEmL3+eul\npcStWiVBXOhC9UCe7u/PrOXLGTx/Pme2bmXj6NEcWL6c0sJCtS8thOImJyZiabB64YfFxcQvXYpf\nhw46jUq0dqrWyP/7ttuY/tJL9W50Fufmkr1uHae3bCF89Gj6Pf44QZGRKg5DCGVlWCx8mJLChb17\nqSgrY9by5Tzw8MN6D0t4CMPd7MyYMYO41FS7T5YWFpLz/vvkvPcewf360W/qVLoOGyZ1dGF4lWVl\nfPnkk3j7+VFVXk7XYcPo9/jjeg9LeAjDBfK/x8UxMSOj2W+qLCvjlMVC9tq1WK1W+j3+OLc++CA+\ndhbfF0JvFVev8s+5cwkICWHYkiUUHz9O5pw5jNu8mTYBAXoPT3gAVwK5qjXysuJiym02TbDHx9+f\niEmTGLNhg9TRhaFdv3yZ7bNmEditG8NefhlvX1+C+/cndNAgjq9fr/fwRCumaiAP6t2b4txch77X\ny8uLrsOGce+bbzJyzRqunT/PJw8+yK7nn6f4+HE1hylEi8qKishISKBjnz7EvPAC3j4+dc8NnD2b\nI6tXU1FaquMIRWumbiCPiOCSg4G84euik5MZl55Ou27dyEhIYPusWfzw1VfI+i1Ca6WFhWTEx9Nl\n8GCG/O53eHnX/9hIVi70pmqN/FBqKtcKChg8f75bJ5I6utDLtfx8MuLjuWX0aG6bO7fJm/EXjxyR\nWrlQhOFq5EGRkYqURaSOLvRw5dw5Pnv8cXqNG8egefOa7aiSrFzoSfVAfunECcXOJ3V0oZWSM2f4\nfNo0fvLoo0Q5uJ+m1MqFXlQN5IHduzvUueIKqaMLtRSfOEHG9OkMmDHDqf5wycqFXlQN5F7e3k51\nrrgiICSEgXPmMGHrVsIfeIB9r7wi67oIlxUdO8a2+HhumzuXPlOmOP16ycqFHlRfa8XVzhVnSR1d\nuKvw0CG2zZjBz+bPp/fEiS6dQ7JyoQdNAnmRhvVrqaMLV+Tv28f22bOJTk6m55gxbp1LsnKhNfUD\nuUKdKy5dW+rowgF5WVl8MW8ew5Ys4ea4OLfPJ1m50Jrqmy9fPnuWz6dObXHNFS1IP7po6NyOHexc\nsIDhS5cSFhOj2Hmlr1y4ynB95KBu54qzpI4ubJ3dto2vn32Wu197TdEgDpKVC22pHsi16FxxltTR\nxenNm8lKTiZ2xQo633GHKteQWrnQiiZbvWnVueIKqaO3Pic2buSbl1/m3tRUQqKiVLuOZOVCK6rX\nyAEOr1qlyJorWpA6umfLWb+eQykp3JuaSlDv3qpfT2rlwlmGrJGDvp0rzpI6uuc6unYth1NTGblm\njSZBHCQrF9rQLJArueaKFqSO7lkOpaZy7N13GfX223QID9f02lIrF2rTJJAbqXPFFVJHNy+r1cq/\nX3+dk5s2Merttwns3l3zMUhWLtSmSSCv7VwxW1bekKzrYi5Wq5X9y5Zxdvt2Rr31Fu26dNFtLJKV\nCzVpEsihOqv1lJKE1NGNz1pVxZ4XXyRv925Grl5NQGioruORrFyoSdNAruWaK1qQOroxVVVWsmvh\nQoqys4lbtQr/jh31HhIgWblQj3aBPDLSsL3kSpA6ujFUXb/Ozt/+livff09sSgp+HTroPaQ6kpUL\ntTgSyFcDecABm2PJwFlgX82fB1o6SVBkpKFmd6pF6uj6qSwvZ8fTT1NeUsI9y5fjGxio95Aakaxc\nqMGRpvMRwGVgLTCw5thCoAT4UzOvs9pmotaqKtZHRzNp+3ZDZUlqs1qt5H39NUfefpuLhw/T55FH\n6PPIIwSEhGg2hgyLhQ9XroTycvDzY3JiIiPHjtXs+lqoLCvjyyefxNvPj7teeQUfPz+9h9SkL379\na7oMHuzU7kOi9VBrQtCXwEV713PmQp7SueIsvevoGRYLa5KSGJGTw4jTpxmRk8OapCQyLBbVr62V\niqtXyXziCXzbt2f40qWGDuIgWblQnjs18rnAt0Aa4NDdJE/qXHGFHnX0D1euZGyDks7YsjI+WrlS\nletp7frly2yfNYvAbt0Y9vLLePv66j2kFkmtXCitjYuvWwG8UPP498AyIKHhNyUnJ9c9jo2NpYsH\ndq64oraOPiA+nlMWC/teeUW9dV3Ky+0etjZx3EzKiorYPmsWoVFRDElKwstbs3v3bhs4ezaZc+YQ\nOWWKrMHSymVmZpKZmenWORwtj9wKfMKNGrkjz1kbZpnfZ2Zy7J13uNdDskGlqFlHnzNxIiNychod\n/6xjR9K++AJvHx+3r6GH0sJCts2YQdc77+SOZ56prSuaitTKhT1aLprVzebxJOp3tDSptXSuOEvN\nOvrkxEQ+bRCsN1mtRPn7Y5kwgVOffkpVZaVb19Datfx8Pp86lR6xsaYN4iC1cqEcRz4B7wL3AJ2o\nbkNcCMQCtwNW4CQwq+Y5W40y8tbaueKK0sJCct5/n5z33iO4Xz/6TZ1K12HDXApa6559ln9s3EhQ\nz554+fnxUGIicWPGkPf11xz4618pKyrip7NnEz5mjOEz9CvnzpGRkEDEpElEJSbqPRy3SVYuGnIl\nI9dkPXJbm6dMYchzz9Fp0CAVL+05lFgf/V9PP03Xu+4iYtKkRs/VlnXMENBLzpxh24wZ9H3sMY8J\nfLJeuWjIFIF854IFdBkyhIiHHlLx0p7H1Tq61Wrl77Gx3Pe3v9H+5ptbPL9RA3rxiRNsnzmTqFmz\n6DNlit7DUZRk5cKWYTeWsOWJa65owdU6esmpU3j7+hLYo4dD5x+1bh1DnnuOnPfeM0wNvejYMbbF\nx3Pb3LkeF8RBauXCfdoHcg9fc0ULzvSj5+3eTdjQoQ7X1o0W0AsPHWLbjBn8bP58ek+cqPn1tSB9\n5cJdmpdWLp89y+dTpzIxI0PFS7cuzdXRm6uPO0LPkkv+vn18MW8eMYsWcXNcnOrX05PUykUtU9TI\npXNFPfbq6AfffJNxFkuz9XFnzq1VQM/LymLHU08xbMkSuo8Yoco1jMaMtfLWsI6P1kwRyEE6V7RQ\nnJvL7t//nvO7dxPx0EP0e/xxgiIj3T6vFgH93I4d7FywgOFLlxIWE6PYeY3ObFl57To+tktAWPz9\nmf7iixLM3WCKm50ga65oISgigp5jx9JtxAhF13VRu4Z+dts2vn72We5+7bVWFcTBPLVya1UVF7Oz\neTs52aPX8TETV9dacYt0rmjjfFYW4fffT8SkSYqv61Ib0MPuvLMuQz/45ptuZeinN29m75IlxK5Y\nQUhUlEvjMjsjrsFitVopOXWKvF27yMvKIi8rC9/27am8fBns3ET3hHV8zEaX0oqsuaK+pvrH1VrX\nxd2Sy4mNG/n21VeJTUkhuG9ft8ZidkaolV8+e7Y6aO/aRd6uXXj5+BAWHU1YTAxh0dEEdu/e5Do+\nO/r0YfnHH+swas9gmhq5dK6o79LJk2ybOZMJn33WZOthcW4u2evWcXrLFsJHj1akju5KQM9Zv55D\nKSncm5pKUO/ebl3fE+hRK7+al1eXbeft2kVlaWl14K4J3u3Dwxu9jzIsFpbPmsVDN91Udyzd3594\nqZG7xTSBXDpX1Jezfj0X9u1j2Esvtfi9Sq7rUsvRgH507Vqy160jLi2NDuHhLl/P06idlZcWFnJ+\n925+3LWL81lZlBYW0mXoUMKio+kaE8NNEREt/vevqqzkhZ/+lB9798bLaq1bx0eCuHtME8hBOlfU\n5kr/uBLrujTUXEA/lJpK7oYNjExLI7B7d5ev4YmUzsrLL13i/J49dXXuK+fO0Xnw4LqMO7hvX6fX\ncy88dIidzz7Lgxs3uj0+cYOpArmsuaIeR9dXae71StfRGwb0qooKvHx8GLlmDe26dHH5vJ7Mnaz8\n+pUr5H/zTV3gvnTyJJ0GDaqrcYcMGOD2bkpH3nqLy2fPMjQpya3ziPpcCeS6dK2AdK6oydH1VZpS\n25HSddiwujr6Jw8+6FYd3bbLZfPkyVw6eRK/oKDqzhoDLc5lJM50sFSWlXFh/35+rLk5WZSdTUhU\nFF2io/nZb35D6G23Kb6XaV5WFr0nTFD0nMI1umXk0rmiHmfq445Soo5urapiz+LFFBw8yL0pKVw8\ncsSwqy0aRVNZeWV5OYUHD9bdnCw4cICgPn3qMu7Od9xBm7ZtVRtXVWUlH911F+PS0wkIDVXtOq2R\nqUorl7/7js+nTZPOFRW4u75Kc1yto1dVVpKVnEzJyZPcs2JF3U1uoy+fq7faWvl/pqdz6eTJunbA\n/P376RAeXlfj7jJ4ML7t22s2LqmPq8dUgVw6V9Thbn3cmes4Wkevun6dnc8+S2lBAXe//jq+gYFN\nnk8CejVrVRVFOTnkZWXxzcsvA9XlyNqMu8vQofh37Kjb+KQ+rh5T1ci9vL0J6t2bSydOSOeKgtyt\njzvK0Tp6ZXk5/3rmGSrLyrhn+fIma71qzBQ1k6ZmT4bFxDAgIYHDq1dz//r1hpntKfVxY9EtIwf4\nasECwqRzRVFq1Mcd1bCO3ueRR8h5/318/P2565VXnLrZ1hoy9Mvff19XKsnLysLL27vR7MlaRpjt\nWUvq4+oyVUYO0FE6VxR3PiuLrnfdpcu1A0JCGDhnDgPi4zn+4Yd88atfATB04UJwcqEuT8zQm5s9\nOfCJJ+zOnqxlpDVYio4epV1YmARxA9E1kAdFRpKXlaXnEDyK1Wolb/duBj35pK7jqLp+nTObN9N7\n0iTCH3iA7P/7Pw688YZL/ehmDujNzZ7sP3WqQ7Mna9mujKh3Vp63ezddhg7VdQyiPn0DeUQExbLt\nm2K0qo83p6yoiO2zZhEaFcWQpCS8vL3pPny42/3oZgjozc2ejHz4YZdmT9oySlYu9XHj0bVGLp0r\nytKzPg7VGei2GTPoeued3PHMM3azTaXWdTFCDV2L2ZMN6V0rl/q4+kzVflhL1lxRjpr94y25lp9P\nRnw8t4wezW1z57YYmJVa10XLgN7c7MmuMTGqzJ5sSO9dhKR/XH2mDOTSuaIMrfrH7bly7hwZCQlE\nTJpEVGKiU69Val0XNQK63rMnm6JnVi794+ozXdcKSOeKUvSqj5ecOcO2GTPo+9hjLgUWpdZ1UaKG\nXlVZycUjR+zOnuw3bZrmsyebometXOrjxqR7Ri5rrihDj/p48YkTbJ85k6hZs+gzZYpi51VkXRcH\nMnTb2ZN5u3Zxfu9e2nXubJjZk83RIyuX+rg2TFlakTVXlKF1fbzo2DG2JyYy6Mkn6T1xoirXUKKO\n3jCghz/wAP7BweTv3Vtv9mRYTAxhQ4fStnNnVX4WpelRK5f6uDZMWVoJ7NGDsuJiyktKpHPFRVr3\njxceOkTmnDkMXrCAnmPGqHYdH39/IiZNovfEiXV19G///Gen6uhXzp3jyg8/ENijB/n79nFwxQoA\nuv7Hf3D/e+9pfj9BKXr0lUv/uHG53tSqENs1V4RrtKyP5+/bx/bZs4lOTlY1iNuqrX/f++abjFyz\nhmvnz/PJgw+y6/nnKW5wf+Xq+fOc/PRTvv7d79h4331sffRRfvzqK7oMGcI4i4VHDx4kbtUqKq9d\nI3P2bE59+ilVlZWa/BxKGzh7NkdWr6aitFST6+VlZREmgdyQdC+tgHSuuEur+nheVhY7nnqKYUuW\n0H3ECFWv1ZLaOvrBFSuwVlbS/pZb8PLxoeziRYf2njRCH7oStKqVV1VU8NHw4VIf14ApSysgnSvu\n0mJ9lXM7drBzwQKGL11KWEyMqtdqTsPZk14+PlgrK7n83XcARC9aRK9x41qso5thpqgjtOpguSjr\nqxiaIQK5rLniOi3q42e3bSMrOZm7X3uNznfcodp17Glu9mT0okXVsyfbtKnXj/7v115zuI5u9oCu\nVa38vNTHDc0YgVzWXHGZ2vXx05s3s3fJEmJXrCAkKkqVa9hyde9Jd/vRzRzQtcjK83bvlv5xAzNE\njVzWXHGdmvXxExs38u2rrxKbkkJw376Knx+qV0osOHBAldmT7vSjm62GrmatXOrj2jJlH3ktWXPF\nNWr1j+esX8+hlBTuTU0lqHdvxc5bb/ZkVhb5+/apvvekO/3oZgnoavaVFxw8yNfPPSf94xoxdSCX\nzhXnqbW+ytG1a8let464tDQ6hIe7dS4jzZ50Z10XMwR0tbLyI2vWcPn772V9FY2YOpAfXrWK0sJC\nfvab36g4JM9y6eRJts2cyYTPPnN6GdimHEpNJXfDBkampdXbasxRdvee7NDhxhZmBpk9WVtHP71l\ni1Pruhg5oKuVlWc+8QS9J0wg/P77FTunaJqpA7msueI8JevjVquVA2+8wZmtW4lLS6Ndly4Ov9bu\n3pM1GXfDvSeNxtU6ulEDutJZudTHtWfqQC5rrjhPqfq41Wpl/7Jl/PDVV8Slprb4gb16/nxdqaTe\n3pM1wbu5vSeNytU6utECutJZudTHtWfqQF7bufJfmZmGWCrU6JSqj1urqtizeDEFBw9yb0qK3Xp1\nc3tPNjd70oxcraMbKaArmZVLfVx7pp3ZCTfWXCnOzZXOFQco0T9eVVlJVnIyJSdPErdqVV3rp9p7\nTxqZq/3oRupDV7KvXPrHzcEwGTlI54oz3K2PV12/zs5nn6W0oID/+OMfq1sCa8ol9faejImpmz3Z\nWrlSR9c7Q1ciK5f6uD5MXVoB6Vxxhjv18euXL/Px6NFcv3SJ4AEDKDl5UvO9J83IlTq6XgFdiVq5\n1Mf1YfpALp0rjnG2Pm47e/Lcl19yYf9+APpNnUr3ESPodPvtuuw9aVau1NH1COjuZuVSH9eHqWvk\nIGuuOKql+nhTsydDBw7kwv79dL/nHu7+y1/w9vXVeOSewZU6uh41dHdr5VIfNw9DZeTSueKYhvXx\nZmdPxsTQZcgQvNu0IXPOHDr07En0okW69zt7Gmfr6Fpl6K5m5VIf149apZXVwIPAeWBgzbEQ4H2g\nJ3AKmAIUNXid04EcZM0VR+x4+mnad+9OYPfuDs2eLCsqYvusWYRGRTEkKcljO06MwNk6utoB3dVa\nudTH9aNWIB8BXAbWciOQ/xG4UPP3fCAY+G2D17kUyKVzxT7b2ZOnPv0UgF4TJrQ4e7K0sJBtM2bQ\n9c47ueOZZzym39vonK2jqxnQXcnKtaqPZ1gsfLhyJZSXg58fkxMTGTl2rKrXNDo1b3beCnzCjUB+\nFLgHyAO6AplAvwavcSmQS+dKtaZmT7YNC+PoW2/x6MGDLQbla/n5ZMTHc8vo0dw2d64EcZ04s66L\nGgHdlaxci/VVMiwW1iQlMbasrO6Yxd+f6S++2KqDuZaB/CLVWXjtOQptvq7lUiBvrZ0rtbMna29Q\nlhYWEjZ0aF1LYO3sSUf7x6+cO0dGQgIRkyYRlZio0U8hmuNMHV3pgO5MVq5WfdxaVUXFtWtUXL1K\nxbVr/L+EBOLOnWv0fTv69GH5xx8rdl2z0atrxVrzp5Hk5OS6x7GxscTGxrZ4stbSudLc7MmIZmZP\nOrI/Z8mZM2ybMYO+jz2m+qa8wnEBISEMnDOHAfHxnLJY2PfKK03W0ZXucnGmg6XgwAHaBARQWV5O\ncW5udfC1CcD1/q59bO/5Bo8rS0vxCQjAt107fNq25VJ2NtjZSMZaXu7Uz2Z2mZmZZGZmunUOd0or\nscCPQDdgOwqVVjy1c6Vu70k3Zk860j9efOIE22fOJGrWLPpMmaLGjyIU4kwdvWGGHjVrFj1iY6ks\nLbUbNO0F2yOrVwNwy333NRt0rRUVALTr2pU2bdvi07ZtXfBtY/O40bF27Ro9X+/1AQF1yUlFaSlT\nY2J4sOZatiQj1y4j3wRMBf5Q87div3VPWXPFdu/J81lZXDx61KG9J5vTUv940bFjbE9MZNCTT9J7\n4kQlfgzhpsry8uYz1atX6T5iBAHBwRz461858Ne/AtCxb18Cu3e3+5qywkJ2/vZGb0G7bt3w69Ch\nUaBt07YtbWqCqX9QEBEPPUTuRx/RIzYW/+DgJoPul08+qWp9PH/fPr5OSuLOyEjSjx+vF8zT/f2J\nl1Kg0xwJ5O9SfWOzE/Ad8DzwMrAeSOBG+6FiboqIoPj4cVMF8kZ7Tx48SFBkJGExMQz8n/9RZPZk\n3u7dhA0daremWnjoEJlz5jB4wQJ6jhnj1nVam4a1W0eyW0dLCkBdMG0yk23bloBOnRj4q19Vty9+\n8glF2dkUZWfTPz6em+PiaNOuXf3XBwSQt2tXXYY+ICHBoZJLWXEx5cXFTU70qaqoIP+bb7jz979X\n/PdcUVrKv19/nVOffMKQ555j3P33M8Bi4aOVK7GWl+Pl50e8dK24xFATgmqZoXNFj70nm1pfJX/f\nPr6YN4+YRYu4OS5O0WsaiSPZrRK1W9tM1t6xusc2wbWp7NbVNWsc7Ud39qZoSx0savWP12bhwf36\nMeS55xzaXq+1Mv1aK7WM2LniyOxJNfeebKo+npeVxY6nnmLYkiV0HzFCtes7SuvstqWga6922yg7\ntqndGo2jdXRnAnpzHSxK9483zMJlu7iWeUwgN8JuQUbbe9Le/pznduxg54IFDF+6lLCYGKfO12J2\naxtsHQnKKmW3to9b+4qMjvSjOxLQm8vKlewflyzcNR4TyPXqXDHa3pO22e3Rt9/mx507GZKURMW1\na5y2WDjx97/Ta/x4Ovbtq0l2Wxtwmwq0tYHZqNmtp3CkH72lgG4vK1eqf1yycPd4TCDPsFh484kn\nCAoPxzckxKVpu8teeIFNaWm0qaqiwtub8QkJPPX88/W+R6m9J7XIbksLCgAIHTSIgm+/BeCmXr3o\nPHiw3ey2qaAs2a3ncKSO3lRALz52rFFWrkR9XLJw93lEIFdi2u6yF15g8xtvMN2m9LEmP5+4qVP5\nr9tv5/vMTH786isA2gQGEjpwIKEDBxLYrVvLN8dcyG4bZbVOZre29fHze/fy7auvEpuSQnDfvk7/\nfoXncaSObi+gn968mbDo6Lqs3J36uGThyvGIQD5n4kRG5OQ0Ov55p04sXLDAoez2d3//O7/q1q3R\nOV4/e5a5NjcKQwcOpE1gYPNB1wDZbW19PCoxkUMpKdybmkpQ796qXlOYU0t1dNuAnr9vHwAPZ2Xh\nGxjocn1csnBleUYgHzuWEadPNzr+SVkZT4wb12J226ZtW/578mRmBDdc+gXSiovJOHvWpR9GTznr\n17N70SICu3cnLi2NDuHheg9JGFxLdfTagL5txgwA7lyyhD0vvsj4zZsdro9LFq4OzwjkTWTkzkzb\nvadnT2bZuUm6PD+fzw4d0rTbRAnvREUBMOGzzzS/4SrMraU6+sUjR/jH5Ml13/8ff/iDQxOL8vfv\nZ1dSEh379pUsXGGuBHLDtRdMTkzE0mDSQ7q/Pw85MW13fEICa/Lz6x1bnZdH9KBBpI8fT9aiRZTY\nyfqNxmpz37N8AAARmklEQVS18u1rrwEwet06CeLCaT7+/kRMmsSYDRsYPH8+Z7ZuZePo0RxYvpzS\nwkKC+/fn5lGjaNulCzf16kXOe+9hmTCBU59+SlVlZaPzVZSWsm/pUr789a+5be5chi9bJkHcAAyX\nkUP1DU/babsPudi18klaGj5VVVR6ezOupmultKCA7L/9jePr1xMWE8OAhARCBgxwaZxqslqt7F+2\njGPvvAPAlL17ZT1xoYiGdfSw6Gi+mj+fYS+9xK3jxjXZtihZuDY8orSiletXrnD8gw84unYtQRER\nDEhIICwmxhDB0lpVxZ7Fiyk4eJBbRo3i0okTLa4/LoSzauvox955h7LCQkKiorj//ffx8vKqd1P0\nal4eVRUVVFVUMDQpSWrhKvOI0opWfAMD6T9tGuM3b6bn2LHsWbyYLT//OWe2bLH7T0qtVFVWsmvh\nQoqys4lbtYqi7Gy6REfrNh7huWrXRx/x5z8D1QuvfTJmDLkbNlBVXk7XYcO4/emnuXLuHNfOn8da\nWUnV9eu6fj6Efa02I2/IWlXF2e3bObxqFeXFxfSfPp1eEyZoOnGm6vp1dj77LKUFBdz9+uu0adeu\nxfXHhXBXbf/4tfPnqaqowFpVxYX9+7leUoKXjw93vfIKt9x3n6qbRIsbJCN3g5e3N7eMHMl977xD\n9KJFfJeRwab77uNwWhrXL19W/fqV5eXsePppyktKuGf5cnwDA1tcf1wIJdQujzxwzhwuHj5M/2nT\nuF5SAoC1spIf/vUvLuXm0nXYMEatW8eQ555r8aao0JZk5M24ePQoh1ev5sd//YuIyZPp+9hjqrQu\nVpaV8eWTT+Lt58ddr7xS968AR/fnFMJVtuurtAkMZP3gwQAM/9OfCL///ib70QHJ0FUiNztVcvns\nWY689Ran09MJf+AB+k+bRoeePRU5d8XVq/xz7lwCQkIYtmQJ3r6+dc81tf64EErIsFh4d9kyLuXk\n0CEyksgrV/hpp05cPnuWh3ftqrcyYlP96N5+fhLQFSaBXGVKty5ev3yZzDlz6NCzJ9GLFtV78zuy\nP6cQrrK3ptGmykpm/ulP+G7Z0uR65U2t6+IfHCwBXSESyDWiROtiWVER22fNIjQqiiFJSY2WfrW3\n/rgQSmluBvXil15qdhehWvbWdbkpIkICupvkZqdG3G1dLC0sJCM+ni6DBzPkd7+zu353c/tzCuG2\n8nK7h63l5QT370/ooEEcX7++2VMERUQQnZzMuPR02nXrRkZCApmzZ2O1WuWmqMYkI1eAM62L1/Lz\nyYiP55bRo7lt7twmA7XUx4WaWlrTqKW9Pe1pqo6e/803kqE7QUorOrNarZzfs4fDaWkUHT1K31/+\nkj4//3ndLkdXzp0jIyGBiEmTiGpm7Ripjwu12auRp/v7E2+z7n9ze3s2p6k6elF2tgR0B0ggN5CG\nrYs9YmP5av58+j72WIsfDKmPCy20tKaRK1l5Q/bq6Nfy8yWgN0MCuQFdPnuWrORkfty5E4BxFkuL\nrYvSPy6MwtWsvKFG/eiPPw5eXhxcvlwCegMSyA2o6Ngxticm0m/qVMpLShxqXZT6uDAKJbJyW43q\n6L/8JQGhoRxetUoCeg0J5AZTeOgQmXPmMHjBAnqOGQO03Loo9XFhNEpl5bbs1dE79OxJzrvvtvqA\nLoHcQPL37eOLefOIWbSIm+PiGj1fWV7OqfR0jqxeTZu2bRmQkMDNo0Zx+cwZqY8LQ1E6K2+oYR29\n409+wpnNm1ttQJdAbhB5WVnseOophi1ZQvcRI5r93oati77t29M+PJzhS5dqNFohWqZGVt5QvTp6\n37507NuX/G++oby4uFUFdAnkBnBuxw52LljA8KVLCYuJcfh1ta2LGdOmAXD7//5vvdZFIfSkdlZu\nq2EdvWOfPpScPk3F1autIqBLINfZ2W3byEpOZsRf/kLnO+5w+vW19fGhzz/PmS1bVF91UQhnaJGV\n22pYR+9w662UFhTg5eXl0QFdArmOTm/ezN4lS4hdsYKQml3vndWwf1zNVReFcJaWWXlDtnV0vw4d\nuF5SQkBoqEcGdAnkOjmxcSPfvvoqsSkpBPft6/J5muofN8uG0cLzaZ2VN2RbRy8rKsJaUcFNvXp5\nVECXQK6DnPXrOZSSwr2pqQT17u3WuVrqHzfyhtGiddAzK7dlW0cvOnYMwGMCugRyjR1du5bsdeuI\nS0ujQ3i4W+dypn+8qdZFM795hXnonZXbsq2j//Dll4D5A7oEcg0dSk0ld8MGRqalEdi9u9vnc2V9\nFSNsGC1aH6Nk5Q3V1tFPbtpEZVmZaQO6BHINWK1WDrzxBme2biUuLY12Xboocl531ldpadVFIZRm\npKy8obo6+rvvUlpQYLqALoFcZVarlf3LlvHDV18Rl5pKQGioYudWan0VrTaMFq2bUbNyWw3r6GYJ\n6BLIVWStqmLP4sUUHDzIvSkp+HfsqNy5VVhfRVoXhdqMnJXbalhHN3pAl0CusAyLhQ9XrsRaVkbx\nd98xuEsX5m3ciF+HDopeR831x+taF99/n7A775TWRaEYM2TlDdnW0QO7d68L6Nu3bOHDlSurt8Dz\n82Nyg7XZtSSBXEF2d1Dx8yN+8WLF/wNrsf64tC4KNZglK2/Ito6eXVbG/uJiJthk5xZ/f6bb7Jak\nJQnkCmppT0Mlabn+uLQuCiWZMSu3VVlWRnxsLPdfutToOTU+645wJZA33r5dVGtml3ElWa1W8nbv\nJmzoUEXP2xQfPz8iJk3iwY0biZo1iyNvvUX6uHEc/+ADKhX+2YTnC+7fn9BBgzi+fr3eQ3GJj78/\n7YKD7T6n9GddTRLIm9JEL7aXwj3aJadO4e3rS2CPHoqetyVe3t7cMnIk973zDtGLFvFdRgab7ruP\nw2lplJeUaDoWYW4DZ8/myOrVVJSW6j0U12j0WVeTBPImTE5MxOLvX+9Yur8/DyUmKnqd2mxcr1q1\nl5cXYUOHcu+bbxL75ptczM5m0/33s//VV7mWn6/LmIS5mD0r1+qzriapkTejdpfxyitXyD94kBmv\nvsrYRx5R9BpG3J9TWheFs8xeK6/9rFvLy/Hy8+Mh6VqpY/pAbmvvSy+BlxeDf/tbxc5p9P05pXVR\nOMOsHSxGIzc7VTRgxgxObtyoaLlBr/q4owJCQxk0bx7jt24ldOBA/vmrX7Ft5kx+/PprPOl/0kIZ\npq+Vm5gEcge17dyZXuPHczgtTbFz6l0fd5RvYCD9p01j/ObN9Bw7lj2LF7Pl5z/nzJYtVFVW6j08\nYRBmr5WbmbsR5BRwCagErgPRNs95VGkF4Fp+Punjx/Pgpk2KrF9ixPq4I2TVRdEUs9fKjUCP0ooV\niAXuoH4Q90hKZuVa948rSVoXRVMkK9eHEqUVY9cFFKZUrdzo9XFHSOuisEdq5dpTIiP/HNgDzHR/\nOManVFZulvq4o4L79eOuP/6RB9av5/qVK6SPH0/WokWUnD6t99CExiQr1567UaQb8APQGfgMmAt8\nWfOcdeHChXXfGBsbS2xsrJuXMwYlauVmrY87SloXWzeplTsuMzOTzMzMuq8XLVoEOvaRLwQuA8tq\nvva4m5223OkrN3r/uJJk1cXWS/rKXaP1zc52QO3C3IHAfcABN85nKu7Uyj2hPu4oaV1svaRWrh13\nAnkY1WWU/cAu4FNgqxKDMgN3auWeVh93hKy62PpIrVw7MkXfDa7Wyj29Pu4IextGR06ZovjuS0Jf\nUit3nkzR15grWbmZ+8eVJK2LrYNk5dqQQO4mZ2vlrak+7ihpXfRsUitXnwRyNzmblbfG+rij2t98\nM0OTkvjPTz/FPziYrb/4BTueeorCw4f1Hppwg2Tl6pNArgBnsvLzWVl0ifb41QzcIqsueh7JytUl\ngVwBjmblUh93jrQueg7JytUlgVwhjmTlUh93jbQuegbJytUjgVwhjmTlUh93j6y6aG6SlatHArmC\nWsrKpT6uDGldNC/JytUhgVxBzWXlUh9Xh7Qumotk5eqQQK6wprJyqY+rS1oXzUOycuVJIFdYU1m5\n1Me1Ia2LxidZufIkkKvAXlYu9XFtSeuisUlWriwJ5CpomJVLfVw/0rpoTJKVK0sCuUpss3Kpj+tP\nWheNR7Jy5cgytipKmT6dL/buxdffn7IrV5ixdCkjx47Ve1iixsWjRzm8ejU/7NhB5MMP0/exx1ze\nuk+45i8TJ7L33DkCO3UCPz8mJya2+s+IK8vYtlFnKCLDYuGLb77hwcpKuHoVvLxYk5QE0OrfqEZR\n27p4+ezZ6pLL+PGEP/AA/adNo0PPnnoPz+NlWCzsys3lP6uq4MoVAPmMuEgycpXMmTiRETk5jY7v\n6NOH5R9/rMOIREvqbRgdE1O9YXRUlN7D8ljyGbFPMnIjaeJGmlVusBlWbevigIQEjn/wAf+cO5eg\n3r0ZMGOGbBitgPJLlyjOza3+c/w4Fw8cADu7BslnxHkSyNXi52f3sFcTx4Vx1LYu/uQXv+BUejp7\nFi+mTdu2DEhI4OZRo/D28dF7iIbWMGDXPr5eUsJNvXsTFBFBUGQk7Xr0gIKCRq+Xz4jzpLSikgyL\nhTVJSYwtK6s7lu7vT/yLL0r9z2SsVVWc3b6dw6tWUV5cTP/p0+k1YQI+rTzgOBqwgyIjCYqIILBb\nN7y8bzTKyWfEPldKKxLIVZRhsfDRypVYy8vx8vPjIbkjb2qtdcNodwN2c+Qz0pgEciE04omti2oG\nbOE4CeRCaKy2dfF0erppWhclYBubBHIhdGLE1kUJ2OYkgVwInV2/coXjH3zA0bVrNWtdlIDtWSSQ\nC2EQleXlnEpP58jq1Y1aFzMsFj5cubJ6roET09IlYLcOEsiFMJiGrYtFt9/Oln/8g7E2k14s/v5M\nt2m5k4DdukkgF8KgalsX5/3iF0yw039uadOG+OhoCdhCpugLYVS1G0aH9OkDdvYT9fbxoe8vfykB\nW7hEArkQWmpiNmj78HB63H23xoMRnkL+ty+EhiYnJmLx9693LN3fn4cSE3UakfAEUiMXQmMyLV00\nR252CiGEybkSyKW0IoQQJieBXAghTE4CuRBCmJwEciGEMDkJ5EIIYXISyIUQwuQkkAshhMlJIBdC\nCJOTQC6EECYngVwIIUxOArkQQpicBHIhhDA5CeRCCGFy7gTyB4CjQA4wX5nhCCGEcJargdwHeIPq\nYD4AeBTor9SgRGOZmZl6D8GjyO9TWfL71JergTwaOA6cAq4D7wETFBqTsEM+KMqS36ey5PepL1cD\neQ/gO5uvz9YcE0IIoTFXA7ls/SOEEAbh6lZvdwLJVNfIARYAVcAfbL7nOBDh8siEEKJ1ygUitbhQ\nm5qL3Qr4AfuRm51CCGE6Y4BsqjPvBTqPRQghhBBCCGFLJgsp6xTwb2AfkKXvUExnNZAHHLA5FgJ8\nBhwDtgIddRiXWdn7fSZT3bm2r+bPA41fJppwC7AdOAQcBObVHNf9PepDdbnlVsAXqZ8r4STV/2GF\n80YAd1A/8PwR+E3N4/nAy1oPysTs/T4XAv+rz3BMrytwe83j9lSXq/tjgPfoMGCzzde/rfkjXHcS\nCNV7ECZ2K/UDz1EgrOZx15qvheNupXEgf0qfoXicj4FROPkeVWPRLJkspDwr8DmwB5ip81g8QRjV\n5QFq/g5r5nuFY+YC3wJpSKnKVbdS/a+dXTj5HlUjkMtkIeXdRfV/4DHA/1D9z1uhDCvynnXXCqAX\n1SWCH4Bl+g7HlNoDHwG/BkoaPNfie1SNQP491QX8WrdQnZUL1/1Q83c+8Heq17oRrsuj+p+rAN2A\n8zqOxROc50awWYW8P53lS3UQX0d1aQWcfI+qEcj3AH24MVno58AmFa7TWrQDOtQ8DgTuo359Ujhv\nEzC15vFUbnx4hGu62TyehLw/neFFdTnqMPBnm+OGeI/KZCHl9KK682c/1e1J8vt0zrvAOaCc6ns3\n06nuAPocaT90RcPfZzywlur22G+pDjhyz8Fxw6le3mQ/9ds35T0qhBBCCCGEEEIIIYQQQgghhBBC\nCCGEEEIIIYQQQgghhKf6/xV0a4q/7gZ4AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f53d5b19bd0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# %matplotlib inline\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "import itertools \n",
    "\n",
    "def get_plot(walk):\n",
    "    \n",
    "    l = walk.l\n",
    "    x = [_.x for _ in l]\n",
    "    y = [_.y for _ in l]\n",
    "    plt.plot(\n",
    "        x, y,\n",
    "        color = 'brown', marker = 'o'\n",
    "    )\n",
    "    plt.xlim(0, g)\n",
    "    plt.ylim(0, g)\n",
    "\n",
    "a = get_plot(current_walk)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Obtaining neighboring state\n",
    "\n",
    "Once the initial state is obtained, we repeatedly obtain new neighboring states in the following manner:\n",
    "\n",
    "- Find any two indices except for the first and last\n",
    "- Swap the two points at those two indices.\n",
    "\n",
    "Once the neighboring state is retrieved, we move on to it if it's cost is lower than the cost of current state. Even if it is less desirable than the current state, we accept it with the acceptance probability _$p(\\Delta c, T)$_ defined earlier.\n",
    "\n",
    "### Tunable parameters\n",
    "\n",
    "Along the iteration, we will decrease the temperature with a certain value per certain iteration. Thus, the tunable parameters in SA are:\n",
    "\n",
    "- Initial value of temperature T\n",
    "- Cooling interval i.e. number of iteration before T is decreased\n",
    "- Cooling rate i.e. the value with which T is decreased\n",
    "- Minimum temperature i.e. the minimum value of temperature to be maintained.\n",
    "\n",
    "### Stopping criteria\n",
    "\n",
    "Generally, we stop the SA once we are sure that we have converged i.e. we have obtained the optimum state. However, in TSP, the determination of optimum path is infeasible for large numbers of points. Thus, we can't effectively determined whether our algorithm has indeed converged to the global minimum. Therefore, we take an alternative approach. We will fix a number called maximum iteration and will continue the algorithm till our iteration reaches that maximum. Along the way, we will record the state that is the most desirable among the states that we have observed during the course of our algorithm.\n",
    "\n",
    "Once the algorithm stops, we will display the state that is most desirable i.e. has high cost.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The cost of the solution state 86.93\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXIAAAEACAYAAACuzv3DAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAHvpJREFUeJzt3Xt01PWd//HnhJABEghiEBUlBKL+xBvir9SqYKSuYioa\nCurRuqsbyyBeym9lRdhNFS09lZ7i1tYflazI2ot1KWlZlRHUlFT0uLp4vHCxQiLQ1guSECJySYTM\n/jEzcZLMTObyvc/rcU4Ok28mMx/HmRdv3vP+fAdERERERERERERERERERERERERERAx1KrAB2Aps\nAb4XOT4MeAnYDrwIDLVldSIi0qcTgfGRy0XAB8CZwI+B+ZHj9wEPW780ERHJxBrgcuDPwIjIsRMj\n34uIiMONBnYDg4HWmOO+Ht+LiIgDFQFvAVWR73sG9z5rlyMiIlH5KVynP1AH/IpwawVgD+GWyqfA\nScBnPX9p7NixoaamJoOWKSKSM5qA8nR+Ia+Pn/uAFcA24Kcxx58FbolcvoWvAv6rlTQ1EQqF9GXQ\n1wMPPGD7Grz0pcdTj6dTv4Cx6YQ49F2RXwzcDLwHvB05tpDwlMoq4DZgF3B9uncsIiLG6CvIXyVx\n1X65wWsREZEM9NVaEYeoqKiwewmeosfTWHo87eUz8bZDkX6PiIikyOfzQZrZrIpcRMTlFOQiIi6X\nyhy5ZKg+GGR1bS10dEBBATMDAb5ZWWn3ssRmel6I0RTkJqkPBllZU0Nle3vXsZU1NQB60eYwPS/E\nDHqz02ChUIgjzc3ced11XL53b6+fry8sZNH99zOwpISBJSUMKCmhoLg4+gaHeNycqiom7djR6/ir\np53GsjW99tVJDsrkzU5V5BmKBnZbYyP7Gxv5vKkpfLmpiby8PA598gkMHNjr944dOsTHDQ0cbm7m\nSHMzh5ubOXbkCAMiwT5w+HAGRAJ+4PDhXWEf/bNfQYEN/7VilM5Dh+IeD3V0WLwS8RIFeR/6Cuzi\n8nKKx45l6OmnU3rVVRSXlzPg+ON5uaoK4lReQ8rLufgnP+l27OjhwxxpaQmH+969XSG/b8uWboHf\n3tJCfmFhONRjQz4S/qryne2jP/2J5q1bYWjvz2Hx6S9oyYKCPCLTwE5kZiDQqxe61u+nOhDodd38\ngQMpOuUUik45JfkaOztp37+/K9gP793LkeZmDn36aa/QV5XvHB1tbby1ZAmfvfUWN957L2t++ctu\nz4vftbYyrbTUxhWK2+VcjzzVwI79M1lgJ1MfDFJXW0uoowNfQQEzLJxOOHrkSFeox1b5h2Mvq8o3\n3Ud/+hNvPvggp0yZwvh/+if6Fxb2el5864YbOPrkk5xzxx2MmT7d7iWLzTLpkXs2yK0MbDdLVOV3\n/akqPyOxVfiFDz3EiK9/Pen12z78kPpbb+XrixczcvJki1YpTpSTQa7Ato6q/NTEq8JTsfedd3jl\nrru4dNkySs491+RVilN5OsgV2O6RsMrv+RdAgio/NvDdVOWnW4XH81FDA2/cfz+XP/UUQ8rKTFil\nOJ0nglyBnVu6Vfk9WjtuqvIzrcLjafr979ny+OP83a9/zaATTjBwleIGjgvy26+9NuH2YwW2pCPU\n2Ul7W1tXRZ9SlZ8g8LOt8mO32Hf6fJwzeDCntrZmXIXHs2X5cv6yfj2XP/UUBYMHG3Kb4g6OC/Lf\njBtH0O/npvnzmVBaqsAWS5hZ5cfbYv/7Q4eY9cgjXGngxEkoFGLTD39IW2Mjl9XWOr6tJMZxZJAD\n1O3bx5wrrlBgi6OkVOW3tHB4796uKv83TU1MHzSo122ZscW+89gxXps3D19eHhf/5Cf48nSy0lzg\n2CDfWFrKL4JBE+9KxFzRKv//3XQTU1paev3crOf4sfZ2NsyezdDTT+eChQs9N+EjvTn2gyW0/Vjc\nLn/AAIpOOYX+w4bF/blZz/F+fj+Tf/YzPvuf/2HbE0+Ych/ifqYH+Vq/nxlxtqWLuNHMQICg39/t\nmNnP8YIhQ6hYvpzGVav48A9/MO1+xL1MPddKMD+f6sWLdZ5l8Yzoczl2i321BadeGHTCCVQsX079\nrbfiP/547f6Ubkztkdd/97tM+fd/N/EuRHKLdn96n+N65J9/+KGZNy+Sc4aPH8+Fixfzyt138/mu\nXXYvRxzC1CBvb2uj48ABM+9CJOeMrKjgvLlz2RAIcDjOp1BJ7jE1yIvHjKGtqcnMuxDJSWO//W3G\nzpjBhtmzVSyJyUE+diyfK8hFTHFWIMDwCRN45e67OaaPistppgf5/sZGM+9CJGf5fD4uWLgQ/9Ch\nvL5gAaHOTruXJDYxN8jLy2lTkIuYJq9fPy5asoQj+/bx1sMP48RP5RLzmR7kmlwRMZd2f4qpQV54\n8smaXBGxQMGQIVQ8/rh2f+YoU4Pcl5enyRURiwwaMYKK5ct559/+jY9eecXu5YiFTD/XiiZXRKxT\nPGYMk372M/77X/6F5vfes3s5YhFLglyTKyLW0e7P3GN+kGtyRcRy2v2ZWywJck2uiFhPuz9zh+lB\nrskVEfto92duMD3INbkiYh/t/swNlnzUmyZXROyj3Z/eZ1mQa3JFxD7a/elt1gS5JldEbKfdn95l\nWZBrckXEfrG7Pz/euNHu5YhBLAlyTa6IOEd09+frCxdq96dHWBLk0ckVVeUizqDdn95iSZBD+A1P\n9clFnEO7P73D0iDX5IqIs2j3pzdYF+Tl5ZolF3Gg6O7Pjd/7nnZ/ulQqQf4ksAfYHHNsEfA34O3I\n19S+bqS4vFy7O0UcKLr7s6C4mNcXLtTuTxdKJchX0juoQ8AjwPmRr3V93YgmV+xTHwwyp6qKOZWV\nzKmqoj4YtHtJ4jBduz9bWrT704VSCfKNQGuc47507kiTK/aoDwZZWVPDpB07mLR7N5N27GBlTY3C\nXHrR7k/3yqZHfjfwLrACGJrKL2hyxXqra2upbG/vdqyyvZ262lqbViROpt2f7pSf4e/9AngocvkH\nwFLgtp5XWrRoUdfliooKTtDkivUSvHkV0ptakkB092f9rbcyoKSEkydNsntJntbQ0EBDQ0NWt5Fq\ne2Q08BxwTho/C/Xss33U0MD2p5/mMlWDlglUVlKxe3ev46+edhrL1qyxYUXiFnvfeYdX7rqLS5ct\no+Tcc+1eTs7w+XyQZus609bKSTGXp9N9oiUhTa5Y63BzM2NaW/nDkSPdjq/au5dLxo+3aVXiFl27\nP++6S7s/HS6V1P8tcClQQngM8QGgAhhPeHplJzA78rNYvSryUGcnqyZOZPqGDRQMHpzdyiWpw83N\n/LG6mlOvvJK9ZWXU1dYS6ujAV1DAld/6Fr66OkZedhnnz5tHXn6mHTbJBU11dWxZvpwrfvMbBg4f\nbvdyPC+TijytK6epV5ADrLv+ev7vv/4rJeedZ+Jd57bYED/3zjvjXqd9/35eu/deQkePcvHSpQwY\nNsziVYqbbFm+nL+sX8/lTz2lIsxkVrZWMqbJFXOlEuIA/qFDqXj8cY4/5xzW33AD+7Zts3CV4jba\n/elstgS5JlfMkWqIR+X168f4e+5h/Lx5bAgE2Pn88xasUtxIuz+dzfog1zlXTJFuiMcqnTqVKStW\nsPmxx3hryRI6jx41aZXiZl27P5ubtfvTYWwJck2uGCubEI867owzuPKZZ2hrbGTDrFkc2bfP4FWK\nF/Tz+5n8859r96fDWP5mpyZXjGVEiMfqPHaM9x59lN0vvMCkRx9l2LhxBqxSvObQnj28dPPNfHHh\nhby6eXN441lBATMDAb5ZWWn38lwtkzc7LZ87iz3niiZXsmN0iMNXffPjxo1jQyDAhAULKLv6akNu\nW7xj0IgR+G66idULFnBdSUnX8ZU1NQAKc4tZ3loBTa4YwYwQj6W+ufTlhf/6r24hDjqPj11sC3JN\nrmTO7BCPUt9cktJ5fBzDniDX5ErGrArxKM2bS0IFBXEP+xIcF/PYFuSaXEmf1SEepXlziWdmIEDQ\n7+92bK3fz4xAwKYV5S5bTrIR+2lBmlxJjV0hHqt06lSGlJWxce5c9m3dqvO05LjoG5p1tbUc2LmT\nEFC9eLHe6LSB5eOHUTrnSuqcEOKxdJ4W6enA7t28ePPNVNXX00+tlay44lwrUZpcSY3TQhzUN5fe\nBpeWMmT0aD7euNHupeQkW4NckyvJOTHEo9Q3l57GVFWxUx9WYgv7glyTK0k5OcRjad5cokZdeSV7\n3nyTIy0tdi8l59jbWlGQx+WWEI/SvLkA9C8qYuRll7Fr7Vq7l5JzbAvywpEjuyZX5CtuC/Eo9c0F\nwu2VD9VesZxtQR57zhUJc2uIR6lvLiMmTqSjrY3W99+3eyk5xbYgBxiiyZUubg/xWOqb5y5fXh5l\n116rqtxitgb5UE2uAN4K8Sj1zXPXmGuvZVcwqI+Es5CtQa7JFW+GeJT65rlJM+XWszfIc3xyxcsh\nHqW+eW7STLm1bA3yXJ5cyYUQj6W+eW7RTLm1bA3yXJ1cybUQj1LfPHdoptxatgY55N7kSq6GeJT6\n5rlDM+XWsT3Ic2lyJddDPEp989ygmXLr2B7kuTK5ohDvTX1zb9NMuXXsD/IcmFxRiCemvrm3aabc\nGrYHudcnVxTifVPf3Ls0U24N24Pcy5MrCvHUqW/uXZopN5/tQQ7enFxRiGdGfXPv0Uy5+RwR5F6b\nXFGIZ0d9c2/RTLn5HBHkXppcUYgbQ31zb9FMubmcEeQemVxRiBtLfXPv0Ey5uRwR5F6YXFGIm0d9\nc/fTTLm5HBHkbp9cUYibT31z99NMuXkcEeTg3skVhbh11Dd3N82Um8cxQT7UhX1yhbj11Dd3N82U\nm8MxQV5cXu6qilwhbi/1zd1JM+XmcE6Qu6giV4g7g/rm7qOZcnM4JsijkytffvGF3UtJSiHuLOqb\nu49myo3nmCCPTq44uSpXiDuT+ubuoply4zkmyMHZkysKcedT39wdNFNuPEcFuVMnVxTi7qG+uTto\nptxYjgpyJ06uKMTdR31z59NMubGcFeQOq8gV4u6lvrnzaabcOI4KcidNrijEvUF9c+fSTLlxUgny\nJ4E9wOaYY8OAl4DtwIvAUCMW45TJFYW4t6hv7kyaKTdOKkG+Epja49gCwkF+OlAf+d4Qdk+uKMS9\nSX1zZ/p4xAi+//3vM6eykjlVVdQHg3YvyZVSCfKNQGuPY9cAT0UuPwVUGbUgOydXFOLepr65s9QH\ng6z51a+YXlTEpN27mbRjBytrahTmGci0Rz6CcLuFyJ8jjFmOfZMrCvHcob65M6yuraWyvb3bscr2\ndupqa21akXvlG3AbochXL4sWLeq6XFFRQUVFRZ83ZsfkikI890T75q/dey8bZs3i4qVLGTBsmN3L\nyi0JZshDOTZb3tDQQENDQ1a34UvxeqOB54BzIt//GagAPgVOAjYA/6fH74RCobj5nlSos5NVEyfy\n7YYG+hcVpf376VKI57bOY8d479FH2f3CC0x69FGGjRtn95JyxpyqKibt2NHr+KunncayHB5L9Pl8\nkHo2A5m3Vp4FbolcvgUw7FG3cnJFIS7qm9tnZiBA0O/vdqzuwAG+PWuWTStyr1RaK78FLgVKgL8C\n9wMPA6uA24BdwPVGLio6uVJy3nlG3mw3CnGJVTp1KkPKytg4dy77tm7l/HnzyMs3ovMoiXyzshKA\nutracDslP5+vNTcz+vBhm1fmPmmV72nKqLUCsO2JJziybx8T5s83eElhCnFJpH3/fl67915CR4+q\nb26Dtg8/5OV/+AemrFjBcWecYfdybGFla8VUZk6uKMQlGc2b26t4zBgm3Hcfr82bx5cHD9q9HNdw\nZpCbNLmiEJdUqG9ur7Jp0xg+YQJvPvggmf6rPtc4MsjNOOeKQlzSpXlz+1ywcCH7t2+nqa7O7qW4\ngiN75PXBII/fcQfFo0bRf9gwZgYCXW+MpGrpQw/x7IoV5Hd28iVw5uDB3HnnnQpxSZv65vbI1X65\nJ3rk9cEgK2tqmF5YyJSWloy27S596CHWPfYYs4uKuG3IEG4fMoSmPXt4SWdZkwyob24P9ctT57iK\n3IhNApeWljI7zmai2i++oGH37rTXJBK1e906Ni1ezIQFCyi7+mq7l5MT3rj/fo4eOcJFS5ZEq1VP\n80RFbsS23fzOzrjH+yU4LpIq9c2tp35535wX5AUFcQ/7EhyP52he/P+sYwmOi6Sj2/nNAwGOtPY8\nOagYKX/gQC555BHe/elPaf3gA7uX40iOS7Z423ZXtbQwtSr1M+Vec9ttrNy7t9uxlZ99xrTbbjNk\njSJdffOzzw73zd9/3+4leZr65ck5rkcO4Tc8o9t2fQUFXHT22RS9/jpTnnySIaWlKd3G0oce4rkV\nK+h39CiHDh7k2ttvZ8HDD2e0HpFkon3zCxYsYLT65qbKhX55Jj1yRwZ5PE11dWxetiytMI9660c/\ngrw8LrjvPsPWIxKr9YMP2Dh3LiMvu0znaTHR0cOHWX/jjZxx882Uz5xp93JM4Y03OxMYO2MG59xx\nB3+srubzNCdPxn33u+xcs4bDPdotIkZR39wa6pfH55ogh8zDfODw4ZRdcw3bnnzSxNVJrlPf3Brq\nl/fmqiCHzMNcVblYoes8Lffcw4ZZs9il87SYQudj6c51QQ6ZhbmqcrFSdN78Pc2bm0bz5V9xzZud\n8aT7BujhvXtZe801fOvZZxk4fLipaxOBmPO0HDsWPk/LccfZvaQu9cEgq2trw5vwCgoyOqeR3bx4\nPhZPT60kkm6Ya4JFrNb1uaDr1oU/F/TMM+1eUtc5jWI/xT7o9/OPixe7Lsx3PvccW5cv58r//E/6\nFxbavZyseXpqJZF02yzqlYvVnNg3X11b2y3EASrb26mrrbVpRZlTv9wDQQ7phbl65WIXR/XNE5y7\nqOXdd3n/P/6Dgx9/bPGCspPr/XJPBDmkF+aqysUujpk3T3DuosLSUtqamlh33XWsv+km14R6rs+X\neybIIfUwV1UudnLCvPnlU6bwux7n51/r9/Od+fO58Ac/YHpDA+fccYerQj2X58td/2ZnPKm8AaoJ\nFnECu87TUl9dzacjR/La5s1d5zSakWBqpfPLL/n0jTf4y/r1fPTHP1JUWsqoK65g1BVXUHjyyZat\nOVVuPx9LTk6tJJJKmGuCRZzA6vO0fLZpE/9dU8PVzz+f9n25IdTdfj4WBXkPfYW5qnJxCivnzeur\nqymbNo0x06dndTtODnU3z5cryOPoK8xVlYtTWDFvnk01nowTQ92t8+UK8gSShbmqcnEaM/vmRlXj\nyURD/a8vvsjf6uttDXU39ssV5EkkC3NV5eI0ZvTNzarGk7E71N3YL1eQ9yFRmKsqFycyum9uRTWe\njF2h7rZ+uYI8BYnCXFW5OJFRfXM7qvFkrA51N/XLFeQpihfmqsrFybLtm9tdjSdjVai7pV+uIE9D\nvDBXVS5Olmnf3GnVeDJmhrpb+uUK8jT1DHNV5eJ0mfTNnVyNJ2NGqLuhX64gz0DPMFdVLk6XTt/c\nTdV4MkaGutP75QryDMWGef9Bg1SViyuk0jd3azWejBGh7uR+uYI8C7FhvuPpp1WViysk65t7pRpP\nJtNQd3K/XEGepWiYX7RkCa/cfbeqcnGFRH1zL1bjyaQb6k7tlyvIDRAN86Gnn87g0aNVlYsr9Oyb\nHz140PPVeDKphroT++UKcoM01dXx5oMPsu3zz9kzbhz9wLWfMi65Jdo3b29t5cLFi3OmGk+mr1B/\n4/77efP999nW0QFffmn7a11BbqBf19Swevlyrj/hhK5jbv2Ucckt259+mk0//CGnf+c7TJg/Pycr\n8kR6hfqoUfytpITnV63iupKSruvZ+VpXkBtoTlUVk3bs6HX81dNOY9maNTasSCQ19dXVnDx5Mp+8\n9pol5zd3q2io//Ptt3N1nKyy67WeSZB76jM7DZXgU8ZDCY6LOMFnmzZx8OOPOePmm23/XFCny+vf\nn5MvuYTiUaPi/txNr3UFeSIJPmXcl+C4iBNsXraMs2fPJi8/n7x+/Rh/zz2Mv+ceNsyaxa7nn7d7\nec7kgde6gjyBmYEAQb+/27G1fj8zAgGbViSSXLQaHz1tWrfjpVOnMmXFCt577DHeWrKEzqNHbVqh\nM3nhta4eeRL1wSB1tbV07N9Py9at3Lp4MdfOnm33skTi6mtu3MrPBXWb6Gs91NGBr6CAGZpa6eL6\nII/19FlnAXDT1q02r0Skt1R3cVrxuaCSHb3ZaaKpv/sdAK1600gcKLY3noz65t6kIE/RsHHjAHjB\nYedlEEnUG09GfXNvyTbIdwHvAW8Db2a9GodTVS5OlGo13tNxZ5zBlc88Q1tjIxsCAY60tpq0QjFb\ntkEeAiqA84GJWa/G4VSVi9NkUo3H8g8dqnlzDzCiteKsk/maTFW5OEmm1Xgs9c3dz4iK/GVgEzAr\n++U4n6pycYpsq/Ge1Dd3r2yr6ZOAT4DhwEvA3cDGyM9CDzzwQNcVKyoqqKioyPLunGHftm2su+46\nrlq9muM0viU2Met845o3t1ZDQwMNDQ1d3z/44INg4xz5A8AXwNLI956aI+9Jc+ViJ7M//Ufz5vax\neo58EDA4crkQuALYnMXtuYp65WInI3rjyahv7i7ZBPkIwm2Ud4A3gOeBF41YlBuoVy52Mbo3noz6\n5u6QTZDvBMZHvs4GfmTIilxEVbnYwexqvCfNmzufdnZmQVW5WM3KajyW5s2dTUGeJVXlYiWrq/FY\n6ps7l4I8S6rKxSp2VeM9qW/uPApyA6gqFyvYWY33pL65syjIDaCqXMzmlGo8lvrmzqEgN4iqcjGT\nk6rxWOqbO4OC3CCqysUsTqzGe1Lf3F4KcgOpKhczOLUa70l9c/soyA2kqlyM5oZqPJb65vZQkBtM\nVbkYyS3VeCz1za2nIDeYqnIxituq8Z7UN7eOgtwEqsrFCG6sxntS39waCnITqCqXbLm9Go+lvrn5\nFOQmUVUu2fBCNR5LfXNzeeNZ4kDDxo3j/YMHWTV5Mid97WtQUMDMQIBvVlbavTRxOC9V4z2VTp3K\nkLIyNs6dS8vWrbSedRZ1TzwBHR16jWRBQW6S+mCQpqIiri8shN27AVhZUwOgJ6ok5bVqvKdo3/z/\n33gjr/7858wsLu76mV4jmVFrxSSra2u5usdnlla2t1NXW2vTisQNvFyNx/IPHcr2goJuIQ56jWTK\nm3/lO0FHR9zDoQTHRcDb1XjHgQO0NTbS1tREW2Mj+7dsgQEDel1Pr5H0ee/Z4hQFBXEP+xIcF/FK\nNd4zsNuammhrauLLAwcYMmYMxWPHUlxezqCRI6Glpdfv6zWSPgW5SWYGAqysqaGyvb3r2Fq/n+pA\nwMZViZO5rRpPNbBPvOgiiseOpfCkk/DlfdXN/c6JJ+o1YhB3PGNcKPpmTV1tLaGODnwFBVTrHXlJ\nwMnVeMfnn3eFdCaBnYheI8bxmXjboVCPN/tEJL766mrKpk1jzPTptq0h1cAuLi9PK7AlPT6fD9LM\nZlXkIjazuho3q8IW+yjIRWxmVm9cgZ07FOQiNjKiGu8K7JiwbmtsDAf22LEK7BygIBexWH0wyOra\nWujoYN/27Vxz440pVeMKbElEQS5iofpgsPvInd9PcO1aTvzGN7qmNRTYki5NrYhYaE5VFZN27Oh1\nPJifT/XEiXEDW1MiuUVTKyJOl2D7eV6/fpzx93+vwJaMKMhFrJRg+3nRqFGMnDzZ4sWIV+ivfREL\nzQwECPr93Y6t9fuZoW3pkgX1yEUsVh8MdtuWPkPb0iVGJj1yBbmIiINkEuRqrYiIuJyCXETE5RTk\nIiIupyAXEXE5BbmIiMspyEVEXE5BLiLicgpyERGXU5CLiLicglxExOUU5CIiLqcgFxFxOQW5iIjL\nZRPkU4E/AzuA+4xZjoiIpCvTIO8HPEY4zMcBNwJnGrUo6a2hocHuJXiKHk9j6fG0V6ZBPhFoBHYB\nXwLPANcatCaJQy8UY+nxNJYeT3tlGuQjgb/GfP+3yDEREbFYpkGuj/4REXGITD/q7UJgEeEeOcBC\noBNYEnOdRmBsxisTEclNTUC5FXeUH7mz0UAB8A56s1NExHWuAj4gXHkvtHktIiIiIiISS5uFjLUL\neA94G3jT3qW4zpPAHmBzzLFhwEvAduBFYKgN63KreI/nIsKTa29Hvqb2/jVJ4FRgA7AV2AJ8L3Lc\n9udoP8LtltFAf9Q/N8JOwv9jJX2TgPPpHjw/BuZHLt8HPGz1olws3uP5AHCPPctxvROB8ZHLRYTb\n1WfigOfoN4B1Md8viHxJ5nYCx9u9CBcbTffg+TMwInL5xMj3krrR9A7yefYsxXPWAJeT5nPUjJNm\nabOQ8ULAy8AmYJbNa/GCEYTbA0T+HJHkupKau4F3gRWoVZWp0YT/tfMGaT5HzQhybRYy3sWE/wdf\nBdxJ+J+3YowQes5m6xdAGeEWwSfAUnuX40pFQB0wFzjQ42d9PkfNCPKPCDfwo04lXJVL5j6J/LkX\n+APhc91I5vYQ/ucqwEnAZzauxQs+46uweQI9P9PVn3CI/4pwawXSfI6aEeSbgNP4arPQDcCzJtxP\nrhgEDI5cLgSuoHt/UtL3LHBL5PItfPXikcycFHN5Onp+psNHuB21DfhpzHFHPEe1Wcg4ZYQnf94h\nPJ6kxzM9vwU+BjoIv3fzj4QngF5G44eZ6Pl4VgO/JDwe+y7hwNF7Dqm7hPDpTd6h+/imnqMiIiIi\nIiIiIiIiIiIiIiIiIiIiIiIiIiIiXvW/IwghUsJFSIMAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f53d59178d0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from math import exp\n",
    "\n",
    "max_iter = 50000\n",
    "i = 0\n",
    "temp = 200\n",
    "least_walk = None\n",
    "\n",
    "def getTwoIndices():\n",
    "    i1 = random.randint(1, N-1)\n",
    "    while True:\n",
    "        i2 = random.randint(1, N-1)\n",
    "        if (i1 != i2):\n",
    "            return i1, i2\n",
    "\n",
    "def getNextWalk(current):\n",
    "    i1, i2 = getTwoIndices()\n",
    "    new = current.l[:]\n",
    "    new[i1], new[i2] = new[i2], new[i1]\n",
    "    return Walk(new)\n",
    "    \n",
    "\n",
    "while i < max_iter:\n",
    "    c1 = current_walk.cost()\n",
    "    new_walk = getNextWalk(current_walk)\n",
    "    c2 = new_walk.cost()\n",
    "    delta_c = c2 - c1\n",
    "    accept_less_desirable = random.random() < exp(-delta_c/temp)\n",
    "    if delta_c <= 0 or accept_less_desirable:\n",
    "        if not least_walk or new_walk.cost() <= least_walk.cost():\n",
    "            least_walk = new_walk\n",
    "        current_walk = new_walk\n",
    "    \n",
    "    if i%5000 == 0 and temp > 10:\n",
    "        temp -= 1\n",
    "        \n",
    "    i += 1\n",
    "\n",
    "# print least_walk\n",
    "print \"The cost of the solution state %.2f\" % least_walk.cost()\n",
    "\n",
    "get_plot(least_walk)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion\n",
    "\n",
    "We saw how a psuedo optimal solution can be achieved for TSP, a problem that has a huge search space, by the use of Simulated Annealing. Of course, better results can be achieved by tuning the parameters of the algorithm. For more details, see this [wiki](https://en.wikipedia.org/wiki/Simulated_annealing#Selecting_the_parameters)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}