Travelling Salesman .ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TSP using Dynamic Programming"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "import numpy as np\n",
    "np.random.seed(42)\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "def DP_TSP(distances_array):\n",
    "    n = len(distances_array)\n",
    "    all_points_set = set(range(n))\n",
    "\n",
    "    # memo keys: tuple(sorted_points_in_path, last_point_in_path)\n",
    "    # memo values: tuple(cost_thus_far, next_to_last_point_in_path)\n",
    "    memo = {(tuple([i]), i): tuple([0, None]) for i in range(n)}\n",
    "    queue = [(tuple([i]), i) for i in range(n)]\n",
    "\n",
    "    while queue:\n",
    "        prev_visited, prev_last_point = queue.pop(0)\n",
    "        prev_dist, _ = memo[(prev_visited, prev_last_point)]\n",
    "\n",
    "        to_visit = all_points_set.difference(set(prev_visited))\n",
    "        for new_last_point in to_visit:\n",
    "            new_visited = tuple(sorted(list(prev_visited) + [new_last_point]))\n",
    "            new_dist = prev_dist + distances_array[prev_last_point][new_last_point]\n",
    "\n",
    "            if (new_visited, new_last_point) not in memo:\n",
    "                memo[(new_visited, new_last_point)] = (new_dist, prev_last_point)\n",
    "                queue += [(new_visited, new_last_point)]\n",
    "            else:\n",
    "                if new_dist < memo[(new_visited, new_last_point)][0]:\n",
    "                    memo[(new_visited, new_last_point)] = (new_dist, prev_last_point)\n",
    "\n",
    "    optimal_path, optimal_cost = retrace_optimal_path(memo, n)\n",
    "\n",
    "    return optimal_path, optimal_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "def retrace_optimal_path(memo: dict, n: int) -> [[int], float]:\n",
    "    points_to_retrace = tuple(range(n))\n",
    "\n",
    "    full_path_memo = dict((k, v) for k, v in memo.items() if k[0] == points_to_retrace)\n",
    "    path_key = min(full_path_memo.keys(), key=lambda x: full_path_memo[x][0])\n",
    "\n",
    "    last_point = path_key[1]\n",
    "    optimal_cost, next_to_last_point = memo[path_key]\n",
    "\n",
    "    optimal_path = [last_point]\n",
    "    points_to_retrace = tuple(sorted(set(points_to_retrace).difference({last_point})))\n",
    "\n",
    "    while next_to_last_point is not None:\n",
    "        last_point = next_to_last_point\n",
    "        path_key = (points_to_retrace, last_point)\n",
    "        _, next_to_last_point = memo[path_key]\n",
    "\n",
    "        optimal_path = [last_point] + optimal_path\n",
    "        points_to_retrace = tuple(sorted(set(points_to_retrace).difference({last_point})))\n",
    "\n",
    "    return optimal_path, optimal_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_route(X, optimal_path):\n",
    "    for p1, p2 in zip(optimal_path[:-1], optimal_path[1:]):\n",
    "        plt.plot([X[p1, 0], X[p2,0]],[X[p1,1], X[p2,1]]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_random_input(n_points):\n",
    "    X = np.random.rand(n_points, 2)\n",
    "    distances_array = np.array([[np.linalg.norm(X[i]-X[j])\n",
    "                                for i in range(n_points)]\n",
    "                               for j in range(n_points)])\n",
    "    return X, distances_array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found optimal path in 0.341 seconds.\n",
      "Optimal cost: 2.484, optimal path: [5, 3, 0, 4, 1, 6, 10, 9, 8, 11, 7, 2]\n"
     ]
    }
   ],
   "source": [
    "input_size = 12\n",
    "X, distances_array = generate_random_input(input_size)\n",
    "\n",
    "t = time.time()\n",
    "optimal_path, optimal_cost = DP_TSP(distances_array)\n",
    "runtime = round(time.time() - t, 3)\n",
    "\n",
    "print(f\"Found optimal path in {runtime} seconds.\") \n",
    "print(f\"Optimal cost: {round(optimal_cost, 3)}, optimal path: {optimal_path}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAsgAAAFgCAYAAACmDI9oAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nOzdeXiU5b3/8fc9S5JJIHtCSCYQ1iQgssgiIIooYHtaS12q1qq1B3ftdqSW1tae2lNtaY/VumO19bTV1pZD7c8eQaEoiiK77ATZsrAkJCEkmZCZ5Pn9MaBoQRKYmWeWz+u6znWuPBlmPucgNx+e3M/3NpZlISIiIiIiQQ67A4iIiIiIRBMVZBERERGR46ggi4iIiIgcRwVZREREROQ4KsgiIiIiIsdRQRYREREROY7rVC8wxjwLfA44YFnWWSf4vgEeBj4LtAJftSxr9aneNzc31yopKel2YBGReLBq1ao6y7Lyuvp6rcUiIqF3srX4lAUZ+C3wKPD8Sb7/GWDQ0f8ZBzxx9H9/qpKSElauXNmFjxcRiT/GmN3d/CW/RWuxiEhInWwtPuUWC8uy3gTqP+UlXwCet4LeBTKNMb1PL6aIiJyI1mIRkcgJxR7kIqDyuK+rjl4TEZHI0VosIhIioSjI5gTXTnh+tTHmZmPMSmPMytra2hB8tIiIHKW1WEQkREJRkKuA4uO+9gI1J3qhZVlPW5Y12rKs0Xl5XX42RURETk1rsYhIiISiIL8MXG+CzgUOWZa1NwTvKyIiXae1WEQkRLoy5u0FYDKQa4ypAu4D3ACWZT0J/IPgWKHtBEcL3RiusCIiiUprsYhI5JyyIFuWdc0pvm8Bd4QskYiI/AutxSIikaOT9EREREREjqOCLCIiIiJyHBVkEREREZHjdOWo6agxf001cxZspabRR2Gmh1nTS5kxUnPwRURERCR0YuYO8vw11cyet57qRh8WUN3oY/a89cxfU213NBGRhNLRabF6T4PdMUREwiZmCvKcBVvx+Ts+ds3n72DOgq02JRIRSUy/f3c3lz2+jA9qm+2OIiISFjFTkGsafd26LiIi4fGZswpwGJi3usruKCIiYREzBbkw09Ot6yIiEh756SmcPziP/11dTWenZXccEZGQi5mCPGt6KR6382PXPG4ns6aX2pRIRCRxXT7KS82hNt7dcdDuKCIiIRczUyyOTavQFIvEpAkmItFl6pBe9Exx8ZfVVUwYmGt3HBGRkIqZggzBkqxSlHiOTTA59pDmsQkmgP57ELFJitvJ587uzd/W1nD/FwKkJcfUXyciIp8qZrZYSOLSBBOR6HT5KC+t7R28umGf3VEkEjo7aa9exRN//yq+xkq704iElf7JL1FPE0xEotM5fbPom5PKX1dXcfk5XrvjSKhZFtTvgB1LYOcbsHMpq60WnijIZ92Sb/LI518gyZlkd0qRsFBBlqhXmOmh+gRlWBNMROxljOGykV5+tWgb1Y0+ivRnMvY17YWdbwYL8Y43oOnoKL+ehTB4Ouf2u4D7TAs/Wvsw33nzO/zigl/gcqhKSPzRf9US9WZNL/3YHmTQBBORaHHZqCIeen0b89dUc8eFA+2OI93la4BdbwXL8M43oG5b8LonC0omwaRvQb/JkDMAjAHgcsDnTuFnK37GvW/fy39N/C+cDudJP0IkFqkgS9TTBBOR6FWcncrYftn8dVUVt08egDlaoiRKtbdC5bsfFeK968DqBHcq9BkPI78C/S6AgrPBcfLHlL4y5Cv4Aj4eWfMIKc4U7ht/n37vJa6oIEtM0AQTkeh1xSgv3/nr+6ypbGRUnyy748jxOvxQvfqjLRNV70FHOzhc4B0D538H+l8ARaPB1b39xDedfRO+gI+56+ficXn4zpjvqCRL3FBBFhGRM/KZYQX88OUNzFtdpYJst85OOLDpo0K8+21obwYMFAyDsTdD/8nBu8XJPc744+4aeRetgVZ+v/n3pLpTuWvkXWf8niLRQAVZRETOSM8UN9OHFvD3dXv5weeGkOzSftSIsSxo2PnRlomdS6G1Lvi97AFw9peCWyb6nQ+p2SH/eGMM94y5h7ZAG0+//zQel4eZw2aG/HNEIk0FWUREztjlo7z8bW0NizYf4LPDetsdJ74d3n900sQS2PEmHNoTvN6zNwy8OFiG+18AGZEZvWeM4Qfn/gBfwMfDqx/G4/Jwbfm1EflskXBRQRYRkTM2cWAuvdKTmbe6SgU51HyNwa0Sx+4S124JXk/JCE6amPj14F3i3EEfTpqINKfDyU/O+wltgTYefO9BUl2pfHHQF23JIhIKKsgiInLGnA7DjJFF/GbpTuqaj5DbI9nuSLHL74M97340j7hmTXDShMsDfcfD8GuCd4l7D4coGq/mdriZc8Ecvr7469y37D6Sncl8tv9n7Y4lclpUkEVEJCQuH+XlqTd28Le1Nfz7ef3sjhM7OgLBErxzSfAuceV70HEkOGmi6ByYdHdwy4R3DLii+x8eSc4kHrrwIW57/Ta+99b3SHGlMKXPFLtjiXSbCrKIiITE4F49GVaUwV9XVakgfxrLOjpp4s2PJk0caQp+r9cwGHtTcMtE3/GQ3NPerKfB4/Lw2EWPcdPCm7j7jbt5dMqjTCiaYHcskW5RQRYRkZC5fFQRP/r7JjbvbaK8d7rdcaJHw67jJk28CS21wevZ/eGsyz6aNJGWa2vMUElzp/HExU/w7wv+nW/88xs8cfETjC4YbXcskS5TQRYRkZC5dEQRP3llM/NWV/H9fxtidxz7NB/4aA/xjjegcXfweo9e0P/C4JaJfudDZh97c4ZRRnIGT019ihsX3Midi+9k7tS5DMsbZncskS5RQRYRkZDJTkviwrJ8/ndNDfdcUobLefLjiuNKW9PHJ00c2BS8npwB/SbB+DuCd4nzSm2bNGGHHE8Oc6fO5YZXb+DW12/l2enPUppdancskVNSQRYRkZC6fJSX1zbtZ+n2Oi4szbc7Tnj426By+Ud3iatXg9UBrhTocy4MuzJ4l7j3iKiaNGGHXmm9eGbaM3z11a9y82s389wlz9E/o7/dsUQ+lQqyiIiE1JSyfDJT3fx1VVX8FOTODqhZe9ykieUQaAPjPDpp4tvBLRPeseBOsTtt1PH29DJ32ly++upXuWnhTfzukt/h7RmZg0xETocKsoiIhFSSy8Glwwt5cUUlh3x+MjxuuyN1n2UFD+TYcfShul1vwZFDwe/lD4XRXzs6aWICpOhhxK7ol9GPudPmcuOrNzJz4Ux+e8lvKUgrsDuWyAmpIIuISMhdPsrL8+/s5h/r93LN2Bh5EK1xz8cnTTTvD17PKoGhM4JbJkrOhx55tsaMZYOzBvPU1KeYuXAmNy28iecueY5cT3xM7pD4ooIsIiIhd7Y3g4H5PfjrqqroLcgtdR+V4R1vQMPO4PW0/OB2if4XBO8SZ/W1N2ecOSv3LB6/6HFuee0WbnntFp6d/iwZyRl2xxL5GBVkEREJOWMMl40q4uevbmVXXQsluWl2R4Ijh2H3so/uEu/fELyenA4l58G4W4OlOK8soSZN2GFUr1E8POVh7lx0J7e+ditzp82lR1IPu2OJfEgFWUREwuKLI4uYs2Ar89ZU8+2pgyMfIHAkeGzzsbvE1augMwDOZOgzDqb8APpPDk6acOqvw0ibUDiB/57833zrn9/ijkV38OTUJ/G4PHbHEgFUkEVEJEx6Z3g4b2Au81ZX8c2LBuFwhPmubGcH7F330eEce96FgA+MAwpHwcRvBLdMFI/TpIkoMbl4Mg9MeoB7lt7DN//5TX495dckOZPsjiWigiwiIuFz2agivvWndby3q55z++eE9s0tC+q2fbRlYtdSaDs6aSKvHM65IViISyZCiva4RqtL+l2CL+Djh8t+yN1v3M0vJ/8StyMGJ59IXFFBFhGRsJk+tIC0pA3MW10VmoJ8qOrjkyYO7w1ez+wD5ZcGt0z0Ox96xMn85QTxxUFfpK2jjZ8u/ynfX/p9Hpj0AM4EP2BF7KWCLCIiYZOa5OKzw3rzj/X7+M9Lz8KT1M3S03IQdr35USmu3xG8npYXLML9zg/eJc7uF/rwElHXlF2DL+DjoVUPkeJK4UcTfoTDJMhR5RJ1VJBFRCSsLhvl5aVVVSzYuI8ZI4s+/cVHmmHPO7BjSbAQ71sfvJ7UM7hVYsxNwUkT+UM0aSIOfe2sr9Hqb+Wp95/C4/Lw3bHfxej3WWwQ9wV5/ppq5izYSk2jj8JMD7Oml556gRYRkZAZ1y+bokwPf11d9a/rb6AdqlZ89GBd9cqjkyaSgg/TTbk3eIe4cJQmTSSIO0bcgS/g4/lNz5PqTuUbo75hdyRJQHG92sxfU83seevx+TsAqG70MXte8G6ESrKISGQ4HIbLRxXx6D+3s6+xlYLWbcdNmngH/K3BSRO9R8CEu4KFuM+54NbIr0RkjOHu0XfjC/h4Zv0zeFwebj77ZrtjSYKJ64I8Z8HWD8vxMT5/B3MWbFVBFhGJoC+O6M3gpXeR+ehtEDg2aaIMRl4X3DLRdyJ4Mu0NKVHDGMO9595LW6CNX6/5NR6Xh+uGXGd3LEkgcV2Qaxp93bouIiLh0S8/nYaeLnalX0DZhM8HH67rWWB3LIliDuPgxxN/TFtHGz9f8XM8Lg9XDL7C7liSIOK6IBdmeqg+QRkuzNSP7UREIm3Ud/5hdwSJMS6Hi59N+hm+gI8fv/NjUlwpfK7/5+yOJQkgruenzJpeisf98ZFCHreTWdNLbUokIiIi3eF2unlo8kOMKRjDvW/dy6Ldi+yOJAkgrgvyjJFFPHDZMIoyPRigKNPDA5cN0/5jERGRGJLiSuHXU37NWblncfebd/NW9Vt2R5I4F9dbLCBYklWIRUREYluqO5XHL36cmQtm8s1/fpMnLn6CMQVj7I4lcSqu7yCLiIhI/EhPSuepqU/h7eHljkV3sK52nd2RJE6pIIuIiEjMyErJYu60ueR6crnt9dvYUr/F7kgSh1SQRUREJKbkpebxzLRnSHOncfPCm9nRuMPuSBJnVJBFREQk5hT2KOSZac/gdDiZuXAmlU2VdkeSOKKCLCIiIjGpb3pfnp76NP5OPzMXzmRfyz67I0mcUEEWERGRmDUoaxBPTn2SpvYmZi6cSZ2vzu5IEgdUkEVERCSmDc0ZyhMXP8GB1gPctPAmGtsa7Y4kMU4FWURERGLeiPwRPDLlEfY07eGW12/hcPthuyNJDFNBFhERkbhwbu9zeejCh9hWv407Ft1Bq7/V7kgSo1SQRUREJG6c7z2fB89/kHW16/jGP7/BkY4jdkeSGKSCLCIiInFlesl07p94P+/ufZf/WPIf+Dv9dkeSGKOCLCIiInHn0gGXcu+4e3mj6g1mL51NR2eH3ZEkhrjsDiAiIiISDleVXUVbRxu/WPkLUpwp/Hjij3EY3RuUU1NBFhERkbh1w9AbaPW38vi6x0lxpfD9cd/HGGN3LIlyXfpnlDHmEmPMVmPMdmPMd0/w/QxjzN+NMeuMMRuNMTeGPqqISOLSOixy+m4dfis3Dr2RP239Ew+tegjLsuyOJFHulHeQjTFO4DFgKlAFrDDGvGxZ1qbjXnYHsMmyrM8bY/KArcaYP1iW1R6W1CIiCUTrsMiZMcbwrXO+RWuglec2PofH7eG24bfZHUuiWFe2WIwFtluWtQPAGPMi8AXg+IXZAnqa4M8segD1QCDEWUVEEpXWYZEzZIzhe+O+hy/g4/G1j5PqSuWGoTfYHUuiVFcKchFQedzXVcC4T7zmUeBloAboCVxlWVZnSBKKiIjWYZEQcBgH/znhP2kLBB/c87g8fKn0S3bHkijUlT3IJ9rJ/snNO9OBtUAhMAJ41BiT/i9vZMzNxpiVxpiVtbW13Q4rIpKgQrYOg9ZiSWwuh4sHJz3IBd4LuP/d+3n5g5ftjiRRqCsFuQooPu5rL8E7FMe7EZhnBW0HdgJln3wjy7KetixrtGVZo/Py8k43s4hIognZOgxai0XcTje/nPxLxvUexw/e/gELdy20O5JEma4U5BXAIGNMP2NMEnA1wR/jHW8PcBGAMaYXUArsCGVQEZEEpnVYJMSSnck8cuEjDM8bzj1v3sObVW/aHUmiyCkLsmVZAeBOYAGwGfizZVkbjTG3GmNuPfqy+4EJxpj1wCLgHsuy6sIVWkQkkWgdFgmPVHcqj130GIOzB/Otf36L5XuX2x1JooSxaxbg6NGjrZUrV9ry2SIidjPGrLIsa7TdObQWi0BjWyM3LriR6uZqnp76NCPyR9gdSSLkZGuxzlsUERGRhJaZksncaXPJT83nttdvY9PBTaf+RRLXVJBFREQk4eV6cnlm2jOkJ6Vzy2u3sL1hu92RxEYqyCIiIiJAQVoBz0x7BrfDzU2v3cTupt12RxKbqCCLiIiIHFWcXszcaXPp6Oxg5sKZ1DR/cqKiJAIVZBEREZHjDMgcwFNTn6LF38JNC2+itlUH6iQaFWQRERGRTyjPKeeJi5+g1lfLTQtvoqGtwe5IEkEqyCIiIiInMDxvOI9d9BhVzVXc8totNLU32R1JIkQFWUREROQkxhSM4aHJD1HRWMHtr99Oq7/V7kgSASrIIiIiIp9ikncSc86fw4a6Ddy1+C7aAm12R5IwU0EWEREROYWL+17M/RPvZ8W+FXx7ybfxd/jtjiRhpIIsIiIi0gWfH/B5fjD+ByytXso9S+8h0BmwO5KEiQqyiIiISBddOfhKvjPmO7y2+zV++PYP6bQ67Y4kYeCyO4CIiIhILLluyHW0+lt5dO2jeFwe7j33XowxdseSEFJBFhEREemmm8++GV/Ax282/IYUVwp3j75bJTmOqCCLiIiIdJMxhm+M+ga+gI/nNz1PqjuVO0bcYXcsCREVZBEREZHTYIzhnrH34Av4eHLdk3hcHr521tfsjiUhoIIsIiIicpocxsF94++jLdDGQ6sewuPycE3ZNXbHkjOkgiwiIiJyBpwOJ/816b/wdfj46fKf4nF5mDFwht2x5AxozJuIiIjIGXI73Pzigl8wvvd47lt2H6/ufNXuSHIGVJBFREREQiDZmczDUx5mRN4IZi+dzZLKJXZHktOkgiwiIiISIh6Xh8cueoyy7DK+veTbvFPzjt2R5DSoIIuIiIiEUI+kHjw59UlKMkr4xj+/wer9q+2OJN2kgiwiIiISYhnJGTw99Wl6pfbi9kW3s7Fuo92RpBtUkEVERETCINeTy9xpc8lMzuSW129hW8M2uyNJF6kgi4iIiIRJQVoBc6fNJdmZzM0Lb2bXoV12R5IuUEEWSRDz11Qz8cHF9PvuK0x8cDHz11TbHUlEJCEU9yxm7rS5WFjMXDiT6matv9FOBVkkAcxfU83seeupbvRhAdWNPmbPW6+SLCISIf0z+vP01KfxBXzc9+x17K3aanck+RQqyCIJYM6Crfj8HR+75vN3MGeBFmgRkUgpzS7lycmPcv0f97H7S1fRtmWL3ZHkJFSQRRJATaOvW9dFRCQ8hvUeSfrP7yfT1ZNd13yZplcX2B1JTkAFWSQBFGZ6unVdRETCZ8T5lzPwr/NIKS2l+pvfpPaRR7A6O+2OJcdRQRZJALOml+JxOz92zeN2Mmt6qU2JREQSmysvjz7P/46Myy+j7vEnqPr61+lobrE7lhylgiySAGaMLOKBy4ZRlOnBAEWZHh64bBgzRhbZHU1EJGE5kpLo/ZOf0Ot736P5n0vYfc01tFdW2h1LAJfdAUQkMmaMLFIhFhGJMsYYsq+/juSBA6j61rfZdcWVFD38K9LOPdfuaAlNd5BFREREbJY2YQL9/vwnnHm57Pn3mdT//g9YlmV3rISlgiwiIiISBZL69qXkxRfpcf757P/JT9j3wx9itbfbHSshqSCLiIiIRAlnjx54H3uUnFtvofGlv7D7xq8ROHjQ7lgJRwVZREREJIoYh4P8b36Tov/+JW0bN7Lziitp27TJ7lgJRQVZREREJAqlf/az9P3D7wHY9eVrafrHP2xOlDhUkEVERESilGfoUPq99GdShgyh+tv/wYFf/UqHikSACrKIiIhIFHPl5tLnt8+ReeUVHHzyKaruvIuO5ma7Y8U1FWQRERGRKOdISqLgxz+m17330vzGG+y6+mra9+yxO1bcUkEWERERiQHGGLK/ci19fvMMHbV17LzyS7QsW2Z3rLikgiwiIiISQ9LOPZeSv7yEOz+PPTfdTP3z/6NDRUJMBVlEREQkxiQVF9P3hRfpMXky+3/6U/beey+dOlQkZFSQRURERGKQs0ca3l8/Qu7tt3Hor/PYc8NXCdTW2h0rLqggi4iIiMQo43CQ9/WvU/Srh2jbsoWdV34J34aNdseKeSrIIiIiIjEu/ZJLKPnjH8Bh2H3ttRz6f6/YHSmmqSCLiIiIxIGU8nL6vfQSKcPOoubuuznwy//G6uiwO1ZMUkEWERERiROunBz6PvssmV/6EgfnzqXq9jvoOHzY7lgxRwVZREREJI6YpCR6//g/KbjvhzS//Ta7rrqa9l277I4VU1SQRUREROJQ1jXX0Oc3v6Gjvp6dX7qK5rfetjtSzFBBFhEREYlTaePGBg8VKSig8uabOfjb3+pQkS5QQRYRERGJY0leLyUv/JGeF03hwIM/Y+/s79F55IjdsaKaCrKIiIhInHOkpVH08MPk3nknh+bPZ/f11+M/cMDuWFFLBVlEREQkARiHg7w776Do4Yc5sq2CXVdciW/9ertjRSUVZBEREZEEkj59GiUv/BHjcrH72q9w6O9/tztS1FFBFhEREUkwKWVllPzlJTzDh1Mz6zvsnzNHh4ocRwVZREREJAG5srPp8+xvyLzmaup/8yyVt91GR1OT3bGiggqyiIiISIIybje977uPgh/9iJZl77Drqqs5snOn3bFsp4IsIiIikuCyrr6Kvs89S0djI7u+dBXNS5faHclWKsgiIiIiQuqYMZS89BLuwkIqb7mVg795NmEPFVFBFhEREREAkrxFwUNFpk7lwJw51NxzT0IeKtKlgmyMucQYs9UYs90Y892TvGayMWatMWajMeaN0MYUEUlsWodFJFIcqakU/eohcr9+F00v/53d112Pf39iHSpyyoJsjHECjwGfAYYA1xhjhnziNZnA48CllmUNBa4MQ1YRSVDz11Qz8cHF9PvuK0x8cDHz11TbHSmitA6LSKQZY8i7/XaKfv0IR7ZvZ9cVV+Bbt87uWBHTlTvIY4HtlmXtsCyrHXgR+MInXvNlYJ5lWXsALMtKrH9miEjYzF9Tzex566lu9GEB1Y0+Zs9bn2glWeuwiNgifepUSl54AZOczO7rrqdx/ny7I0VEVwpyEVB53NdVR68dbzCQZYxZYoxZZYy5/kRvZIy52Riz0hizsra29vQSi0hCmbNgKz7/x4fX+/wdzFmw1aZEtgjZOgxai0Wke1JKB1Py0p/xjBzJa7/bxmv3/NHuSGHXlYJsTnDtk480uoBzgH8DpgM/MMYM/pdfZFlPW5Y12rKs0Xl5ed0OKyKJp6bR163rcSpk6zBoLRaR7nNlZdHnmbk4+vSnpi3H7jhh15WCXAUUH/e1F6g5wWtetSyrxbKsOuBNYHhoIopIIivM9HTrepzSOiwitjNuNwMvHUfzETdNdfF9k6IrBXkFMMgY088YkwRcDbz8idf8DZhkjHEZY1KBccDm0EYVkUQ0a3opHrfzY9c8biezppfalMgWWodFJCp4y7IAqNraYHOS8HKd6gWWZQWMMXcCCwAn8KxlWRuNMbce/f6TlmVtNsa8CrwPdALPWJa1IZzBRSQxzBgZ3Go7Z8FWahp9FGZ6mDW99MPriUDrsIhEi+zCNFLTk6jaXM+QiYV2xwkbY9cJKaNHj7ZWrlxpy2eLiNjNGLPKsqzRdufQWiwi3fXacxup3FTPjT87D+M40SMSseNka7FO0hMRERGRLisuy8Z32M/Bmma7o4SNCrKIiIiIdNmxfciVm+N3H7IKsoiIiIh0WY+sFLIKUqnaUm93lLBRQRYRERGRbvGWZVNT0UiHv9PuKGGhgiwiIiIi3eItyyLQ3sm+nYfsjhIWKsgiIiIi0i1FpVkYA5Wb43ObhQqyiIiIiHRLssdFfkk6VVvi80E9FWQRERER6bbi8mwO7GriSKvf7ighp4IsIiIiIt3mLcvCsqB6W6PdUUJOBVlEREREuq2gfwauJAdVcbgPWQVZRERERLrN6XJQOCiLyjjch6yCLCIiIiKnpbg8i8b9rRyub7M7SkipIIuIiIjIafGWZQPE3TQLFWQREREROS05hWl4errj7thpFWQREREROS3GYfCWZVO5pQHLsuyOEzIqyCIiIiJy2rxlWfia2qmvabE7SsioIIuIiIjIaSsuD+5Djqdjp1WQRUREROS09cxOISPfE1cP6rnsDiCxb/6aauYs2EpNo4/CTA+zppcyY2SR3bFEREQkQorLstmyfB8dgU6crti//xr7/xeIreavqWb2vPVUN/qwgOpGH7PnrWf+mmq7o4mIJJyOjg67I0iC8pZnETjSwf6dTXZHCQkVZDkjcxZsxef/+ILs83cwZ8FWmxKJiCSmZe/8nFcXTKCt7ZDdUSQBFQ3OwhiojJNxbyrIckZqGn3dui4iIuGRlNREUtJBVqx43+4okoBS0tzk9U2nanN87ENWQZYzUpjp6dZ1EREJj7Q0C8tK46233qKlJX7GbUnsKC7LYv+uJtp9AbujnDEVZDkjs6aX4nE7P3bN43Yya3qpTYlERBKT399AWmov2tvbWbJkid1xJAF5y7OxOi2qKxrtjnLGVJDljMwYWcQDlw2jKNODAYoyPTxw2TBNsRARiTC/v4EUTy6jR49m5cqV1NbW2h1JEkxB/3RcbgdVcTAPWWPe5IzNGFmkQiwiYrPgHeSBTJ48mffff5+FCxdy7bXX2h1LEojL7aT3oEwq42Aesu4gi4iIxIH29nrcSVmkpaUxadIkKioq2LFjh92xJMF4y7Jo2NtCS+MRu6OcERVkERGRGGdZnQQCjbjdWQCMGzeOjIwMFixYQGdnp83pJJEUlwWPna6K8XFvKsgiIiIxLhA4jGV1fFiQ3W43F198Mfv372fdunU2p5NEkuvtQUqam8oYH/emgiwiIhLj/N1YqG8AACAASURBVP7g3bokd/aH18466yyKiopYtGgR7e3tdkWTBGMcBm9ZFpVb6rEsy+44p00FWUREJMb5/cG7dcfuIAMYY5g+fTrNzc0sW7bMrmiSgLxlWbQeaqdhb6vdUU6bCrKIiEiMaz9BQQbo06cPQ4YM4e2336apqcmOaJKAisuDP8mI5WOnVZBFRERinL/9WEHO/pfvXXzxxXR2drJ48eJIx5IElZ7rIT03haoYHvemgiwiIhLjPtyDnJT1L9/Lzs5m7NixrF27lr1790Y6miSo4vJsqrc10NERm1NUVJBFRERinN/fgMORjMPhOeH3zz//fDweDwsXLozpB6ckdnjLsvG3dXBg12G7o5wWFWQREZEY1+5vwO3Owhhzwu97PB4mT57Mzp07qaioiHA6SUTe0iwwsTsPWQVZREQkxvn9DSfcf3y80aNHk5OTw8KFC+no6IhQMklUKT3c5BX3pHKzCrKIiIjYwO+vJ8n9r/uPj+d0Opk6dSp1dXWsWrUqQskkkRWXZ7F/RxPtbQG7o3SbCrKIiEiM8x/dYnEqpaWl9O3blyVLltDW1haBZJLIvGXZdHZa1FQ02h2l21SQRUREYlx7ewPuE0yw+KRjh4e0traydOnSCCSTRNZ7QAZOlyMmx72pIIuIiMSwzs4AgcChU+5BPqawsJDhw4fz7rvv0tAQe8VFYocryUnvgRkxuQ9ZBVlERCSGBQKNgNWlLRbHTJkyBWMMixYtCl8wEYLHTtfXtNBy6IjdUbpFBVlERCSGHTtm+lQP6R0vIyODCRMmsGHDBqqqqsIVTeTDY6djbZuFCrKIiEgM++iY6a4XZICJEyeSlpbGggULdHiIhE1ucU+SU10xNw9ZBVlERCSG+f3HCnLX9iAfk5yczJQpU6isrGTTpk3hiCaCw2HwlmZRtaUhpv4hpoIsIiISw/z+4J25rkyx+KSRI0eSn5/P66+/TiAQe7NqJTZ4y7NpbjhC4/5Wu6N0mQqyiIhIDPvwDrKr+wXZ4XAwbdo0GhoaeO+990IdTQQIHhgCsbUPWQVZREQkhrX7G3A603A6k0/r1w8cOJCBAwfy5ptv0toaO3f4JHak53romZMSU+PeVJBFRERimN9f3+0H9D5p2rRpHDlyhDfeeCNEqUQ+YoyhuCyL6m2NdHZ02h2nS1SQRUREYlhXj5n+NPn5+YwaNYoVK1ZQV1cXomQiH/GWZ9PuC3Bgz2G7o3SJCrKIiEgM87c3dGsG8slceOGFuFwuXn/99RCkEvk4b+nRfcibY2MfsgqyiIhIDGv3N3R7xNuJ9OjRg/POO48tW7awa9euMw8mchxPzyRyi3vEzDxkFWQREZEY5vc3nNaItxMZP3486enpLFiwgM7O2NgrKrHDW5bN3g8O4T/SYXeUU1JBFhERiVGdnUfo6Gg+4z3Ix7jdbi666CL27t3L+vXrQ/KeIscUl2XR2WFRs73R7iinpIIsIiISo/z+YNEIVUEGGDZsGIWFhSxatIj29vaQva9I74GZOFyGqhgY96aCLCIiEqPajx4SkhSCPcjHHDs8pKmpiXfffTdk7yviTnbSu38GlTFwYIgKsoiISIzytx89ZjqEd5ABSkpKKCsr46233uLw4dgYyyWxwVuWzcGqZlqbovunEyrIIiIiMerDY6ZDXJABpk6dSiAQ4J///GfI31sSV3F58Kcd1Vuj+y6yCrKIiEiM+rAgJ4Vui8UxOTk5jBkzhjVr1rB///6Qv78kpry+PUnyuKiM8nFvKsgiIiIx6tgeZLcrIyzvf8EFF5CcnMzChQvD8v6SeBwOg7c0i8rN9ViWZXeck1JBFhERiVF+fz0uVzoOhzss75+amsr555/PBx98wPbt28PyGZJ4vGVZNNcf4VCtz+4oJ9WlgmyMucQYs9UYs90Y891Ped0YY0yHMeaK0EUUERGtw3Iifn9DWPYfH2/s2LFkZWWxcOFCHR4iIXFsH3JVFE+zOGVBNsY4gceAzwBDgGuMMUNO8rqfAQtCHVJEJJFpHZaT8beH5pjpT+NyuZg6dSoHDhxgzZo1Yf0sSQwZ+R56ZCVH9TzkrtxBHgtstyxrh2VZ7cCLwBdO8Lq7gL8CB0KYT0REtA7LSfj9DSSF+Q4yQHl5OX369GHx4sUcOXIk7J8n8c0Yg7c8m6qtDXR2Ruc+5K4U5CKg8rivq45e+5Axpgj4IvBk6KKJiMhRWoflhNr99WHfYgHBQjNt2jRaWlp46623wv55Ev+Ky7I40hqgdk90ztnuSkE2J7j2ybr/K+Aey7I6PvWNjLnZGLPSGLOytra2qxlFRBJdyNZh0FocT/z+BtxJ4S/IAF6vl7POOot33nmHQ4cOReQzJX55y47tQ47ObRZdKchVQPFxX3uBmk+8ZjTwojFmF3AF8LgxZsYn38iyrKctyxptWdbovLy804wsIpJwQrYOg9bieNHR4aOzsy3se5CPd/HFF2NZFosWLYrYZ0p8Sk1PIqcojcrN0fmgXlcK8gpgkDGmnzEmCbgaePn4F1iW1c+yrBLLskqAvwC3W5Y1P+RpRUQSk9Zh+RfHDgmJxB7kYzIzMxk/fjzvv/8+1dXVEftciU/esmz2ftCIv/2UP/iKuFMWZMuyAsCdBJ+K3gz82bKsjcaYW40xt4Y7oIhIotM6LCfS7g/+aDoSe5CPd95555GamsrChQuj+qAHiX7esiw6Axb7tkfflh1XV15kWdY/gH984toJHwSxLOurZx5LRESOp3VYPsnffvQUvQgX5JSUFC688EJeeeUVtmzZQnl5eUQ/X+JH4aBMHE5D5ZZ6iodEbqtQV+gkPRERkRh0bItFJPcgHzNq1Chyc3N57bXXCAQCEf98iQ9JKS4K+mdE5YEhKsgiIiIxyH90i0VShKZYHM/pdDJt2jTq6+tZuXJlxD9f4oe3LIvaysP4mtvtjvIxKsgiIiIxqN3fADhwudJt+fxBgwbRv39/3njjDXw+ny0ZJPYVl2eDBdVbG+2O8jEqyCIiIjHI72/A7c4keMJ45B07PMTn8/Hmm2/akkFiX37fnrhTnFRG2TzkLj2kJ3LM/DXVzFmwlZpGH4WZHmZNL2XGyKJT/0IREQmpYEGO/PaK4xUUFDBy5EiWL1/OmDFjyM6OrgetJPo5nA6KBmdRtTm6CrLuIEuXzV9Tzex566lu9GEB1Y0+Zs9bz/w1moUpIhJpm3xufM5Cu2Nw4YUX4nQ6ef311+2OIjGquDyLpro2DtVGz1YdFWTpsjkLtuLzf3yYt8/fwZwFW21KJCKSmFoCHdzfcik/a7vS7iikp6czceJENm3axJ49e+yOIzEoGo+dVkGWLqtpPPG/7E52XUREwuOXu/ZTZ2Xy3QFeu6MAMGHCBHr27MmCBQt0eIh0W1ZBKmkZSVF17LQKsnRZYaanW9dFRCT0Njf7eKrqANf2zubCwuF2xwEgKSmJKVOmUF1dzYYNG+yOIzHGGIO3PJuqrfVYndHxDywVZOmyWdNL8bg//rS0x+1k1vRSmxKJiCSWTsviO1uryHA5+f4A+/cfH2/48OEUFBTw+uuv4/f77Y4jMaa4LIsjLQHqqprtjgKoIEs3zBhZxAOXDaMo04MBijI9PHDZME2xEBGJkBf21rOiqYX7BhSR7Y6uQVQOh4Np06Zx6NAhli9fbncciTHH9iFXRsk0i+j60yVRb8bIIhViEREb1LUHuP+DGsZnpvGlAnvHu51M//79GTx4MEuXLmXkyJGkpaXZHUliRFpmMtmFaVRtqWfU9L52x9EdZBERkVjw4w+qaeno5GeDizHG2B3npKZOnUp7eztLliyxO4rEGG9ZFjXbDxH4xMQsO6ggi4iIRLm3Gw7z530N3N4nn8FpKXbH+VR5eXmMHj2alStXUltba3cciSHFZdl0+DvZ98Ehu6OoIIuIiESz9s5Ovrutij4pSXyjby+743TJ5MmTSUpKYuHChXZHkRhSODgT4zBUbrF/3JsKsoiISBR7Yk8tFa1H+OlgL6nO2PhrOy0tjUmTJlFRUcGOHTvsjiMxIinFRUG/9Kg4djo2/qSJiIgkoN2+Izy0ex//lpfBxTnpdsfplnHjxpGRkcGCBQvo7Oy0O47ECG9ZFgf2HKatxd5RgSrIIiIiUciyLGZvq8JpDPcPjL3pQW63m6lTp7J//37WrVtndxyJEd7ybLCgepu92yxUkEVERKLQK7WHWFx/mHv6FVCYkmR3nNMydOhQvF4vixYtor293e44EgN69UvHney0/dhpFWQREZEo0xzo4N6Kas7q4eFrRXl2xzltxhimTZtGc3Mzb7/9tt1xJAY4nQ4KB2favg9ZBVlERCTK/HznPva3+/n5YC8uR/TOPO6KPn36MGTIEJYtW0ZTU5PdcSQGFJdlc6jWR1Odz7YMKsgiIiJRZP3hVp6pquX6whxGZcTHSXQXX3wxnZ2dLF682O4oEgO8ZcGTIqu22rfNQgVZREQkSnRYFrO2VpHtdvG9/r3tjhMy2dnZjBs3jrVr17J3716740iUyy5MIzU9ydZtFirIIiIiUeJ/ag6y9nArPx5URIbbZXeckJo0aRIej4eFCxdiWZbdcSSKGWPwlmdRtbUBq9Oe/1ZUkEVERKLAgSN+frqjhklZPfhifqbdcULO4/EwefJkdu7cSUVFhd1xJMoVl2XjO+znYE2zLZ+vgiwiIhIFfvRBDW0dFg8O9mJMbD+YdzKjR48mJyeHhQsX0tHRYXcciWLH9iHbNe5NBVlERMRmS+sPM29/A3f2zWdAaordccLG6XQydepU6urqWLVqld1xJIr1yEohqyCVqi327ENWQRYREbFRW0cn92yrosSTxNf79LI7TtiVlpZSUlLCkiVLaGtrszuORDFvWTY1FY10+CN/VLkKsoiIiI0e23OAHb4jPDjYS4oz/v9aPnZ4SGtrK0uXLrU7jkQxb1kWgfZO9u08FPHPjv8/iSIiIlFqR+sRHtmznxn5mUzOTrc7TsQUFhYyfPhw3n33XRoa7D1SWKJXUWkWxkDVlsj/N6KCLAlr/ppqJj64mH7ffYWJDy5m/ppquyOJSAKxLIvZ26pIMob/HFhkd5yImzJlCsYYFi1aZHcUiVLJHhf5JelU2jAPWQVZEtL8NdXMnree6kYfFlDd6GP2vPUqySISMX870MgbDYeZ3b83vZLddseJuIyMDCZMmMCGDRuo3FNpdxyJUsXl2RzY1cSRVn9EP1cFWRLSnAVb8fk/PmLI5+9gzoKtNiUSkURyyB/gh9urGd7Tww1FuXbHsc3EiRNJS/Lwyu//l0Bzu91xJAp5y7KwLKje1hjRz1VBloRU0+jr1nURkVB6cOc+6toD/Ly0GGeczjzuiuTkZCaVn0umz8Pex1fj399idySJMgX9MnAlOSJ+7LQKsiSkwkxPt66LiITKmqZWfltdx9e8uQzvmWp3HNud+8UL+OLMq3C2w4HH1+Gzae6tRCen20HhoEwqI/ygngqyJKRZ00vxuJ0fu+ZxO5k1vdSmRCKSCDosi3u2VpKf5OKefr3tjhM1kvumk3/nSFw5KRz83UYOv1GFZVl2x5IoUVyeTeP+Vg7XR25utgqyJKQZI4t44LJhFGV6MEBRpocHLhvGjJGJ9yS5iETOc9V1vN/s48eDiujpcp76FyQQV2YyebcOx3NWLof+bycNf96GZcMBERJ9vGXZQGTHvbki9kkiUWbGyCIVYhGJmH1H/Dy4Yy8XZvfk0rxMu+NEJUeSk+wvl3F4cSVNr+0mUOcj57ohONOT7I4mNsopTMPT003VlnrKJ0TmJy+6gywiIhIBP9xejd+yeGCwF5PAD+adijGG9Iv6kH1tOf59LRx4dA3tVYftjiU2Mg6Dtyybyi0NEdt6o4IsIiISZosPNvHygUa+2bcXJZ5ku+PEhNRhueTdNhwchtqn3qd1Xa3dkcRG3rIsfE3t1NdEZtKJCrKIiEgY+To6mb2tioGpydzeJ9/uODElqbAH+XeOwF3Yg/oXtnBo4S6sTj28l4iKyyO7D1kFWUREJIwe2b2f3W3tPDjYS7JDf+12l7NHEnk3DSN1dC8OL67k4B8203mk49S/UOJKz+wUMvI9VEZoDKD+pIqIiIRJRUsbj+45wBW9sjgvq6fdcWKWcTnIunwQGZ/rT9umg9Q+sY5AQ+RGfkl0KC7LpnpbIx2B8E83UUEWEREJA8uyuGdbFalOB/cNLLQ7TswzxtDzvCJybzyLQGMbBx5dy5Fdh+yOJRHkLc8icKSD/Tubwv5ZKsgiIiJh8Jf9DSxrbOb7/XuTl+S2O07cSBmcRf4dI3B4XNTOXU/Lin12R5IIKRqcBYaIbLNQQRYREQmxRn+AH22v4Zz0VL5SmGN3nLjjzksl//bhJPfPoOGvFTT+/QOsDj28F+9S0tzk9+lJ1ebwP6ingiwiIhJiP92xl8ZAgJ+XFuPQzOOwcKS6yf3qWfSYWEjz2zXU/XYDna1+u2NJmHnLs9m/q4l2XyCsn6OCLCIiEkIrD7XwfM1BZnrzGNrDY3ecuGachszPDyDr8kEc2XGIA4+vw1/bancsCaPi8mysTovqisawfo4KsoiISIgEOi2+s7WSwmQ3s0oK7I6TMNLGFJB30zA6fQEOPLaWtm2RmZUrkVfQPx2X20HV5vDuQ1ZBFhERCZFnqmrZ1NLGTwYV0cPltDtOQkkuySD/zhG4MlOoe24Dh5dWR+xYYokcl9tJ70GZVIb5wBAVZBERkRCobmvn57v2MTUnnc/kZtgdJyG5slLIu204KUNyOPTKDhr+UoEVgZm5Elnesiwa9rbQ0ngkbJ+hgiwiIhICP6gI3rH8r0FFGD2YZxtHspOca8vpOaWY1lX7qZ27no7mdrtjSQgVlx07djp82yxUkEVERM7QwrpD/KPuEN8uKaCPJ9nuOAnPOAwZ00rI/nIZ/ppmDjy6lvaaZrtjSYjkenuQkuYO6zYLFWQREZEz0NLRwfcqqihNS+HW4ny748hxUs/OI++Ws8GyqH1iHb4NdXZHkhAwDoO3LIuqzfVh22eugiwiInIGHtq1n6o2Pz8b7MXt0NaKaJPk7Un+nSNx907j4O830/T6bj28Fwe8ZVm0HGqnYW94xvqpIIuIiJymLS0+nqw8wNUF2Zyb2cPuOHISzp5J5N10Nqmj8ml6fQ/1f9xCZ3uH3bHkDBSXB/chh+vYaRVkERGR09BpWdyztYqeTic/GFBodxw5BeN2kHXlYDI+2w/fhjpqn1xHIIxTECS80nM9pOemUBWmfcgqyCIiIqfhT/vqWX6ohR8MLCQnyWV3HOkCYww9z/eSc8NQAgfbOPDoGo7sbrI7lpwmb3k21dsa6OgI/Sg/FWQRkW6av6aaiQ8upt93X2Hig4uZv6ba7kgSYQfbA9z/QQ3jMtK4uiDb7jjSTZ6ybPJvH45JdlL79Pu0rNpvdyQ5DcVl2fjbOjiw63DI31sFWUSkG+avqWb2vPVUN/qwgOpGH7PnrVdJTjA/2VFDU6CDBwd7cWjmcUxy90oj//YRJJek0/DSNhpf2YHVqYf3Yom3NAsLPxUrtoX8vVWQRUS6Yc6Crfj8H3+4x+fvYM6CrTYlkkh7t7GZF/bWc2txPuU9PHbHkTPgTHOT+7WzSBvfm+al1Rz83UY62wJ2x5JTaPe1suXtN3jt6V/QfuhJ3n/tuZB/Rpc2TRljLgEeBpzAM5ZlPfiJ718L3HP0y2bgNsuy1oUyqIhINKhp9HXreqhoHY4O7Z2d3LOtCm+Km2+V9LI7joSAcTrI+sJA3AVpNP7tAw48tpacG4biztU/fqKJr/kwH6xcTsXyt9m9fi0dfj+pGZmUjDiPPkPHhvzzTlmQjTFO4DFgKlAFrDDGvGxZ1qbjXrYTuMCyrAZjzGeAp4FxIU8rImKzwkwP1Scow4WZ4fvLVOtw9HiqspatLW08P6wfaU6n3XEkhHqM640r10P9HzYHS/K1ZaQMzLI7VkJraWxg+4p32LZ8GZUb38fq7KRnbh7Dp36WQeMmUDi4DIcjPH8Ou3IHeSyw3bKsHQDGmBeBLwAfLsyWZS077vXvAt5QhhQRiRazppcye976j22z8LidzJpeGs6P1TocBfb4jvDfu/bxmdwMpuVm2B1HwiBlQCb5d4yg7vlN1D27gczPDSBtfG+M9plHTFPtASree4eK996meutmsCyyehcx5tLLGTR2Ar36D4zI70dXCnIRUHnc11V8+l2Jfwf+70xCiYhEqxkji4DgXuSaRh+FmR5mTS/98HqYaB22mWVZfL+iGmMM9w8K6++12MyV4yH/9uHUv7iVxpc/wL+vhcxLB2BcemwrXOprqql4bxkVy5exf0cFAHl9SphwxZcZNHY8OcV9I/6PlK4U5BMlOuFjnsaYCwkuzOed5Ps3AzcD9OnTp4sRRUSiy4yRReEuxJ8UsnX46Gu0FnfTq3WHeO1gE/cNKMSbkmR3HAkzR7KLnOuG0LRwN4eXVOKv9ZHzlXKcaW67o8UFy7Ko27Prw1JcV7kbgIKBg5n05a8yaNwEsgrsPXynKwW5Cig+7msvUPPJFxljzgaeAT5jWdbBE72RZVlPE9wXx+jRozVLRUSka0K2DoPW4u5qCXTw/YpqhqSlMNObZ3cciRDjMGRcUoK7IJX6v2zjwKNryL1hKO6CNLujxSTLstj3wbbg9onlb9O4by8Yg7dsKBd+9WYGjhlPem70/PnqSkFeAQwyxvQDqoGrgS8f/wJjTB9gHnCdZVmhH0YnIpLYtA7baM6ufdQc8fP00BLcDu1FTTSpI/Jx5Xioe34TBx5fR/ZVpXiG5tgdKyZ0dnZQs2Vz8E7xe+9w+GAtDqeT4qFnM+bzlzNg9DjSMqPzQchTFmTLsgLGmDuBBQTHCz1rWdZGY8ytR7//JPBDIAd4/OgekYBlWaPDFzu+zV9THen9jSISxbQO22djs4+5VbVcV5jD6AzdOUxUScU96XVX8OG9g7/fRPq0EnpO9urhvRPoCASo3Pg+FcuXsX3lu7QeasTpdlMyfBQTr/oK/c8Zi6dHT7tjnpKxLHt+ujZ69Ghr5cqVtnx2NDt2Stcnn5B/4LJhKskiccQYsyoaCqzW4pPrtCw+8+4Wqjo6eGtcGVnuLh0dIHHM8ndQ/5cKfOtq8QzPI/uKQRi3xv0F2tvZ9f4aKpa/zQerlnOkpQV3cgr9Ro1h8LgJ9BtxDkmeVLtjntDJ1mL9aY8yn3ZKlwqyiEjk3Pb/1rNlRTXf/8oIlWMBwLidZF9dyuGCNJoW7uLAQR+51w3BmZFsd7SIa2/zsXPNSrYtX8bONSvxt/lITktjwDnjGDRuIn3PHoE7KXb//6I/8VHGrlO6RETkI79btosFb1dS0i+Trw3QiXnyEWMM6RcW4+6VSv2LW9n/6Fpyrx9CUnH0bxs4U23NzXywajkV7y1j17rVH55mVz7xAgaNm0Dx0GE4XfEx6UMFOcrYcUqXiIh85MX39nDfyxuZNqQXj107CpdT82/lX3mG5JB/+3DqfreRA0+tI/uKwaSOyLc7Vsi1NDbwwcrlbFv+NpUb36ezo4MeObmcffElDB47kcKy8rCdZmcnFeQoY9MpXSIiwtHnQP53PRcMzuPXXx6JW+VYPoW7II38O0dy8PebqX9xK/59LaRPK8HE+LSTprpatq94h4rly6jesgnL6iSzV2/O+bcZDBo3gYIBg+P+AUUV5Chj0yldIiIJ7//W7+U/XlrHuf1yeOq6c0h2xd9dMQk9Z5qbvH8/i8a/f8DhJVX497eSfXUpjuTYqlgN+2qoWL6MiveWsW97cFJkjrcP4y67isHjJpDbpyTuS/HxYut3L0HYcEqXiEhCW7xlP3e9sIYRxZk8c8NoUjSZQLrBuBxkzhiIuyCNxr9/wIHH15F7/RBcOdG7PdKyLA5W7v7w4I7aPbsA6NV/IOddfT2Dxk0gu9Brb0gbqSCLiEhCe6uijlt/v5ohhek8d+MY0mLszp9EB2MMPcYX4srzcPAPWzjw2Fqyry0nZUCm3dE+ZFkW+3ds//CI54a91WAMRaXlTL5+JoPGTiA9L/72UZ8OrQIRpANARESiy/IdB5n5/Ar656bx/NfGkp4SH0/gi31SBmbR644R1P1uI3W/2UDmFwbQY1xv2/JYnZ1Ub9vM9qOn2TXVHsA4HBQPPZtRn/0CA8ecS4+sbNvyRSsV5Aj55AEg1Y0+Zs9bD6CSLCJigzV7Gvjab1dQlOnh9zPHkZmaZHckiROuXA/5d4yg/oUtNP7vdvz7Wsj8XH9MhB767AgEqNq0gYr3lrF9xTu0NDbgdLnoe/ZIxl9+DQNGj8PTMz0iWWKVCnKE6AAQEZHosaH6EDc8+x65PZP5403nktsjdg80kOjkSHGRc8NQDr26k+Y3qwkcaCXn2nIcqeH5KUXA72f3+2uoeG8ZH6xcTlvzYVzJyfQfMZqB4ybQf+QYklOj8zS7aKSCHCE6AEREJDpYlsUP/7aBnilu/jBzHL3SU+yOJHHKOAyZn+2Pu1caDfMq2P9Y8FARd6+0kLy/v62NnWtXUvHeO+xY/R7tPh/JqWn0P2csg8aOp2T4KNzJ+u/7dKggR4gOABERiQ7GGJ74yjm0+TvwZumOmoRf2jm9cOV6OPg/mzjw+DqyrynDU3Z6+37bWprZsXoFFcvfZtfa1QT87Xh6plM6fhKDxk6gz7DhcXOanZ1UkCNEB4CIiEQP3TWWSEvumx48VOR/NnHwdxvJuKQfPc4v6tJs4damQ2xf8S4V7y1jz/p1dHYE6JGVzVlTpjFo7AS85UNxODWaMJRUkCNEB4BItNFUFRGRyHJlJpN3y9k0/GUbh/5vJ/59LWRdNgjj/teH9w7X17H9veBpdlWbN2JZnWTk92LUZy9l0Njx9B5YinHopMdwUUGOIB0AItFCU1VEROzhSHKSfU0Zh3tV0vTabgIHfeR8ZQjO9CQa9+87OqP4bfZWbAUgu6iYbnSUuAAABrhJREFUcV+8koFjJ5Bf0j+hTrOzkwqySALSVBUREfsYY0i/qA/uXqkc/NNWKucsY037YnbsWg3A/2/v3mLtKMsADL+f0mo5ttCWkh48lCoKQYKlwXoIHhKghNTGJuCJBL3RRKMXENALQkK88I4Yo4QQQryRG8VEBcRIFASqVlNKUTQVBasXiDWSolFKPy9mdjrd6R5nsfbMP3G9T7KSvbon2W/+tfL1X2vPrL369Rt551UfZ9OWrZyxbn3h2tnkBlmaQX6qiiSVt+y8laxasZRnbv0pq5esZ/3HLuDsLVtZfuaa0mkzzw2yNIP8VBVJGofXrD2VDV94N5uWn0y8ytMnxsKzu6UZdP2lb2bZkmOvePZTVSSpjNeefoqb45HxHWRpBvmpKpIkLcwNsjSj/FQVSZKOz1MsJEmSpAY3yJIkSVKDG2RJkiSpwQ2yJEmS1OAGWZIkSWpwgyxJkiQ1uEGWJEmSGtwgS5IkSQ1ukCVJkqQGN8iSJElSQ2RmmR8c8VfgmQW+vRJ4fsCc/8Wedva0s6fdrPa8LjNXDfBzWjmLp2JPO3vajalnTC0wbM9xZ3GxDXKbiNidmZtLd8yxp5097expZ894jW0t7GlnTzt7FjamFhhHj6dYSJIkSQ1ukCVJkqSGsW6Qby8dMI897expZ087e8ZrbGthTzt72tmzsDG1wAh6RnkOsiRJklTKWN9BliRJkoooukGOiMsi4rcRsT8ibjzO9yMivlJ/f29EXFi455yIeCwi/h0R1/XZ0rHno/W67I2IRyPibYV7ttcteyJid0S8q2RP47iLIuLliNhZsiciLomIf9TrsycibirZ02jaExFPRsRPSrVExPWNddlXP16nF+w5LSK+GxGP12tzbV8tY+AsnqrFOewcfsU9jabe53CXHmdxQ2YWuQGvBn4PvBFYCjwOvHXeMduA+4AALgZ+VrhnNXAR8CXguhGsz1ZgRf315SNYn5M5etrO+cBTJXsaxz0I3AvsLLw+lwDf6/N5M2HPcuDXwIb6/uqSj1Xj+CuBBwuvzReBL9dfrwIOAkuHeOyGvjmLp25xDjuHp+kZZA5P8ng1jp/pWVzyHeQtwP7MfDoz/wPcDWyfd8x24BtZ2QUsj4izSvVk5nOZ+QvgpZ4aJu15NDP/Xt/dBawr3HMo62cxcBLQ5wnuXZ4/AJ8FvgU812PLJD1D6dLzEeDbmfksVM/vgi1NHwa+2VNL154ETomIoNpwHAQO99hUkrN4uhbnsHN4mp6h5nDXnqaZnsUlN8hrgT817h+o/23SY4bsGdKkPZ+keoenaE9E7IiIp4DvA58o2RMRa4EdwG09dnTuqb2j/lXRfRFxbuGeNwErIuLHEfHLiLimYAsAEXEicBnVf6Z96dLzVeAtwF+AJ4DPZeaRHptKchYvXotz2Dk8ac9Qc7hrD+AsBjhhiB+ygDjOv81/pdvlmMUy5M/qonNPRLyXajD3ea5Zp57MvAe4JyLeA9wCfKBgz63ADZn5cvXis1dden5F9SctD0XENuA7wKaCPScAbwfeDywDHouIXZn5uwItc64EHsnMg4vcMGnPpcAe4H3ARuCHEfFwZr7QY1cpzuKFOYen73EOt/cMNYe79syZ+Vlc8h3kA8D6xv11VK8QJj1myJ4hdeqJiPOBO4Dtmfm30j1zMvMhYGNErCzYsxm4OyL+COwEvhYRHyzVk5kvZOah+ut7gSWF1+cAcH9mvpiZzwMPAX1cYDTJc+dq+v2VXteea6l+7ZmZuR/4A3BOz12lOIunbHEOt/Y4h1t6GG4Od+2Z4yzu+yTnhW5Ur5qeBt7A0ZOzz513zBUce2HIz0v2NI69mf4v0uuyPhuA/cDWkTxeZ3P04pALgT/P3S/5eNXH30W/F4d0WZ81jfXZAjxbcn2ofm31o/rYE4F9wHmlHivgNKrzy04awXP568DN9ddn1s/llX12lbo5i6deG+ewc3iankHm8CSPl7O4uhU7xSIzD0fEZ4AfUF3JeGdmPhkRn6q/fxvVFa/bqIbPP6leSRTriYg1wG7gVOBIRHye6orLRX+rv+P63AScQfWKHOBwZm5e7JYJej4EXBMRLwH/Aq7K+lldqGcwHXt2Ap+OiMNU63N1yfXJzN9ExP3AXuAIcEdm7ivRUh+6A3ggM19c7IZX0HMLcFdEPEG1Kbwhq3d3/u84i6drwTnsHJ6iZ6g53LWnPtRZjH9JT5IkSTqGf0lPkiRJanCDLEmSJDW4QZYkSZIa3CBLkiRJDW6QJUmSpAY3yJIkSVKDG2RJkiSpwQ2yJEmS1PBfAqr3SxXcX5cAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 720x360 with 2 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.figure(figsize=(10, 5));\n",
    "\n",
    "plt.subplot(1, 2, 1);\n",
    "plt.scatter(X[:, 0], X[:, 1]);\n",
    "\n",
    "plt.subplot(1, 2, 2);\n",
    "plot_route(X, optimal_path)\n",
    "\n",
    "plt.tight_layout();"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}