qpwo/traveling salesman - simulated annealing.ipynb

## traveling salesman - simulated annealing.ipynb
{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# September 2018 - Luke Harold Miles - Public Domain\n",
    "# Simulated annealing solution to traveling salesman problem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy\n",
    "import matplotlib.pyplot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_tour(cities, distance):\n",
    "    n = len(cities)\n",
    "    tour = numpy.random.permutation(n) # some ordering of the cities\n",
    "\n",
    "    for temperature in numpy.logspace(4, 0, num=10**5):\n",
    "        i = numpy.random.randint(n - 1) # city 1\n",
    "        j = numpy.random.randint(i + 1, n) # city 2\n",
    "        def length(tour): # sum of distance to and from i and j in tour\n",
    "            return sum(distance(cities[tour[k % n]], cities[tour[(k + 1) % n]])\n",
    "                       for k in [j - 1, j, i - 1, i])\n",
    "        old_length = length(tour)\n",
    "        tour[[i, j]] = tour[[j, i]] # swap i and j in tour\n",
    "        new_length = length(tour)\n",
    "        if numpy.exp((old_length - new_length) / temperature) < numpy.random.random(): # swap was mistake\n",
    "            tour[[i, j]] = tour[[j, i]] # swap them back\n",
    "    return tour"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "cities = numpy.random.randint(0, 100, (15, 2))\n",
    "\n",
    "def euclidean_distance(c1, c2):\n",
    "    return numpy.linalg.norm(c1 - c2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "tour = find_tour(cities, euclidean_distance)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXoAAAD8CAYAAAB5Pm/hAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAAIABJREFUeJzt3Xl4lNX5//H3YRNZBBFU9oAKKhQRE4pF0LiiqFCluLa41UpR0VYRa63fetWK1Lq1X7UWF+w3LhG0YH9uiKMmLpAgqMiirAKiRlnUuLDk/P64ZzqThEDILM8sn9d15ZrMM5PMjU7u58x57nMf571HRESyV6OgAxARkeRSohcRyXJK9CIiWU6JXkQkyynRi4hkOSV6EZEsp0QvIpLllOhFRLKcEr2ISJZrEnQAAO3bt/d5eXlBhyEiklHmzZv3hfe+w66elxaJPi8vj/Ly8qDDEBHJKM651fV53i6nbpxzDznnPnfOLYw51s45N8s591H4du/wceecu8c5t8w5955zbkDD/wkiIpII9ZmjfwQYVuPYRGC29/4gYHb4PsDJwEHhr0uB+xITpoiINNQuE733/nVgQ43DI4Cp4e+nAiNjjj/qzdtAW+dcx0QFKyIiu6+hVTf7ee/Xh7//FNgv/H1nYE3M89aGj4mISEDiLq/01tB+t5vaO+cudc6VO+fKKyoq4g1DRETq0NBE/1lkSiZ8+3n4+Dqga8zzuoSP1eK9f8B7n++9z+/QYZfVQbIDkydDKFT9WChkx0VEIhqa6GcCY8LfjwFmxBz/Rbj6ZhCwOWaKRxKsoABGj44m+1DI7hcUBBuXiKSXXdbRO+ceB44B2jvn1gI3AZOAYufcxcBqYHT46c8BpwDLgG+BC5MQc87zHj7/HPbcEy67DE47DYYOhTffhEcegcLCoCMUkXTi0mHP2Pz8fK8FU1Hew4YNsHIlrFpV+3bVKvjuu7p/fr/9oE8f6NvXbiNfbdumJn4RSQ3n3Dzvff6unpcWK2Nz0ebNtZN4bCL/+uvqz997b+jRAw45BE4+2b7Py4OKCrj2Wjj/fHj4YTj3XPjhB/jgA3jwQaisjP6OTp1qnwAOPRT22itl/2wRCYASfZJUVu54NB653bix+vNbtbLk3aOHTb1EEnnktk2b2q8RCsGFF8JTT9nPjBhhc/TFxXa/qgo+/tiSfuzX/fdX/0TQtWs08UdOAoccYjGJSOZTom+g77+H1avrTuQ1K0b33DOauI88snYib9cOnNu9GMrKokkd7La42I4XFkKjRva78/Jg+PDoz1VVWZw1TwChkH0aiMjLqz7107cvHHwwtGixe3GKSLA0R1+HLVtgzZq6E/n6GrVEzZpB9+61E3jkdt99dz+Rp9r27bB8ee0TwJIlsHWrPcc56Nmz+gmgTx87ATRvHmz8IrmmvnP0OZvot22DdevqTuTr1tnIN6JxY+jWre5E3rGjjaCz0datsGxZ7RPAhx/af0ewf/uBB9Y+AfTubSdBEUm8rE70kydbrXhsGWEoZFMWEybY/aoqG3XXlcjXrIkmKbCRapcudSfyzp2hiSa6qtmyBT76CBYurH4CWLbMPh2AnSB79ap9AjjoIGjaNNj4RTJdVif6yMKgJ5+E1q1h5ky44w449libY161yubPt2yp/nMdO9adyLt21cgzUX74AZYutaQfexJYvtxKR8GSfO/etU8ABxygE6pIfWV1ogdL9iNGVC9D7NCh7kTevbvmkIP23Xc231/zBLByZfQ5e+xhJ4CaawB69LBPByISlfWJHuD662HSJKto+e47GDLEjg0blv4XPiWqshIWL44m/shJ4OOPo89p3txKPmuuA+jePXuvjYjsStYn+sj0zdixcO+9cPbZMGMGrF0Lhx0GEyfCqFGaBshkX38NixbVPgGsi2mT17Jl9AQQexLo2lUne8l+WZ3oI0k+UkMeuV9UBJ98ArfdZlMEPXvaxdkxYzRtk002bdrxCeDTT6PPad3aVv3WXAfQqZNOAJI9sjrR76rqpqrKRve33mrH9t8frr7aGoBpuX/22rChdgnowoXVF6+1aVP7AnCfPvYe0QlAMk1WJ/r68t5OALfeCi+/bH/k48bB+PG2gElyQ0VF7RPABx/Al19Gn9Ou3Y5PAHqfSDpToq+hvNwu3D79tFV2XHwxXHONVeRI7vEePvtsxyeATZuiz2vfvnYFUJ8+sM8+wcUuEqFEX4elS+Evf4FHH7UpnrPPtgu3ffum5OUlzXlv13l2dAKILeVVK2hJB0r0u7B2Ldx5J/zjH1bed+qpVpr5k5+kNAzJEN7be6bmKuBFi9QKWoKjRF9PGzbA3/8O99xjc7aqxZfdEdsKOvYksHixWkFL8inR76bKSpgyBW6/XbX4Er/t260VR80TwJIldbeCjpwA1Apa6kuJvoG2bIHHHlMtviTHtm2wYkXtNQBLl+68FXTfvtYaQu9BiaVEHyfV4ksq1WwFHTkBfPRRw1tB16fLq2Q2JfoEidTiT5oEs2ZZLf6vf221+PvtF3R0ku22bLG+/zVPAMuWRfdLaNLE2j7XPAGsW2d7CNdcQR67K5lkNiX6JCgvtymd6dOtFv+ii6wWv0ePoCOTXPP999FW0LEngRUrqreC7tzZ9mW4+GJL8Ery2UWJPol2VIt/3XXwox8FHZnkum+/jbaCjnzNmmUXgMePh7vuCjpCSSQl+hRYt842PImtxZ84EQYPDjoyERMKwRln2PuzqgqeeQZOOy3oqCRR6pvo1ck7Dp07w1//anXUN98Mb70FRx0FQ4fCc89FP0KLBCEyJ//00/Z+BDjzTHjxxWDjktRTok+Adu3gxhtt+8K777b66eHDoX9/ePzx6nvTiqRKWVl0Tv744+Ff/7Lqnmuuie7pK7lBiT6BWraEK6+0iohHHrE/qnPPtfK3+++3C2giqTJhQvULr+ecY1ONCxfa+1SfOHOHEn0SNGtmC6wWLrQ50fbtbSesvDyr2vnqq6AjlFx19dVw7bW2K9sttwQdjaSKEn0SNWoEI0fC22/DK69Av352sbZbN/jd76xNrkiqTZoE559v041TpgQdjaSCEn0KOGcfoV96yWrxTzjB/tjy8mwjlJUrg45QckmjRvDQQ3DSSfCrX8GzzwYdkSSbEn2KHXEEPPWU1Tqfdx7885+2qvH88+H994OOTnJF06YwbRp07GiN+956K/pYKGTtEyR7KNEHpFcv+9i8ciVcdRX8+982tXPaafDGG0FHJ7mgVStrz71tm43uFy2KlmQWFAQdnSSSEn3AOne21siqxZcgnHGGrfD+5htb2X3yydbIT20Ssktcid45d7Vz7gPn3ELn3OPOuebOuR7OuTnOuWXOuSedczvoqyc1qRZfgnLeeXDFFbZydvt2+OUvre7+ueeijdMkszU40TvnOgNXAvne+75AY+Bs4DbgTu/9gcBG4OJEBJorIrX4y5erFl9SIxSyPRhuvNG6s/7yl3YNafhw2wbxH/+wHjqSueKdumkC7OmcawK0ANYDxwLTwo9PBUbG+Ro5qWlT1eJL8sW2Lr75ZisUeOYZePhhKCqygcdll1lJ8O9/b50wJfM0ONF779cBtwMfYwl+MzAP2OS9j0w0rAU6xxtkLqtZix/Z4lC1+JIIsW0SwG6Li2H+fPskWV4Or71m143+/Gfo3h0uuADefTfQsGU3Nbh7pXNub2A6cBawCXgKG8n/T3jaBudcV+D58NROzZ+/FLgUoFu3bkesXr26QXHkonnzbFQ/bZr64kvqLFtm148eesimco49Fn7zG7uA20hlHYFIRffK44GV3vsK7/1W4GlgMNA2PJUD0AVYt6Mf9t4/4L3P997nd+jQIY4wcs8RR9ioa8kSq79XLb6kwoEHwt/+BmvX2oK/pUutNXdkHv9Pf7KpoFiqyU8P8ST6j4FBzrkWzjkHHAcsAkLAqPBzxgAz4gtR6tKrlyV51eJLKu29t220s3Jl9Xn8v/zFEv+08BU61eSnj7g2HnHO/RGbutkGzAcuwebknwDahY+d773/YWe/J1M3Hkk3GzbA//6vfbz+8ksYMsTm808+2dowiCSD91BSAnfeaYMNgOOOs3l8bV2YXNphKodVVto8amQhVqSZ2s9+ZhtJiyTLsmX2iXLJEsjPtyKCxo2Djip7aYepHNaypS2AWbYMpk6tXYt/yy2aS5XkWLMGvvgCjjzSKnaOOQa++y7oqESJPos1bQq/+IXV4v/739Chg9Xi//WvNur6z3/seZpLlUSIrcl/803rzFpaau+rL78MOrrcpkSfAxo1ghEjrI9OKGR/eJWVcPrptodo5I9Tc6kSj5o1+X//O9x0k03jDB5sbT0kGJqjz1HvvAOnnGILrm64wUrjRJLh9ddtoNG8OTz/vPVvksTQHL3s1ObN0bnTv/2t9py9SKIMHWpTOE2b2vezZgUdUe5Ros9BkbnU6dOhSxerxx89WslekqdPH5s6zMuzT5L/+lfQEeUWJfocFJlLPf5461RYXm410GVlQUcm2axzZ6u3HzLEigQmTdJ+C6miRJ+DJkyIXjC7+GKrc37vPTsukkxt2tg8/TnnwPXXWxnw9u1BR5X9lOhzXOfOdqHsoYfU615SY4894P/+D6691lZy/+xnqrVPNiV6YexYq3OePj3oSCRXNGpkC/TuusvWeBx/vGrtk0mJXjj2WOt+ed99QUciuWb8eLteNG+eau2TSYleaNQIfvUr63ipNseSaqNGwUsv2ZqOI4+0TU8ksZToBbBdg/bYQ6N6CYZq7ZNLiV4A2GcfOOssq2/++uugo5FcFKm179FDtfaJpkQv/zV2LHzzDTz2WNCRSK6qWWt/662qtU8EJXr5rx//2DYfv+8+/XFJcGJr7X/3O7j8ctXax0uJXv7LORvVv/uubRghEpTYWvt777ULtqq1bzgleqnmvPOgdWvboEQkSLG19jNmqNY+Hkr0Uk2rVvDzn8OTT+qPStKDau3jp0QvtVx2GfzwAzzySNCRiJhRo6zkUrX2DaNEL7X86Ec2crr/fqiqCjoaETNkiC3qU6397lOilx0aO9Y2F589O+hIRKIOPdRq7Xv2VK397lCilx0680xbRKWLspJuOne27QmHDlWtfX0p0csO3XOPVTnMmAHr1tmxUMiqIESCFqm1P/dc1drXhxK97FBBgTWa2r4dpkyJbj9YUBB0ZCKmWTObulGt/a4p0csOFRZaf/qmTW3Lt+HD4coroV+/oCMTiYrU2t99t2rtd0aJXupUWAgXXWQ7T23ZAn/4A7Rvb8n+iivsRFBREXSUIjYIeeop1drXRYle6hQKWTK/8UbYe28bNf3pT7D//rb14KhRsO++1nXw17+2RVaffhp01JKrzjxTtfZ1cT4NLlfn5+f78vLyoMOQGJE5+eJiG9nXvL91K5SXw2uv2VdpqXW+BOjdG44+OvrVuXOw/xbJLYsWwbBhsHEjPP00nHBC0BElj3Nunvc+f5fPU6KXHZk82S68FhZGj4VCUFYGEybUfv62bTaCevVVS/wlJfDVV/bYgQdWT/zduqXknyA5bN06q7NftAgefNDKMLOREr0Eavt2WLAgOuIvKbERFtjGErGJPy/POmeKJNLmzXDGGfDKK3DLLXD99dn3PlOil7RSVWX70b72mo36X389Wh3RtSscc0w08R9wQPb9QUowtmyBCy+0zXTGjoW//Q0aNw46qsRRope0VlVlH6sjI/5XX41W8HTqZAk/kvx79VLil4arqoKJE+Evf4GRIy3p77ln0FElRkoSvXOuLTAF6At44CJgKfAkkAesAkZ77zfu7Pco0Yv3sGRJ9cQfqeDZf39b7h5J/occEk38u3stQXLXPffAVVfBoEHw7LPW4iPTpSrRTwVKvPdTnHPNgBbA74AN3vtJzrmJwN7e++t29nuU6KUm7+Gjj6on/kgrhg4dool/zz1t7rWu6iCRWNOn2+Y6eXnWQqFHj6Ajik/SE71zrg2wAOjpY36Jc24pcIz3fr1zriPwqve+985+lxK97Ir3sGJFNPG/9hqsXm2PtW5t/fNPPNG2QFSSl50pKYHTT7ftCp97DgYMCDqihktFou8PPAAsAg4D5gHjgXXe+7bh5zhgY+R+jZ+/FLgUoFu3bkesjvzVitTTqlXRpP/EE9bn5JprbC5WZGdia+2nT7dBQiaqb6KPZ2VsE2AAcJ/3/nCgEpgY+4TwSH+HZxLv/QPe+3zvfX6HDh3iCENyVV4ejBljWx9u2WILsx55xKZvRHYmtq/98OHw6KNBR5Rc8ST6tcBa7/2c8P1pWOL/LDxlQ/j28/hCFKlbKGRL37dvt8qK4mKbo1eyl12J7Ws/Zgz8+c/Z29e+wYnee/8psMY5F5l/Pw6bxpkJjAkfGwPMiCtCkZ0oK4OTTrLa6NGjbW6+uNiOi+xKbF/7G26AceOys699vFU3/bHyymbACuBC7ORRDHQDVmPllRt29nt0MVYaqqrKpnD69rULayINUVVl1VuTJ2dWrX195+ibxPMi3vsFwI5e5Lh4fq9IfZWWwpo1tp2cSEM1agS33QZdusD48XDccdlTaw9qUywZ7rHHoEULGDEi6EgkG1xxhfW1f+cd62u/cmXQESWGEr1krC1b7I9y5Eho1SroaCRbnHkmvPwyfP659bV/552gI4qfEr1krBdegA0bbKWjSCIddRS88YYtqjr6aNs/OZMp0UvGKiqyrQ2zeWMJCc4hh2RPrb0SvWSkr76CmTPhrLNsA3ORZOjUyWrtjz46s2vtleglIz3zjG1armkbSbY2bax097zzMrfWPq7ySpGgFBXZR+pBg4KORHJBs2Y2ddO5s9Xar1+fObX2oBG9ZKBPP4XZs201ozYkkVSJ1Nrfcw/MmGG19l98EXRU9aNELxnniSdsJaOmbSQImVhrr0QvGaeoyHqIH3xw0JFIrorU2ldUZEatvRK9ZJQPP4Tycpu2EQlSzVr7F18MOqK6KdFLRikqsnn5s88OOhKR6rX2p54KU6cGHdGOKdFLxvDeEn1hoVU/iKSD2Fr7Cy5Iz1p7JXrJGHPnwvLluggr6admrf2vf51etfaqo5eMUVRk86Fnnhl0JCK11VVr36JF0JFpRC8ZYts2ePJJmwdt0yboaER2LLbWfubM9Km1V6KXjBBpG6tpG8kEkVr7+fPTo9ZeiV4yQlERtG0Lp5wSdCQi9ZNOtfZK9JL2KiutidmoUTZHL5Ip0qXWXole0t7MmZbsNW0jmSgdau2V6CXtFRXZps1DhwYdiUjDdOoEJSXRWvthw+CVV6o/JxSyap1kUKKXtPbFF/Zx95xzrKJBJFPttVe01v7FF23XqpdftsdCIRg9GgoKkvPa+tORtFZcbKWVmraRbBCptb/uOts4Z/hwuP56S/LFxbbqOxmU6CWtFRVBnz7Qr1/QkYgkRqNGMGmSfW3ZYrdjxyYvyYMSvaSxlSvhzTdtNK8NRiTbVFba7SWXwH332fRNsijRS9p6/HG7VUtiyTahENx+u21sf++9Nm0zenTykr0SvaSlSKfKo46C7t2DjkYkscrKrNyyoMCSfWGhJfuysuS8nhK9pKV334VFi3QRVrLT1VdbJ9Yf/zh6rLAQJkxIzusp0UtaKiqCJk1sNaxItnn/fau6iU30yaREL2ln+3abnx82DNq3DzoakcSbM8duleglZ73+Oqxbp2kbyV5z5sC++6bu+pMSvaSFyZOjFQdFRdCqlfWdT9aScJEgzZkDAwemrmw47kTvnGvsnJvvnPtP+H4P59wc59wy59yTzrlm8Ycp2a6gwMrLXnwRpk2ztq6/+EXyloSLBGXTJliyJHXTNpCYEf14YHHM/duAO733BwIbgYsT8BqS5SLlZaNHw+bNtj9sMpeEiwQlUkKZMYneOdcFGA5MCd93wLHAtPBTpgIj43kNyR2FhdC7t30/bpySvGSnyIXYVH5ajXdEfxcwAagK398H2OS93xa+vxboHOdrSI4IhWwXnrw8eOCB5C4JFwnKnDlw8MG2Y1qqNDjRO+dOBT733s9r4M9f6pwrd86VV1RUNDQMyRKhEPzsZ1ZaOWZM8peEiwTBe5uWTOW0DcQ3oh8MnO6cWwU8gU3Z3A20dc41CT+nC7BuRz/svX/Ae5/vvc/v0KFDHGFINigrg2uuse+HDEn+knCRIKxebZvcZ0yi995f773v4r3PA84GXvHenweEgMh6xjHAjLijlKw3YQJ8/TU0bgyDBtmxZC4JFwlCqhdKRSSjjv464DfOuWXYnP2DSXgNyUIlJTBgALRsGXQkIskxZw40bw4/+lFqX7fJrp+ya977V4FXw9+vAAYm4vdK7vjhB5u7HDcu6EhEkmfOHBvMNG2a2tfVylhJC+XlluyHDAk6EpHk2LrVqspSPW0DSvSSJkpK7Hbw4GDjEEmW995LbcfKWEr0khZKSqy2WAVYkq3mzrVbJXrJSVVV8MYbtpuUSLZKdcfKWEr0EriFC62/jebnJZvNmWOj+SA2uleil8BF5ueV6CVbBdGxMpYSvQSutBQ6dbIeNyLZKLLCe2BAhedK9BIo721EP2RIMB9pRVIhiI6VsZToJVCrV9u2gZq2kWwWRMfKWEr0EqjI/LwqbiRbBdWxMpYSvQSqpMT2hu3bN+hIRJIjqI6VsZToJVClpbYatnHjoCMRSY6gOlbGUqKXwHzxBSxerGkbyW5BdayMpUQvgSkttVtdiJVsNmcOHHFE6jtWxlKil8CUlsIeewRXciaSbJGOlUHVz0co0UtgSkosye+xR9CRiCRHkB0rYynRSyAqK22ko2kbyWbpcCEWlOglIHPmwLZtSvTZZPJkCIWqHwuF7Hiumjs3uI6VsZToJRAlJdby4Mgjg45EEqWgAEaPjib7UMju5/I1mCA7VsZKyJ6xIrurpAT69QtuSbgkXmEh3HknnHQSdOsG69fDDTfAoYcGHVkwIh0rzz8/6Eg0opcAbN0Kb7+taZtsM2sWXHmlLX5bvhy+/dYS/f77W+I/80yYNAlmz7b9B7JdpGNl0PPzoBG9BGDBArsYq4VS2cF7uOsuuOYaS+jOwbXXwr33wh/+ANu3W9IrK4Onn47+XK9eNq0zcKDd9u8Pe+4Z3L8j0YLuWBlLiV5STo3Mssf338Nll8HUqfb/c/FimDbNpnEKC22OvrgYrr7anr9hA5SXRxN/KARFRfZYkybW86igIPrVp0+wC43iEelY2aZN0JGA894HHQP5+fm+vLw86DAkRc44w0b1K1YEHYnEY/16+OlPLaH9z//YMv+BAy3BR4RCltAnTKj793zySTTxR742brTHmjeHww+PJv6BA+HAA6FRmk46n3IKHH+8ndj228/u9+sHL78Mzz2X+Ndzzs3z3ufv6nka0UtKeW8rYk8+OehIJB5z51qS37wZpk+3k/eOREb2O9OpE4wYYV9g75EVK+w1Iol/yhS45x57vE0byM+vPvLv0iX4yhawJH/NNfbJpaICvv7a7t9+e7BxKdFLSn34of0B6EJs5nr0Ubj0UkvQb72V+GZdzsEBB9jXOefYsW3bbFoodtT/17/ahX2w0XNs4i8ogPbtExtXffzmN3b729/a7TPPWJKPHA+Kpm4kpaZMgV/+0v5oDz446Ghkd2zbBtddB3fcYaP04uJgkmnE999bi4Gysujof8kS+0QAtgdx5EJvQQEMGACtW6cmttat4Ztv7ILz0qXJex1N3UhaKimBDh2gd++gI5HdsXEjnH02vPQSXH65JfugL5JGrgkMHAjjxtmxr76y1hqRUf/cuXZCAvukcMgh1Uf9hx2W+F5Ld9xhVWUtW9on2EmTYOLExL7G7lKil5QqLbXqjHSYT5X6WbwYTj/ddkr65z/hkkuCjqhue+0FxxxjXxEVFdUrfZ5/3qqEwE5W/fpVv9h7yCEN3wjnjjuic/IDBtgnn+uvh2bNgp2+0dSNpMwnn0Dnzja3GvScpdTPs8/CeedBixZWA/+TnwQdUfy8hzVrqs/3l5fbpwGwkfiAAdVH/j171m9wEqm6iby/f/pT+H//z65JzZ6d+H+Lpm4k7UTq53UhNv15D7feCr//vSW9Z56Brl2DjioxnLOFXZHVugBVVfDRR9WT/7332nUAgHbtalf6dOpU+3fXLKGcPNkSfc+eyf037YpG9JIyV1wBDz9sPUCaaIiRtior4aKLbG773HPtAno2rVitr61b4YMPqpd5LlxoK33BEn3sxd78fNh779q/Z8gQm7JcsMCuCUD91hfUR31H9Er0kjL9+1uVxssvBx2J1OXjj62e/d134bbbbL5Z11Oivv3WEnbsyP/DD6OPH3hg9VH/gAH2fh850t7/8+bBq69GVwzvao3BriR96sY51xV4FNgP8MAD3vu7nXPtgCeBPGAVMNp7v7GhryPZYdMmK4W76aagI5G6vP46jBoFW7bYdIMWtdXWooVdp4i9VrFpkyXwSOIvKYHHH7fHGjWyNg777gvz59snpJdfTkyS3x3xfIDeBvzWe/+Oc641MM85Nwu4AJjtvZ/knJsITASuiz9UyWRvvWXzvpqfT0/3329Taz17wsyZKn/dHW3bwnHH2VfEp59WH/V/8okdf+IJuPHG1CZ5iKNNsfd+vff+nfD3XwOLgc7ACCBcvMRUYGS8QUrmKymxefl0aNkqUVu2wNix9nXCCda3Rkk+fvvvD6edBjffbOWcxcV2QXfCBLjvvto7cSVbQloDOefygMOBOcB+3vv14Yc+xaZ2JMeVlNh8ZcuWQUciERUVltzvv99WvD77rDaCSYZQCM46y7p63nabJf3YnbhSIe5E75xrBUwHrvLefxX7mLcrvTu82uucu9Q5V+6cK6+oqIg3DElj339vlQuatkkfCxZYlcjcudYmeNKkhi8Skp0rK6s+Jx9pHxHZmCQV4ipyc841xZJ8kfc+sqXAZ865jt779c65jsDnO/pZ7/0DwANgVTfxxCHprbzcpgjUfz49PPUUXHCBTSWUlsIRRwQdUXbbUQllfbp6JlKDR/TOOQc8CCz23t8R89BMYEz4+zHAjIaHJ9mgtNRuleiDVVVlC6BGj7ZSv7IyJflcEc+IfjDwc+B959yC8LHfAZOAYufcxcBqYHR8IUqmKymx/iFBdjrMRZMETK4HAAAKg0lEQVQnWy13YaEt7z//fJuHLyiAV15JfDMvSV8NTvTe+1KgrqUUx9VxXHLM9u3wxhs2ipTUKiiw/+533mntDJYsgVatbD5eST63aCG6JNUHH9guRLoQm1pr18Ly5fZJ6uc/txYGrVtbz5pU13BL8JToJanUyCw1fvjBroW88IJ9LVxox7t0sT1X58+3dgZK8rlJiV6SqqTEWhN37x50JNln5UpbjPPCCzbnXllp/dWHDoUxY6yFwWefWQ33jTfaQp1UV3tIelCil6Tx3hL90KFqjJUI330Hr71mif3556PNtHr0sMQ+bJgl8Vat7HhkoU6khruwMHHNtCSzKNFL0qxaZT0+VFbZMN5bj/TIqP3VV23xWfPmtoPSuHGW3A86aMcn0p0t1FGizy1K9JI0mp/ffd98YyPxSHJfudKO9+4Nv/qVJfajj65ff/h0WKgj6UGJXpKmtBTatIG+fYOOJH15b5VJkemYkhLb8KJlS+uGeO21cNJJwe9QJJlNiV6SpqQEBg+2ntwStXmz7R8aGbWvXWvH+/aF8ePtIurgwap1l8RRopekqKiwBTpjxuz6udmuqsp2bIqM2t980xaS7bWXdY+86SabkunSJehIJVsp0UtSvPGG3ebq/PyGDfDSS9G69s8+s+OHH24tgYcNg0GDrBxSJNmU6CUpSkps6iF/l7tZZoft2207uch0zNy5NpJv1w5OPNGmY0480TakEEk1JXpJipISGDgwu+eZP/ssOmp/8UX48ksrcywosAVKw4bZ9+rzLkFTopeEq6yEd96xKYpssm2bbbUXGbXPm2fH990XTjnFRu0nnKAunZJ+lOgl4d5+26YysmGh1Lp1Nlp//nmYNcsqZho3hiOPhD/9yZJ7//6qLJL0pkQvCVdaalMYP/lJ0JHsvi1b7EJy5CLqe+/Z8U6dYNQom445/njtrSqZRYleEq6kBA47zBZLZYLVq6PTMbNn2+rUpk3tE8nkyZbc+/ZVvx7JXEr0klBbt8Jbb8FFFwUdSd2+/x5efz1a175kiR3v3t12YRo2DI491vq3i2QDJXpJqAUL4Ntv069+ftmy6Kg9FLJOkHvsYX1jIj1kevfWqF2ykxK9JFSkkVnQF2IrK63bYyS5L19uxw86CC65xC6iHn00tGgRaJgiKaFELwlVUmINuDp1Su3reg+LF0enY15/3S6stmhh0zBXX22j9gMOSG1cIulAiV4SxnuruBk+PDWv99VXtrNSZNT+8cd2/NBD4fLLbdR+1FHWv10klynRS8IsXQpffJG8+XnvrdwxMmp/4w1bxNS6tZU83nCDjdq7dUvO64tkKiV6SZhkzM9v3GgLlSJ17evX2/HDDrPNrocNs3p9NQcTqZsSvSRMaSl06AC9ejX8d1RVWfuEyHTM22/bsbZtqzcHS/U1AJFMpkQvCVNSYqP53S1RrKio3hysosKO5+dHp2MGDoQmereKNIj+dCQh1q2z/U2vuGLXz92+3dr4Rkbt5eU2/96+vW2bF2kOtu++yY9bJBco0UtClJbabV0XYtevr94cbONGawQ2aBD88Y+W3AcMUHMwkWRQope4TJ5sPddLSmxD6/79beXp22/bRdLIRdQFC+z5HTvCyJHR5mDt2gUbv0guUKKXuBQUwOjR1sCsVy/rQf/3v1sr3+++s3n1wYNh0iRL7v36qc2ASKop0UtcCgth6tToIqn5863y5qc/tcR+3HG2CbaIBEeJXuJ28sk2TfPmm3DZZXDvvRq1i6QTXfqSuL36Knz4oe2TOm2a3ReR9JGURO+cG+acW+qcW+acm5iM15D0EArZHH1xMdx8s92OHm3HRSQ9JDzRO+caA/8LnAwcCpzjnDs00a8j6aGszJJ7YaHdLyy0+2VlwcYlIlHJmKMfCCzz3q8AcM49AYwAFiXhtSRgEybUPlZYGE38IhK8ZEzddAbWxNxfGz4mIiIBCOxirHPuUudcuXOuvCLS3ERERBIuGYl+HdA15n6X8LFqvPcPeO/zvff5HTp0SEIYIiICyUn0ZcBBzrkezrlmwNnAzCS8joiI1EPCL8Z677c55y4HXgQaAw957z9I9OuIiEj9OO990DHgnKsAVgcdRz21B74IOogGUuzBUOzByNTYdyfu7t77Xc59p0WizyTOuXLvfX7QcTSEYg+GYg9GpsaejLjVAkFEJMsp0YuIZDkl+t33QNABxEGxB0OxByNTY0943JqjFxHJchrRi4hkOSX6nXDOdXXOhZxzi5xzHzjnxoePt3POzXLOfRS+3TvoWGtyzjV3zs11zr0bjv2P4eM9nHNzwi2knwwvaks7zrnGzrn5zrn/hO9nStyrnHPvO+cWOOfKw8fS/v0C4Jxr65yb5pxb4pxb7Jw7MhNid871Dv/3jnx95Zy7KhNiB3DOXR3+G13onHs8/Leb0Pe7Ev3ObQN+670/FBgEjAu3XJ4IzPbeHwTMDt9PNz8Ax3rvDwP6A8Occ4OA24A7vfcHAhuBiwOMcWfGA4tj7mdK3ACF3vv+MSVymfB+AbgbeMF7fzBwGPbfP+1j994vDf/37g8cAXwLPEMGxO6c6wxcCeR77/tii0zPJtHvd++9vur5BcwATgCWAh3DxzoCS4OObRdxtwDeAX6MLcRoEj5+JPBi0PHtIN4u2B/mscB/AJcJcYdjWwW0r3Es7d8vQBtgJeHrdpkUe414TwTeyJTYiXb7bYd1KvgPcFKi3+8a0deTcy4POByYA+znvV8ffuhTYL+Awtqp8PTHAuBzYBawHNjkvd8Wfkq6tpC+C5gAVIXv70NmxA3ggZecc/Occ5eGj2XC+6UHUAE8HJ4ym+Kca0lmxB7rbODx8PdpH7v3fh1wO/AxsB7YDMwjwe93Jfp6cM61AqYDV3nvv4p9zNspNy1Ll7z32719nO2CbQhzcMAh7ZJz7lTgc+/9vKBjaaCjvPcDsB3WxjnnhsY+mMbvlybAAOA+7/3hQCU1pjrSOHYAwvPYpwNP1XwsXWMPXzcYgZ1oOwEtgWGJfh0l+l1wzjXFknyR9/7p8OHPnHMdw493xEbMact7vwkIYR8B2zrnIs3sdthCOmCDgdOdc6uAJ7Dpm7tJ/7iB/47Q8N5/js0TDyQz3i9rgbXe+znh+9OwxJ8JsUecDLzjvf8sfD8TYj8eWOm9r/DebwWexv4GEvp+V6LfCeecAx4EFnvv74h5aCYwJvz9GGzuPq045zo459qGv98Tu7awGEv4o8JPS7vYvffXe++7eO/zsI/hr3jvzyPN4wZwzrV0zrWOfI/NFy8kA94v3vtPgTXOud7hQ8dh23+mfewxziE6bQOZEfvHwCDnXItwvon8d0/o+10LpnbCOXcUUAK8T3S++HfYPH0x0A3rujnae78hkCDr4JzrB0zFruI3Aoq99zc753piI+V2wHzgfO/9D8FFWjfn3DHANd77UzMh7nCMz4TvNgEe897f4pzbhzR/vwA45/oDU4BmwArgQsLvHdI/9pZY0uzpvd8cPpYp/93/CJyFVfnNBy7B5uQT9n5XohcRyXKauhERyXJK9CIiWU6JXkQkyynRi4hkOSV6EZEsp0QvIpLllOhFRLKcEr2ISJb7/zLYB3cbUEk1AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "xcoords, ycoords = list(zip(*cities[tour].tolist(), cities[tour[0]].tolist()))\n",
    "matplotlib.pyplot.plot(xcoords, ycoords, 'xb-')\n",
    "matplotlib.pyplot.show() # graph the tour"
   ]
  }
 ],
 "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.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
	{
	"cells": [
	{
	"cell_type": "code",
	"execution_count": null,
	"metadata": {},
	"outputs": [],
	"source": [
	"# September 2018 - Luke Harold Miles - Public Domain\n",
	"# Simulated annealing solution to traveling salesman problem"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 1,
	"metadata": {},
	"outputs": [],
	"source": [
	"import numpy\n",
	"import matplotlib.pyplot"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 2,
	"metadata": {},
	"outputs": [],
	"source": [
	"def find_tour(cities, distance):\n",
	" n = len(cities)\n",
	" tour = numpy.random.permutation(n) # some ordering of the cities\n",
	"\n",
	" for temperature in numpy.logspace(4, 0, num=10**5):\n",
	" i = numpy.random.randint(n - 1) # city 1\n",
	" j = numpy.random.randint(i + 1, n) # city 2\n",
	" def length(tour): # sum of distance to and from i and j in tour\n",
	" return sum(distance(cities[tour[k % n]], cities[tour[(k + 1) % n]])\n",
	" for k in [j - 1, j, i - 1, i])\n",
	" old_length = length(tour)\n",
	" tour[[i, j]] = tour[[j, i]] # swap i and j in tour\n",
	" new_length = length(tour)\n",
	" if numpy.exp((old_length - new_length) / temperature) < numpy.random.random(): # swap was mistake\n",
	" tour[[i, j]] = tour[[j, i]] # swap them back\n",
	" return tour"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 3,
	"metadata": {},
	"outputs": [],
	"source": [
	"cities = numpy.random.randint(0, 100, (15, 2))\n",
	"\n",
	"def euclidean_distance(c1, c2):\n",
	" return numpy.linalg.norm(c1 - c2)"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 4,
	"metadata": {},
	"outputs": [],
	"source": [
	"tour = find_tour(cities, euclidean_distance)"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 5,
	"metadata": {},
	"outputs": [
	{
	"data": {
	"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXoAAAD8CAYAAAB5Pm/hAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAAIABJREFUeJzt3Xl4lNX5//H3YRNZBBFU9oAKKhQRE4pF0LiiqFCluLa41UpR0VYRa63fetWK1Lq1X7UWF+w3LhG0YH9uiKMmLpAgqMiirAKiRlnUuLDk/P64ZzqThEDILM8sn9d15ZrMM5PMjU7u58x57nMf571HRESyV6OgAxARkeRSohcRyXJK9CIiWU6JXkQkyynRi4hkOSV6EZEsp0QvIpLllOhFRLKcEr2ISJZrEnQAAO3bt/d5eXlBhyEiklHmzZv3hfe+w66elxaJPi8vj/Ly8qDDEBHJKM651fV53i6nbpxzDznnPnfOLYw51s45N8s591H4du/wceecu8c5t8w5955zbkDD/wkiIpII9ZmjfwQYVuPYRGC29/4gYHb4PsDJwEHhr0uB+xITpoiINNQuE733/nVgQ43DI4Cp4e+nAiNjjj/qzdtAW+dcx0QFKyIiu6+hVTf7ee/Xh7//FNgv/H1nYE3M89aGj4mISEDiLq/01tB+t5vaO+cudc6VO+fKKyoq4g1DRETq0NBE/1lkSiZ8+3n4+Dqga8zzuoSP1eK9f8B7n++9z+/QYZfVQbIDkydDKFT9WChkx0VEIhqa6GcCY8LfjwFmxBz/Rbj6ZhCwOWaKRxKsoABGj44m+1DI7hcUBBuXiKSXXdbRO+ceB44B2jvn1gI3AZOAYufcxcBqYHT46c8BpwDLgG+BC5MQc87zHj7/HPbcEy67DE47DYYOhTffhEcegcLCoCMUkXTi0mHP2Pz8fK8FU1Hew4YNsHIlrFpV+3bVKvjuu7p/fr/9oE8f6NvXbiNfbdumJn4RSQ3n3Dzvff6unpcWK2Nz0ebNtZN4bCL/+uvqz997b+jRAw45BE4+2b7Py4OKCrj2Wjj/fHj4YTj3XPjhB/jgA3jwQaisjP6OTp1qnwAOPRT22itl/2wRCYASfZJUVu54NB653bix+vNbtbLk3aOHTb1EEnnktk2b2q8RCsGFF8JTT9nPjBhhc/TFxXa/qgo+/tiSfuzX/fdX/0TQtWs08UdOAoccYjGJSOZTom+g77+H1avrTuQ1K0b33DOauI88snYib9cOnNu9GMrKokkd7La42I4XFkKjRva78/Jg+PDoz1VVWZw1TwChkH0aiMjLqz7107cvHHwwtGixe3GKSLA0R1+HLVtgzZq6E/n6GrVEzZpB9+61E3jkdt99dz+Rp9r27bB8ee0TwJIlsHWrPcc56Nmz+gmgTx87ATRvHmz8IrmmvnP0OZvot22DdevqTuTr1tnIN6JxY+jWre5E3rGjjaCz0datsGxZ7RPAhx/af0ewf/uBB9Y+AfTubSdBEUm8rE70kydbrXhsGWEoZFMWEybY/aoqG3XXlcjXrIkmKbCRapcudSfyzp2hiSa6qtmyBT76CBYurH4CWLbMPh2AnSB79ap9AjjoIGjaNNj4RTJdVif6yMKgJ5+E1q1h5ky44w449libY161yubPt2yp/nMdO9adyLt21cgzUX74AZYutaQfexJYvtxKR8GSfO/etU8ABxygE6pIfWV1ogdL9iNGVC9D7NCh7kTevbvmkIP23Xc231/zBLByZfQ5e+xhJ4CaawB69LBPByISlfWJHuD662HSJKto+e47GDLEjg0blv4XPiWqshIWL44m/shJ4OOPo89p3txKPmuuA+jePXuvjYjsStYn+sj0zdixcO+9cPbZMGMGrF0Lhx0GEyfCqFGaBshkX38NixbVPgGsi2mT17Jl9AQQexLo2lUne8l+WZ3oI0k+UkMeuV9UBJ98ArfdZlMEPXvaxdkxYzRtk002bdrxCeDTT6PPad3aVv3WXAfQqZNOAJI9sjrR76rqpqrKRve33mrH9t8frr7aGoBpuX/22rChdgnowoXVF6+1aVP7AnCfPvYe0QlAMk1WJ/r68t5OALfeCi+/bH/k48bB+PG2gElyQ0VF7RPABx/Al19Gn9Ou3Y5PAHqfSDpToq+hvNwu3D79tFV2XHwxXHONVeRI7vEePvtsxyeATZuiz2vfvnYFUJ8+sM8+wcUuEqFEX4elS+Evf4FHH7UpnrPPtgu3ffum5OUlzXlv13l2dAKILeVVK2hJB0r0u7B2Ldx5J/zjH1bed+qpVpr5k5+kNAzJEN7be6bmKuBFi9QKWoKjRF9PGzbA3/8O99xjc7aqxZfdEdsKOvYksHixWkFL8inR76bKSpgyBW6/XbX4Er/t260VR80TwJIldbeCjpwA1Apa6kuJvoG2bIHHHlMtviTHtm2wYkXtNQBLl+68FXTfvtYaQu9BiaVEHyfV4ksq1WwFHTkBfPRRw1tB16fLq2Q2JfoEidTiT5oEs2ZZLf6vf221+PvtF3R0ku22bLG+/zVPAMuWRfdLaNLE2j7XPAGsW2d7CNdcQR67K5lkNiX6JCgvtymd6dOtFv+ii6wWv0ePoCOTXPP999FW0LEngRUrqreC7tzZ9mW4+GJL8Ery2UWJPol2VIt/3XXwox8FHZnkum+/jbaCjnzNmmUXgMePh7vuCjpCSSQl+hRYt842PImtxZ84EQYPDjoyERMKwRln2PuzqgqeeQZOOy3oqCRR6pvo1ck7Dp07w1//anXUN98Mb70FRx0FQ4fCc89FP0KLBCEyJ//00/Z+BDjzTHjxxWDjktRTok+Adu3gxhtt+8K777b66eHDoX9/ePzx6nvTiqRKWVl0Tv744+Ff/7Lqnmuuie7pK7lBiT6BWraEK6+0iohHHrE/qnPPtfK3+++3C2giqTJhQvULr+ecY1ONCxfa+1SfOHOHEn0SNGtmC6wWLrQ50fbtbSesvDyr2vnqq6AjlFx19dVw7bW2K9sttwQdjaSKEn0SNWoEI0fC22/DK69Av352sbZbN/jd76xNrkiqTZoE559v041TpgQdjaSCEn0KOGcfoV96yWrxTzjB/tjy8mwjlJUrg45QckmjRvDQQ3DSSfCrX8GzzwYdkSSbEn2KHXEEPPWU1Tqfdx7885+2qvH88+H994OOTnJF06YwbRp07GiN+956K/pYKGTtEyR7KNEHpFcv+9i8ciVcdRX8+982tXPaafDGG0FHJ7mgVStrz71tm43uFy2KlmQWFAQdnSSSEn3AOne21siqxZcgnHGGrfD+5htb2X3yydbIT20Ssktcid45d7Vz7gPn3ELn3OPOuebOuR7OuTnOuWXOuSedczvoqyc1qRZfgnLeeXDFFbZydvt2+OUvre7+ueeijdMkszU40TvnOgNXAvne+75AY+Bs4DbgTu/9gcBG4OJEBJorIrX4y5erFl9SIxSyPRhuvNG6s/7yl3YNafhw2wbxH/+wHjqSueKdumkC7OmcawK0ANYDxwLTwo9PBUbG+Ro5qWlT1eJL8sW2Lr75ZisUeOYZePhhKCqygcdll1lJ8O9/b50wJfM0ONF779cBtwMfYwl+MzAP2OS9j0w0rAU6xxtkLqtZix/Z4lC1+JIIsW0SwG6Li2H+fPskWV4Or71m143+/Gfo3h0uuADefTfQsGU3Nbh7pXNub2A6cBawCXgKG8n/T3jaBudcV+D58NROzZ+/FLgUoFu3bkesXr26QXHkonnzbFQ/bZr64kvqLFtm148eesimco49Fn7zG7uA20hlHYFIRffK44GV3vsK7/1W4GlgMNA2PJUD0AVYt6Mf9t4/4L3P997nd+jQIY4wcs8RR9ioa8kSq79XLb6kwoEHwt/+BmvX2oK/pUutNXdkHv9Pf7KpoFiqyU8P8ST6j4FBzrkWzjkHHAcsAkLAqPBzxgAz4gtR6tKrlyV51eJLKu29t220s3Jl9Xn8v/zFEv+08BU61eSnj7g2HnHO/RGbutkGzAcuwebknwDahY+d773/YWe/J1M3Hkk3GzbA//6vfbz+8ksYMsTm808+2dowiCSD91BSAnfeaYMNgOOOs3l8bV2YXNphKodVVto8amQhVqSZ2s9+ZhtJiyTLsmX2iXLJEsjPtyKCxo2Djip7aYepHNaypS2AWbYMpk6tXYt/yy2aS5XkWLMGvvgCjjzSKnaOOQa++y7oqESJPos1bQq/+IXV4v/739Chg9Xi//WvNur6z3/seZpLlUSIrcl/803rzFpaau+rL78MOrrcpkSfAxo1ghEjrI9OKGR/eJWVcPrptodo5I9Tc6kSj5o1+X//O9x0k03jDB5sbT0kGJqjz1HvvAOnnGILrm64wUrjRJLh9ddtoNG8OTz/vPVvksTQHL3s1ObN0bnTv/2t9py9SKIMHWpTOE2b2vezZgUdUe5Ros9BkbnU6dOhSxerxx89WslekqdPH5s6zMuzT5L/+lfQEeUWJfocFJlLPf5461RYXm410GVlQUcm2axzZ6u3HzLEigQmTdJ+C6miRJ+DJkyIXjC7+GKrc37vPTsukkxt2tg8/TnnwPXXWxnw9u1BR5X9lOhzXOfOdqHsoYfU615SY4894P/+D6691lZy/+xnqrVPNiV6YexYq3OePj3oSCRXNGpkC/TuusvWeBx/vGrtk0mJXjj2WOt+ed99QUciuWb8eLteNG+eau2TSYleaNQIfvUr63ipNseSaqNGwUsv2ZqOI4+0TU8ksZToBbBdg/bYQ6N6CYZq7ZNLiV4A2GcfOOssq2/++uugo5FcFKm179FDtfaJpkQv/zV2LHzzDTz2WNCRSK6qWWt/662qtU8EJXr5rx//2DYfv+8+/XFJcGJr7X/3O7j8ctXax0uJXv7LORvVv/uubRghEpTYWvt777ULtqq1bzgleqnmvPOgdWvboEQkSLG19jNmqNY+Hkr0Uk2rVvDzn8OTT+qPStKDau3jp0QvtVx2GfzwAzzySNCRiJhRo6zkUrX2DaNEL7X86Ec2crr/fqiqCjoaETNkiC3qU6397lOilx0aO9Y2F589O+hIRKIOPdRq7Xv2VK397lCilx0680xbRKWLspJuOne27QmHDlWtfX0p0csO3XOPVTnMmAHr1tmxUMiqIESCFqm1P/dc1drXhxK97FBBgTWa2r4dpkyJbj9YUBB0ZCKmWTObulGt/a4p0csOFRZaf/qmTW3Lt+HD4coroV+/oCMTiYrU2t99t2rtd0aJXupUWAgXXWQ7T23ZAn/4A7Rvb8n+iivsRFBREXSUIjYIeeop1drXRYle6hQKWTK/8UbYe28bNf3pT7D//rb14KhRsO++1nXw17+2RVaffhp01JKrzjxTtfZ1cT4NLlfn5+f78vLyoMOQGJE5+eJiG9nXvL91K5SXw2uv2VdpqXW+BOjdG44+OvrVuXOw/xbJLYsWwbBhsHEjPP00nHBC0BElj3Nunvc+f5fPU6KXHZk82S68FhZGj4VCUFYGEybUfv62bTaCevVVS/wlJfDVV/bYgQdWT/zduqXknyA5bN06q7NftAgefNDKMLOREr0Eavt2WLAgOuIvKbERFtjGErGJPy/POmeKJNLmzXDGGfDKK3DLLXD99dn3PlOil7RSVWX70b72mo36X389Wh3RtSscc0w08R9wQPb9QUowtmyBCy+0zXTGjoW//Q0aNw46qsRRope0VlVlH6sjI/5XX41W8HTqZAk/kvx79VLil4arqoKJE+Evf4GRIy3p77ln0FElRkoSvXOuLTAF6At44CJgKfAkkAesAkZ77zfu7Pco0Yv3sGRJ9cQfqeDZf39b7h5J/occEk38u3stQXLXPffAVVfBoEHw7LPW4iPTpSrRTwVKvPdTnHPNgBbA74AN3vtJzrmJwN7e++t29nuU6KUm7+Gjj6on/kgrhg4dool/zz1t7rWu6iCRWNOn2+Y6eXnWQqFHj6Ajik/SE71zrg2wAOjpY36Jc24pcIz3fr1zriPwqve+985+lxK97Ir3sGJFNPG/9hqsXm2PtW5t/fNPPNG2QFSSl50pKYHTT7ftCp97DgYMCDqihktFou8PPAAsAg4D5gHjgXXe+7bh5zhgY+R+jZ+/FLgUoFu3bkesjvzVitTTqlXRpP/EE9bn5JprbC5WZGdia+2nT7dBQiaqb6KPZ2VsE2AAcJ/3/nCgEpgY+4TwSH+HZxLv/QPe+3zvfX6HDh3iCENyVV4ejBljWx9u2WILsx55xKZvRHYmtq/98OHw6KNBR5Rc8ST6tcBa7/2c8P1pWOL/LDxlQ/j28/hCFKlbKGRL37dvt8qK4mKbo1eyl12J7Ws/Zgz8+c/Z29e+wYnee/8psMY5F5l/Pw6bxpkJjAkfGwPMiCtCkZ0oK4OTTrLa6NGjbW6+uNiOi+xKbF/7G26AceOys699vFU3/bHyymbACuBC7ORRDHQDVmPllRt29nt0MVYaqqrKpnD69rULayINUVVl1VuTJ2dWrX195+ibxPMi3vsFwI5e5Lh4fq9IfZWWwpo1tp2cSEM1agS33QZdusD48XDccdlTaw9qUywZ7rHHoEULGDEi6EgkG1xxhfW1f+cd62u/cmXQESWGEr1krC1b7I9y5Eho1SroaCRbnHkmvPwyfP659bV/552gI4qfEr1krBdegA0bbKWjSCIddRS88YYtqjr6aNs/OZMp0UvGKiqyrQ2zeWMJCc4hh2RPrb0SvWSkr76CmTPhrLNsA3ORZOjUyWrtjz46s2vtleglIz3zjG1armkbSbY2bax097zzMrfWPq7ySpGgFBXZR+pBg4KORHJBs2Y2ddO5s9Xar1+fObX2oBG9ZKBPP4XZs201ozYkkVSJ1Nrfcw/MmGG19l98EXRU9aNELxnniSdsJaOmbSQImVhrr0QvGaeoyHqIH3xw0JFIrorU2ldUZEatvRK9ZJQPP4Tycpu2EQlSzVr7F18MOqK6KdFLRikqsnn5s88OOhKR6rX2p54KU6cGHdGOKdFLxvDeEn1hoVU/iKSD2Fr7Cy5Iz1p7JXrJGHPnwvLluggr6admrf2vf51etfaqo5eMUVRk86Fnnhl0JCK11VVr36JF0JFpRC8ZYts2ePJJmwdt0yboaER2LLbWfubM9Km1V6KXjBBpG6tpG8kEkVr7+fPTo9ZeiV4yQlERtG0Lp5wSdCQi9ZNOtfZK9JL2KiutidmoUTZHL5Ip0qXWXole0t7MmZbsNW0jmSgdau2V6CXtFRXZps1DhwYdiUjDdOoEJSXRWvthw+CVV6o/JxSyap1kUKKXtPbFF/Zx95xzrKJBJFPttVe01v7FF23XqpdftsdCIRg9GgoKkvPa+tORtFZcbKWVmraRbBCptb/uOts4Z/hwuP56S/LFxbbqOxmU6CWtFRVBnz7Qr1/QkYgkRqNGMGmSfW3ZYrdjxyYvyYMSvaSxlSvhzTdtNK8NRiTbVFba7SWXwH332fRNsijRS9p6/HG7VUtiyTahENx+u21sf++9Nm0zenTykr0SvaSlSKfKo46C7t2DjkYkscrKrNyyoMCSfWGhJfuysuS8nhK9pKV334VFi3QRVrLT1VdbJ9Yf/zh6rLAQJkxIzusp0UtaKiqCJk1sNaxItnn/fau6iU30yaREL2ln+3abnx82DNq3DzoakcSbM8duleglZ73+Oqxbp2kbyV5z5sC++6bu+pMSvaSFyZOjFQdFRdCqlfWdT9aScJEgzZkDAwemrmw47kTvnGvsnJvvnPtP+H4P59wc59wy59yTzrlm8Ycp2a6gwMrLXnwRpk2ztq6/+EXyloSLBGXTJliyJHXTNpCYEf14YHHM/duAO733BwIbgYsT8BqS5SLlZaNHw+bNtj9sMpeEiwQlUkKZMYneOdcFGA5MCd93wLHAtPBTpgIj43kNyR2FhdC7t30/bpySvGSnyIXYVH5ajXdEfxcwAagK398H2OS93xa+vxboHOdrSI4IhWwXnrw8eOCB5C4JFwnKnDlw8MG2Y1qqNDjRO+dOBT733s9r4M9f6pwrd86VV1RUNDQMyRKhEPzsZ1ZaOWZM8peEiwTBe5uWTOW0DcQ3oh8MnO6cWwU8gU3Z3A20dc41CT+nC7BuRz/svX/Ae5/vvc/v0KFDHGFINigrg2uuse+HDEn+knCRIKxebZvcZ0yi995f773v4r3PA84GXvHenweEgMh6xjHAjLijlKw3YQJ8/TU0bgyDBtmxZC4JFwlCqhdKRSSjjv464DfOuWXYnP2DSXgNyUIlJTBgALRsGXQkIskxZw40bw4/+lFqX7fJrp+ya977V4FXw9+vAAYm4vdK7vjhB5u7HDcu6EhEkmfOHBvMNG2a2tfVylhJC+XlluyHDAk6EpHk2LrVqspSPW0DSvSSJkpK7Hbw4GDjEEmW995LbcfKWEr0khZKSqy2WAVYkq3mzrVbJXrJSVVV8MYbtpuUSLZKdcfKWEr0EriFC62/jebnJZvNmWOj+SA2uleil8BF5ueV6CVbBdGxMpYSvQSutBQ6dbIeNyLZKLLCe2BAhedK9BIo721EP2RIMB9pRVIhiI6VsZToJVCrV9u2gZq2kWwWRMfKWEr0EqjI/LwqbiRbBdWxMpYSvQSqpMT2hu3bN+hIRJIjqI6VsZToJVClpbYatnHjoCMRSY6gOlbGUqKXwHzxBSxerGkbyW5BdayMpUQvgSkttVtdiJVsNmcOHHFE6jtWxlKil8CUlsIeewRXciaSbJGOlUHVz0co0UtgSkosye+xR9CRiCRHkB0rYynRSyAqK22ko2kbyWbpcCEWlOglIHPmwLZtSvTZZPJkCIWqHwuF7Hiumjs3uI6VsZToJRAlJdby4Mgjg45EEqWgAEaPjib7UMju5/I1mCA7VsZKyJ6xIrurpAT69QtuSbgkXmEh3HknnHQSdOsG69fDDTfAoYcGHVkwIh0rzz8/6Eg0opcAbN0Kb7+taZtsM2sWXHmlLX5bvhy+/dYS/f77W+I/80yYNAlmz7b9B7JdpGNl0PPzoBG9BGDBArsYq4VS2cF7uOsuuOYaS+jOwbXXwr33wh/+ANu3W9IrK4Onn47+XK9eNq0zcKDd9u8Pe+4Z3L8j0YLuWBlLiV5STo3Mssf338Nll8HUqfb/c/FimDbNpnEKC22OvrgYrr7anr9hA5SXRxN/KARFRfZYkybW86igIPrVp0+wC43iEelY2aZN0JGA894HHQP5+fm+vLw86DAkRc44w0b1K1YEHYnEY/16+OlPLaH9z//YMv+BAy3BR4RCltAnTKj793zySTTxR742brTHmjeHww+PJv6BA+HAA6FRmk46n3IKHH+8ndj228/u9+sHL78Mzz2X+Ndzzs3z3ufv6nka0UtKeW8rYk8+OehIJB5z51qS37wZpk+3k/eOREb2O9OpE4wYYV9g75EVK+w1Iol/yhS45x57vE0byM+vPvLv0iX4yhawJH/NNfbJpaICvv7a7t9+e7BxKdFLSn34of0B6EJs5nr0Ubj0UkvQb72V+GZdzsEBB9jXOefYsW3bbFoodtT/17/ahX2w0XNs4i8ogPbtExtXffzmN3b729/a7TPPWJKPHA+Kpm4kpaZMgV/+0v5oDz446Ghkd2zbBtddB3fcYaP04uJgkmnE999bi4Gysujof8kS+0QAtgdx5EJvQQEMGACtW6cmttat4Ztv7ILz0qXJex1N3UhaKimBDh2gd++gI5HdsXEjnH02vPQSXH65JfugL5JGrgkMHAjjxtmxr76y1hqRUf/cuXZCAvukcMgh1Uf9hx2W+F5Ld9xhVWUtW9on2EmTYOLExL7G7lKil5QqLbXqjHSYT5X6WbwYTj/ddkr65z/hkkuCjqhue+0FxxxjXxEVFdUrfZ5/3qqEwE5W/fpVv9h7yCEN3wjnjjuic/IDBtgnn+uvh2bNgp2+0dSNpMwnn0Dnzja3GvScpdTPs8/CeedBixZWA/+TnwQdUfy8hzVrqs/3l5fbpwGwkfiAAdVH/j171m9wEqm6iby/f/pT+H//z65JzZ6d+H+Lpm4k7UTq53UhNv15D7feCr//vSW9Z56Brl2DjioxnLOFXZHVugBVVfDRR9WT/7332nUAgHbtalf6dOpU+3fXLKGcPNkSfc+eyf037YpG9JIyV1wBDz9sPUCaaIiRtior4aKLbG773HPtAno2rVitr61b4YMPqpd5LlxoK33BEn3sxd78fNh779q/Z8gQm7JcsMCuCUD91hfUR31H9Er0kjL9+1uVxssvBx2J1OXjj62e/d134bbbbL5Z11Oivv3WEnbsyP/DD6OPH3hg9VH/gAH2fh850t7/8+bBq69GVwzvao3BriR96sY51xV4FNgP8MAD3vu7nXPtgCeBPGAVMNp7v7GhryPZYdMmK4W76aagI5G6vP46jBoFW7bYdIMWtdXWooVdp4i9VrFpkyXwSOIvKYHHH7fHGjWyNg777gvz59snpJdfTkyS3x3xfIDeBvzWe/+Oc641MM85Nwu4AJjtvZ/knJsITASuiz9UyWRvvWXzvpqfT0/3329Taz17wsyZKn/dHW3bwnHH2VfEp59WH/V/8okdf+IJuPHG1CZ5iKNNsfd+vff+nfD3XwOLgc7ACCBcvMRUYGS8QUrmKymxefl0aNkqUVu2wNix9nXCCda3Rkk+fvvvD6edBjffbOWcxcV2QXfCBLjvvto7cSVbQloDOefygMOBOcB+3vv14Yc+xaZ2JMeVlNh8ZcuWQUciERUVltzvv99WvD77rDaCSYZQCM46y7p63nabJf3YnbhSIe5E75xrBUwHrvLefxX7mLcrvTu82uucu9Q5V+6cK6+oqIg3DElj339vlQuatkkfCxZYlcjcudYmeNKkhi8Skp0rK6s+Jx9pHxHZmCQV4ipyc841xZJ8kfc+sqXAZ865jt779c65jsDnO/pZ7/0DwANgVTfxxCHprbzcpgjUfz49PPUUXHCBTSWUlsIRRwQdUXbbUQllfbp6JlKDR/TOOQc8CCz23t8R89BMYEz4+zHAjIaHJ9mgtNRuleiDVVVlC6BGj7ZSv7IyJflcEc+IfjDwc+B959yC8LHfAZOAYufcxcBqYHR8IUqmKymx/iFBdjrMRZMETK4HAAAKg0lEQVQnWy13YaEt7z//fJuHLyiAV15JfDMvSV8NTvTe+1KgrqUUx9VxXHLM9u3wxhs2ipTUKiiw/+533mntDJYsgVatbD5eST63aCG6JNUHH9guRLoQm1pr18Ly5fZJ6uc/txYGrVtbz5pU13BL8JToJanUyCw1fvjBroW88IJ9LVxox7t0sT1X58+3dgZK8rlJiV6SqqTEWhN37x50JNln5UpbjPPCCzbnXllp/dWHDoUxY6yFwWefWQ33jTfaQp1UV3tIelCil6Tx3hL90KFqjJUI330Hr71mif3556PNtHr0sMQ+bJgl8Vat7HhkoU6khruwMHHNtCSzKNFL0qxaZT0+VFbZMN5bj/TIqP3VV23xWfPmtoPSuHGW3A86aMcn0p0t1FGizy1K9JI0mp/ffd98YyPxSHJfudKO9+4Nv/qVJfajj65ff/h0WKgj6UGJXpKmtBTatIG+fYOOJH15b5VJkemYkhLb8KJlS+uGeO21cNJJwe9QJJlNiV6SpqQEBg+2ntwStXmz7R8aGbWvXWvH+/aF8ePtIurgwap1l8RRopekqKiwBTpjxuz6udmuqsp2bIqM2t980xaS7bWXdY+86SabkunSJehIJVsp0UtSvPGG3ebq/PyGDfDSS9G69s8+s+OHH24tgYcNg0GDrBxSJNmU6CUpSkps6iF/l7tZZoft2207uch0zNy5NpJv1w5OPNGmY0480TakEEk1JXpJipISGDgwu+eZP/ssOmp/8UX48ksrcywosAVKw4bZ9+rzLkFTopeEq6yEd96xKYpssm2bbbUXGbXPm2fH990XTjnFRu0nnKAunZJ+lOgl4d5+26YysmGh1Lp1Nlp//nmYNcsqZho3hiOPhD/9yZJ7//6qLJL0pkQvCVdaalMYP/lJ0JHsvi1b7EJy5CLqe+/Z8U6dYNQom445/njtrSqZRYleEq6kBA47zBZLZYLVq6PTMbNn2+rUpk3tE8nkyZbc+/ZVvx7JXEr0klBbt8Jbb8FFFwUdSd2+/x5efz1a175kiR3v3t12YRo2DI491vq3i2QDJXpJqAUL4Ntv069+ftmy6Kg9FLJOkHvsYX1jIj1kevfWqF2ykxK9JFSkkVnQF2IrK63bYyS5L19uxw86CC65xC6iHn00tGgRaJgiKaFELwlVUmINuDp1Su3reg+LF0enY15/3S6stmhh0zBXX22j9gMOSG1cIulAiV4SxnuruBk+PDWv99VXtrNSZNT+8cd2/NBD4fLLbdR+1FHWv10klynRS8IsXQpffJG8+XnvrdwxMmp/4w1bxNS6tZU83nCDjdq7dUvO64tkKiV6SZhkzM9v3GgLlSJ17evX2/HDDrPNrocNs3p9NQcTqZsSvSRMaSl06AC9ejX8d1RVWfuEyHTM22/bsbZtqzcHS/U1AJFMpkQvCVNSYqP53S1RrKio3hysosKO5+dHp2MGDoQmereKNIj+dCQh1q2z/U2vuGLXz92+3dr4Rkbt5eU2/96+vW2bF2kOtu++yY9bJBco0UtClJbabV0XYtevr94cbONGawQ2aBD88Y+W3AcMUHMwkWRQope4TJ5sPddLSmxD6/79beXp22/bRdLIRdQFC+z5HTvCyJHR5mDt2gUbv0guUKKXuBQUwOjR1sCsVy/rQf/3v1sr3+++s3n1wYNh0iRL7v36qc2ASKop0UtcCgth6tToIqn5863y5qc/tcR+3HG2CbaIBEeJXuJ28sk2TfPmm3DZZXDvvRq1i6QTXfqSuL36Knz4oe2TOm2a3ReR9JGURO+cG+acW+qcW+acm5iM15D0EArZHH1xMdx8s92OHm3HRSQ9JDzRO+caA/8LnAwcCpzjnDs00a8j6aGszJJ7YaHdLyy0+2VlwcYlIlHJmKMfCCzz3q8AcM49AYwAFiXhtSRgEybUPlZYGE38IhK8ZEzddAbWxNxfGz4mIiIBCOxirHPuUudcuXOuvCLS3ERERBIuGYl+HdA15n6X8LFqvPcPeO/zvff5HTp0SEIYIiICyUn0ZcBBzrkezrlmwNnAzCS8joiI1EPCL8Z677c55y4HXgQaAw957z9I9OuIiEj9OO990DHgnKsAVgcdRz21B74IOogGUuzBUOzByNTYdyfu7t77Xc59p0WizyTOuXLvfX7QcTSEYg+GYg9GpsaejLjVAkFEJMsp0YuIZDkl+t33QNABxEGxB0OxByNTY0943JqjFxHJchrRi4hkOSX6nXDOdXXOhZxzi5xzHzjnxoePt3POzXLOfRS+3TvoWGtyzjV3zs11zr0bjv2P4eM9nHNzwi2knwwvaks7zrnGzrn5zrn/hO9nStyrnHPvO+cWOOfKw8fS/v0C4Jxr65yb5pxb4pxb7Jw7MhNid871Dv/3jnx95Zy7KhNiB3DOXR3+G13onHs8/Leb0Pe7Ev3ObQN+670/FBgEjAu3XJ4IzPbeHwTMDt9PNz8Ax3rvDwP6A8Occ4OA24A7vfcHAhuBiwOMcWfGA4tj7mdK3ACF3vv+MSVymfB+AbgbeMF7fzBwGPbfP+1j994vDf/37g8cAXwLPEMGxO6c6wxcCeR77/tii0zPJtHvd++9vur5BcwATgCWAh3DxzoCS4OObRdxtwDeAX6MLcRoEj5+JPBi0PHtIN4u2B/mscB/AJcJcYdjWwW0r3Es7d8vQBtgJeHrdpkUe414TwTeyJTYiXb7bYd1KvgPcFKi3+8a0deTcy4POByYA+znvV8ffuhTYL+Awtqp8PTHAuBzYBawHNjkvd8Wfkq6tpC+C5gAVIXv70NmxA3ggZecc/Occ5eGj2XC+6UHUAE8HJ4ym+Kca0lmxB7rbODx8PdpH7v3fh1wO/AxsB7YDMwjwe93Jfp6cM61AqYDV3nvv4p9zNspNy1Ll7z32719nO2CbQhzcMAh7ZJz7lTgc+/9vKBjaaCjvPcDsB3WxjnnhsY+mMbvlybAAOA+7/3hQCU1pjrSOHYAwvPYpwNP1XwsXWMPXzcYgZ1oOwEtgWGJfh0l+l1wzjXFknyR9/7p8OHPnHMdw493xEbMact7vwkIYR8B2zrnIs3sdthCOmCDgdOdc6uAJ7Dpm7tJ/7iB/47Q8N5/js0TDyQz3i9rgbXe+znh+9OwxJ8JsUecDLzjvf8sfD8TYj8eWOm9r/DebwWexv4GEvp+V6LfCeecAx4EFnvv74h5aCYwJvz9GGzuPq045zo459qGv98Tu7awGEv4o8JPS7vYvffXe++7eO/zsI/hr3jvzyPN4wZwzrV0zrWOfI/NFy8kA94v3vtPgTXOud7hQ8dh23+mfewxziE6bQOZEfvHwCDnXItwvon8d0/o+10LpnbCOXcUUAK8T3S++HfYPH0x0A3rujnae78hkCDr4JzrB0zFruI3Aoq99zc753piI+V2wHzgfO/9D8FFWjfn3DHANd77UzMh7nCMz4TvNgEe897f4pzbhzR/vwA45/oDU4BmwArgQsLvHdI/9pZY0uzpvd8cPpYp/93/CJyFVfnNBy7B5uQT9n5XohcRyXKauhERyXJK9CIiWU6JXkQkyynRi4hkOSV6EZEsp0QvIpLllOhFRLKcEr2ISJb7/zLYB3cbUEk1AAAAAElFTkSuQmCC\n",
	"text/plain": [
	"<Figure size 432x288 with 1 Axes>"
	]
	},
	"metadata": {
	"needs_background": "light"
	},
	"output_type": "display_data"
	}
	],
	"source": [
	"xcoords, ycoords = list(zip(*cities[tour].tolist(), cities[tour[0]].tolist()))\n",
	"matplotlib.pyplot.plot(xcoords, ycoords, 'xb-')\n",
	"matplotlib.pyplot.show() # graph the tour"
	]
	}
	],
	"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.7.0"
	}
	},
	"nbformat": 4,
	"nbformat_minor": 2
	}