4.Optimizing Package Delivery.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Optimizing the Delivery of Packages\n",
    "This last jupyter notebook aims at finding the shortest paths between destinations of the devlivery drones. We want to minimize the time of flight of the drones, which is important becuase of the limited autonomy of the drones and their slow charging.\n",
    "\n",
    "If a drone begins at, for example, site 1, it is required to deliver packages to other destinations, and then return to the starting site 1. Each destination site needs to be visited exactly once and none can be skipped. The objective is to find the sequence of sites which being and end at site 1 such that the journey is minimized. This is essentially the **travelling salesman problem**, a well known NP-complete problem.\n",
    "\n",
    "## Preliminary Work\n",
    "The function `generate_map()` randomly places `N` sites on a 2D map of size $L_x\\times L_y$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import tkinter as tk\n",
    "import sys\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import time\n",
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(831, 75), (566, 103), (144, 307), (483, 179), (486, 269), (106, 453), (459, 384), (203, 389)]\n"
     ]
    }
   ],
   "source": [
    "def generate_map(Lx,Ly,N):\n",
    "    L=[]\n",
    "    while N>0:\n",
    "        T=[(random.randint(0,Lx),random.randint(0,Ly))]\n",
    "        if not T in L:\n",
    "            L+=T\n",
    "            N-=1\n",
    "    return(L)\n",
    "\n",
    "sites = generate_map(840, 480, 8)\n",
    "print(sites)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def draw_map(sites,canvas):\n",
    "    for i in range(len(sites)-1):\n",
    "        canvas.create_line(sites[i],sites[i+1],fill=\"green\")\n",
    "        canvas.create_line(sites[i], (sites[i][0]+5, sites[i][1]+5),fill=\"black\",width=4)\n",
    "        \n",
    "    canvas.create_text(sites[0][0]+5, sites[0][1]+15, text=\"0\")\n",
    "    \n",
    "window = tk.Tk()\n",
    "canvas = tk.Canvas(window, width=860, height=500)\n",
    "draw_map(sites,canvas)\n",
    "canvas.pack()\n",
    "window.mainloop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Randomly generated sites for a map](images/random_map.jpg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2927\n"
     ]
    }
   ],
   "source": [
    "def distance(sites,i,j):\n",
    "    try:\n",
    "        return(round(((sites[j][0]-sites[i][0])**2+(sites[j][1]-sites[i][1])**2)**(1/2)))\n",
    "    except IndexError:\n",
    "        print(i, j)\n",
    "        print(sites)\n",
    "        raise Exception\n",
    "    \n",
    "def total_distance(parcours):\n",
    "    S=distance(parcours,0,-1)\n",
    "    for i in range(len(parcours)-1):\n",
    "        S+=distance(parcours,i,i+1)\n",
    "    return(S)\n",
    "\n",
    "print(total_distance(sites))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Greedy Algorithm - Nearest Neighbor Heuristic\n",
    "The greedy algorithm starts from the first site and for each of the $(N-1)$ iterations we fly tot he next nearest location, before finally returning back to the starting location."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0, 266, 725, 363, 396, 818, 484, 702], [266, 0, 469, 113, 184, 578, 301, 462], [725, 469, 0, 362, 344, 151, 324, 101], [363, 113, 362, 0, 90, 466, 206, 350], [396, 184, 344, 90, 0, 422, 118, 307], [818, 578, 151, 466, 422, 0, 360, 116], [484, 301, 324, 206, 118, 360, 0, 256], [702, 462, 101, 350, 307, 116, 256, 0]]\n"
     ]
    }
   ],
   "source": [
    "def generate_distance_matrix(sites):\n",
    "    '''returns a matrix where M[i,j] is the distance between site i and j\n",
    "    '''\n",
    "    n=len(sites)\n",
    "    M=[ [0 for i in range(n)] for j in range(n)]\n",
    "    for i in range(n):\n",
    "        for j in range(i):\n",
    "            d=distance(sites,i,j)\n",
    "            M[i][j]=d\n",
    "            M[j][i]=d\n",
    "    return(M)\n",
    "\n",
    "print(generate_distance_matrix(sites))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nearest_neighbor(sites):\n",
    "    M=generate_distance_matrix(sites)\n",
    "    n=len(M[0])\n",
    "    L=[sites[0]]\n",
    "    current=0\n",
    "    \n",
    "    while len(L)<len(sites):\n",
    "        \n",
    "        for i in range(n):              # on in terdit que le plus proche voisin soit current\n",
    "            M[i][current]=sys.maxsize\n",
    "        \n",
    "        nextindex=M[current].index(min(M[current]))\n",
    "        L+=[sites[nextindex]]\n",
    "            \n",
    "        current=nextindex\n",
    "    return(L)\n",
    "    \n",
    "window = tk.Tk()\n",
    "canvas = tk.Canvas(window, width=860, height=500)\n",
    "draw_map(nearest_neighbor(sites),canvas)\n",
    "canvas.pack()\n",
    "window.mainloop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Greedy algorithm results](images/map_greedy.jpg)\n",
    "The complexity of the above algorithm is $\\mathcal{O}(n^2)$ where $n$ is the number of sites."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of sites: 100 , Calculation time: 0.018966200000001265\n",
      "Number of sites: 125 , Calculation time: 0.01955149999999861\n",
      "Number of sites: 150 , Calculation time: 0.022667000000005544\n",
      "Number of sites: 175 , Calculation time: 0.028084399999997345\n",
      "Number of sites: 200 , Calculation time: 0.03800369999999731\n",
      "Number of sites: 225 , Calculation time: 0.04512799999999828\n",
      "Number of sites: 250 , Calculation time: 0.05273620000000534\n",
      "Number of sites: 275 , Calculation time: 0.0686370000000025\n",
      "Number of sites: 300 , Calculation time: 0.07606409999999642\n",
      "Number of sites: 325 , Calculation time: 0.09032039999999597\n",
      "Number of sites: 350 , Calculation time: 0.10669379999999506\n",
      "Number of sites: 375 , Calculation time: 0.11888340000000142\n",
      "Number of sites: 400 , Calculation time: 0.14402439999999928\n",
      "Number of sites: 425 , Calculation time: 0.14897210000000172\n",
      "Number of sites: 450 , Calculation time: 0.17764139999999884\n",
      "Number of sites: 475 , Calculation time: 0.18351279999999548\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYoAAAEGCAYAAAB7DNKzAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAVSUlEQVR4nO3df5BsZX3n8fdHKRZCUEhAEK7slVKMJiLiiMmyBlkoICwLWcMaXBPxB0u5a9zsr4QgFd31llXuslVJpSQxdzFX40qMQgguIL9KCcsC6ty9/BKIIQTkLkO4ymoSlRq5fPeP07O0Q8+ZvjPTfXp63q+qrulzztPdX7ye+czznD7Pk6pCkqSlPK/rAiRJk82gkCS1MigkSa0MCklSK4NCktRqr64LGIWDDjqoNm/e3HUZkrRubN++/ZtVdfCgY1MZFJs3b2Z2drbrMiRp3UjyyFLHHHqSJLUyKCRJrQwKSVIrg0KS1MqgkCS1MigkaRrMzcEJJ8Djj6/5WxsUkjQNtmyBW29tfq4xg0KS1ru5Odi2DZ55pvm5xr0Kg0KSJtkwQ0pbtjQhAbB795r3KgwKSZpkyw0pLfQm5ueb7fn5Ne9VGBSSNKmGGVLq700sWONehUEhSZNqmCGl229/tjexYH4ebrttzcrINK6ZPTMzU04KKGldm5uDI4+Ep556dt+++8JDD8Ghh675xyXZXlUzg47Zo5CkSTSGIaVhGRSSNInGMKQ0rKlcj0KS1r0dO7qu4P+zRyFJamVQSJJaGRSSpFYGhSSplUEhSWplUEiSWhkUkqRWBoUkjdMIV6IbFYNCksZphCvRjYpBIUnjMuKV6EbFoJCk1Rp2OGnEK9GNikEhSas1zHDSGFaiGxWDQpJWY9jhpAmaNnxPGRSStBrDDidN0LThe8oV7iRppca8Ct0oucKdJI3COh5O2hOdBEWSi5M8kOTuJFcmOWCJdqcl+fMkDyb5jXHXKUmt1vFw0p7oqkdxI/BTVXU08HXgwsUNkjwfuAT4OeBVwFuTvGqsVUpSmx07oOq5jwlanW4tdBIUVXVDVT3d27wD2DSg2XHAg1X1UFXNA58BzhpXjZKkxiRco3gX8IUB+w8HHu3b3tnbN1CS85PMJpndtWvXGpcoSRvXXqN64yQ3AYMu+19UVVf12lwEPA18etBbDNi35Fe0qmorsBWabz3tccGSpIFGFhRVdXLb8STnAmcAJ9Xg7+juBF7St70JeGztKpQkDaOrbz2dBlwAnFlV31ui2VeBlyd5aZK9gXOAz4+rRklSo6trFB8F9gduTHJnko8BJDksybUAvYvdvwJcD9wPfLaqvtZRvZK0YY1s6KlNVb1sif2PAaf3bV8LXDuuuiRJzzUJ33qSJE0wg0KS1MqgkKR+63BN61EzKCSp3zpc03rUDApJWrBO17QeNYNCkhas0zWtR82gkCRY12taj5pBIUmwYRYhWgmDQpJgwyxCtBKd3JktSRNnyhYbWkv2KCRJrQwKSdPLm+fWhEEhaXp589yaMCgkTSdvnlszBoWk6eTNc2vGoJA0fbx5bk0ZFJKmjzfPrSmDQtL08ea5NeUNd5KmjzfPrSl7FJKkVgaFJKmVQSFJamVQSJJaGRSSpFYGhSSplUEhSWplUEiabE4V3jmDQtJkc6rwzhkUkiaXU4VPBINC0uRyqvCJYFBImkxOFT4xDApJk8mpwieGQSFpMjlV+MRwmnFJk8mpwidGJ0GR5GLgnwDzwF8C76yqbw9o9zDwt8Bu4OmqmhlnnZKk7oaebgR+qqqOBr4OXNjS9sSqOsaQkKRudBIUVXVDVT3d27wD2NRFHZKk5U3Cxex3AV9Y4lgBNyTZnuT8tjdJcn6S2SSzu3btWvMiJWmjGtk1iiQ3AYcOOHRRVV3Va3MR8DTw6SXe5viqeizJi4AbkzxQVbcMalhVW4GtADMzM7Xq/wBJEjDCoKiqk9uOJzkXOAM4qaoG/mKvqsd6P59IciVwHDAwKCRJo9HJ0FOS04ALgDOr6ntLtNkvyf4Lz4FTgHvHV6UkCbq7RvFRYH+a4aQ7k3wMIMlhSa7ttTkEuDXJXcBXgGuq6rpuypW0Yk4Tvu51ch9FVb1sif2PAaf3nj8EvGacdUkagf5pwi+5pOtqtAKT8K0nSdPKacKngkEhaXScJnwqGBSSRsNpwqeGQSFpNJwmfGoYFJJGw2nCp4bTjEsaDacJnxr2KCRJrQwKSUvzZjlhUEhq03+znDYsg0LSYN4spx6DQtJg3iynnqGDIsmBSX4yyZFJDBhpmnmznPq0/sJP8sIk709yD82Spb8PfBZ4JMnnkpw4jiIljZk3y6nPcvdRXA78IfDGqvp2/4EkrwN+OcmRVfXxURUoqQPeLKc+ywXFeVX1yKADVbUd2L72JUnqnDfLqc9y1xquHEsVkqSJtVxQZCxVSJIm1nJDT4cn+Z2lDlbVv17jeiRJE2a5oPg+XoeQpA1tuaD4VlV9ciyVSJIm0nLXKOaXOS5JmnLLBcU5bQfT2LSG9UiSJsxyQ08X96bruIrmWsUuYB/gZcCJwEnAB4GdoyxSktSd1qCoqn+W5FXA24B3AS+mucB9P3AN8OGqemrkVUqSOrPsUqhVdR9w0RhqkSRNoKHWzE7y5gG7vwPcU1VPrG1JkqRJMlRQAO8Gfgb4Um/7TTSzyR6V5ENV9akR1CZJmgDDBsUzwCur6q8BkhwC/B7wBuAWwKCQpCk17AJEmxdCoucJ4KiqehL4wdqXJUmaFMP2KP5nkquBz/W2zwZuSbIf8O2lXyZJWu+G7VG8F9gGHAO8Fvgk8N6q+m5VucqdNGnm5uCEE1y6VGtiqKCoqgJuBb4I3ATc0tsnaRJt2QK33urSpVoTQwVFkrcAX6EZcnoL8OUkZ4+yMEkrNDcH27Y1a15v22avQqs27NDTRcDrq+rcqno7cBzwm6MrS9KKbdnShATA7t32KrRqwwbF8xbdWPetPXitpHFZ6E3M9yZ+np+3V6FVG/aX/XVJrk/yjiTvoJnn6drVfHCSLUnuTnJnkhuSHLZEu3OT/EXvce5qPlOaev29iQX2KrRKw17M/jVgK3A08Bpga1VdsMrPvriqjq6qY4CrgQ8sbpDkx2hmp30DzXDXB5McuMrPlabX7bc/25tYMD8Pt93WTT2aCsPeR0FVXQFcsVYfXFV/07e5HzDoW1SnAjf2buwjyY3AacAfrVUd0lTZsaPrCjSFWoMiyd8y+Bd4aL41+4LVfHiSDwNvp5lgcND9GIcDj/Zt7+ztG/Re5wPnAxxxxBGrKUuS1Kd16Kmq9q+qFwx47D9MSCS5Kcm9Ax5n9d7/oqp6CfBp4FcGvcWgspaodWtVzVTVzMEHH7xcaZKkIQ099LQSVXXykE0vo7lA/sFF+3fSzFS7YBNw86oLkyQNrbOvuCZ5ed/mmcADA5pdD5yS5MDeRexTevskSWMy0h7FMj6S5BU0U5g/ArwHIMkM8J6qOq+qnkyyBfhq7zUfWriwLUkaj0zjlE0zMzM1OzvbdRnScObm4Jxz4I//GA49tOtqtEEl2V5VM4OOeXe11DUn8NOEMyikLjmBn9YBg0LqkhP4aR0wKKSuOIGf1gmDQuqKE/hpnTAopK44gZ/WiS7vo5A2Nifw0zphj0KS1MqgkCS1MigkSa0MCklSK4NCktTKoJAktTIoJEmtDAppGHNzcMIJTq+hDcmgkIbhVODawAwKaTlOBa4NzqCQluNU4NrgDAqpjVOBSwaF1MqpwCWDQmrlVOCS04xLrZwKXLJHIUlqZ1BIkloZFJKkVgaFJKmVQSFJamVQSJJaGRSSpFYGhSSplUEhSWplUEiSWhkUkqRWBoUkqVUnkwIm2QKcBTwDPAG8o6oeG9BuN3BPb/MbVXXm+KqUJEF3PYqLq+roqjoGuBr4wBLtvl9Vx/QehoQkdaCToKiqv+nb3A+oLuqQJC2vs2sUST6c5FHgbSzdo9gnyWySO5L8/DLvd36v7eyuXbvWvF5J2qhSNZo/5pPcBBw64NBFVXVVX7sLgX2q6oMD3uOwqnosyZHAF4GTquovl/vsmZmZmp2dXUX1krSxJNleVTODjo3sYnZVnTxk08uAa4DnBMXCBe6qeijJzcBrgWWDQpK0djoZekry8r7NM4EHBrQ5MMnf6z0/CDgeuG88FUqSFnR1jeIjSe5NcjdwCvCrAElmklzaa/NKYDbJXcCXgI9UlUGhHzY3ByecAI8/3nUl0tTq5D6KqvqFJfbPAuf1nt8GvHqcdWkd2rIFbr21+XnJJV1XI00l78zW+jU3B9u2wTPPND/tVUgjYVBo/dqypQkJgN27m21Ja86g0Pq00JuYn2+25+ftVUgjYlBofervTSywVyGNhEGh9en225/tTSyYn4fbbuumHmmKdfKtJ2nVduzougJpw7BHIUlqZVBIkloZFJKkVgaFJKmVQSFJamVQSJJaGRSSpFYGhSSplUEhSWplUEiSWhkUWhuuNCdNLYNCa6N/pTlJU8Wg0Oq50pw01QwKrZ4rzUlTzaDQ6rjSnDT1DAqtjivNSVPPoNDquNKcNPVc4U6r40pz0tSzRyFJamVQSJJaGRSSpFYGhSSplUEhSWplUKxXTsInaUwMivXKSfgkjYlBsR45CZ+kMTIo+q2X4Rwn4ZM0RgZFv/UwnOMkfJLGzKBYsF6Gc5yET9KYdR4USf5Dkkpy0BLHz03yF73HuSMrZL0M5zgJn6QxS1V19+HJS4BLgZ8AXldV31x0/MeAWWAGKGB7r93/bXvfmZmZmp2dHb6QuTk48kh46qln9+27Lzz0EBx66PDvI0nrVJLtVTUz6FjXPYrfAn6dJgQGORW4saqe7IXDjcBpa16FwzmStKTOgiLJmcD/qaq7WpodDjzat72zt2/Q+52fZDbJ7K5du/asGIdzJGlJI12PIslNwKCxm4uA9wOnLPcWA/YN7H1U1VZgKzRDT3tQpmsqSFKLkQZFVZ08aH+SVwMvBe5KArAJ+N9Jjquq/q8b7QTe1Le9Cbh5JMVKkgbqZOipqu6pqhdV1eaq2kwTCMcuCgmA64FTkhyY5ECaHsj1Yy5Xkja0ri9mP0eSmSSXAlTVk8AW4Ku9x4d6+yRJYzIRa2b3ehULz2eB8/q2/wD4gw7KkiQxgT0KSdJk6fSGu1FJsgt4ZAUvPQj45rKtumFtK2NtK2NtK7Oea/v7VXXwoANTGRQrlWR2qTsTu2ZtK2NtK2NtKzOttTn0JElqZVBIkloZFD9sa9cFtLC2lbG2lbG2lZnK2rxGIUlqZY9CktTKoJAktdqQQZHk+Ul2JLl6ieNvSXJfkq8luWxSaktyRJIv9Y7fneT0Mdf2cJJ7ktyZ5DkrQ6XxO0ke7NV37ATV9rZeTXcnuS3Jayaltr52r0+yO8nZk1Rbkjf1jn8tyZ9NSm1JXpjkfyS5q1fbO8dY2wFJLk/yQJL7k/zMouNdngvL1bbn50JVbbgH8O+Ay4CrBxx7ObADOLC3/aIJqm0r8C97z18FPDzm2h4GDmo5fjrwBZrp4X8a+PIE1fYP+v5Nf26Sauu1eT7wReBa4OxJqQ04ALgPOKK3PbbzYYja3g/8597zg4Engb3HVNsngfN6z/cGDlh0vMtzYbna9vhc2HA9iiSbgH9MswTrIP8CuKR6y61W1RMTVFsBL+g9fyHw2Djq2gNnAX9YjTuAA5K8uOuiAKrqtnp2Cd07aKasnyTvA64Axvb/tyH9c+BPquobMN7zYQgF7J9mrYIfpQmKp0f9oUleAPws8HGAqpqvqm8vatbJuTBMbSs5FzZcUAC/TbP86jNLHD8KOCrJ/0pyR5K1X3p1acvV9h+BX0qyk+Yvz/eNqa4FBdyQZHuS8wccH3pFwhFYrrZ+76b5a29cWmtLcjjwT4GPjbGmBcv973YUcGCSm3tt3j5BtX0UeCXNH0z3AL9aVUudO2vpSGAXsK03DHxpkv0WtenqXBimtn5DnQsbKiiSnAE8UVXbW5rtRTP89CbgrcClSQ6YkNreCnyiqjbRdG0/lWSc/4bHV9WxNN3V9yb52UXHh16RcASWqw2AJCfSnBwXjKmuYWr7beCCqto9xpoWLFfbXsDraHq6pwK/meSoCantVOBO4DDgGOCjvb+oR20v4Fjg96rqtcB3gd9Y1Karc2GY2oA9Oxc2VFAAxwNnJnkY+Azwj5L890VtdgJXVdUPquqvgD+nCY5JqO3dwGcBqup2YB+aib7Goqoe6/18ArgSOG5Rk53AS/q2NzGm4bEhaiPJ0TTDemdV1bfGUdeQtc0An+n9258N/G6Sn5+Q2nYC11XVd6vqm8AtwFi+CDBEbe+kGRarqnoQ+CvgJ8ZQ2k5gZ1V9ubd9Oc0v58VtujgXhqltj8+FDRUUVXVhVW2qZv2Lc4AvVtUvLWr2p8CJAEkOoul6PzQhtX0DOKlX2ytpgmLXqGvrfd5+SfZfeE6z2uC9i5p9Hnh77xsfPw18p6rmJqG2JEcAfwL8clV9fdQ17UltVfXSena1x8uBf1VVfzoJtQFXAW9MsleSHwHeANw/IbX1nw+HAK9gPOfq48CjSV7R23USzQX/fp2cC8PUtpJzYSIWLupakg8Bs1X1eZ5dfvU+YDfwa+P863OZ2v498N+S/Fuabuw7qvfVhTE4BLiyuW7IXsBlVXVdkvcAVNXHaK6bnA48CHyP5i++SantA8CP0/y1DvB0jWeWz2Fq68qytVXV/UmuA+6muXZ2aVUt/oXdSW00q19+Isk9NEM9F/R6PePwPuDTSfamCad3Tsi5MExte3wuOIWHJKnVhhp6kiTtOYNCktTKoJAktTIoJEmtDApJUiuDQlqBJH+3ytdfnuTI3vOHk1zRd+zsJJ/oPT8jyX9aVbHSKhkU0pgl+Ung+VXVf3PYTG//YtfQ3LH/I+OpTnoug0Jahd6dtxcnuTfN2gm/2Nv/vCS/m2adhKuTXJtn15l4G80dz/3+K8202T+kd0PlzcAZI/zPkFoZFNLqvJlmQrrXACcDF6eZTvrNwGbg1cB5QP/iMccDiyd//CxwbJKXDfiMWeCNa1u2NDyDQlqdfwj8UVXtrqq/Bv4MeH1v/+eq6pne/Dtf6nvNi3nuHF27gYuBCwd8xhM0M6RKnTAopNUZNJ10236A79NM6LjYp2gWnTli0f59eq+ROmFQSKtzC/CLadY6P5jmF/1XgFuBX+hdqziEZn2TBfcDzxliqqofAL8F/JtFh47iuTOnSmNjUEircyXNzKp30ax5/eu9oaYraNYGuBf4feDLwHd6r7mGHw6Ofh/nubM6n9h7jdQJZ4+VRiTJj1bV3yX5cZpexvFV9XiSfWmuWRy/3Kp2vd7IZVV10hhKlgYyKKQRSXIzcACwN/BfquoTfcdOBe6vqm8s8x6vB35QVXeOsFSplUEhSWrlNQpJUiuDQpLUyqCQJLUyKCRJrQwKSVKr/wfzuLEJrLMJiQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "N_list = np.arange(100,500,25)\n",
    "Time_list = []\n",
    "\n",
    "for N in N_list:\n",
    "   c = generate_map(840, 480, N)\n",
    "\n",
    "   ti = time.perf_counter()\n",
    "   nearest_neighbor(c)\n",
    "   ts = time.perf_counter()\n",
    "\n",
    "   print(\"Number of sites:\", N, \", Calculation time:\", ts - ti)\n",
    "   Time_list.append(math.log(ts - ti))\n",
    "\n",
    "#print N_list, time_list\n",
    "plt.xlabel('log(N)')\n",
    "plt.ylabel('log(T)')\n",
    "plt.plot(np.log(N_list), Time_list, 'r^')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The gradient of the above curve is approximately 2, which agrees with the complexity of $n^2$.\n",
    "\n",
    "## Exhaustive Search Algorithm\n",
    "A brute force method which goes through all possible paths and keeps the one which is the shortest. The complexity of such a algorithm would be $\\mathcal{O}(n!)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "path_list = []\n",
    "\n",
    "def all_paths(start_path, remaining_sites):\n",
    "    if len(remaining_sites)==1:\n",
    "        global path_list\n",
    "        path_list+=[start_path + remaining_sites]\n",
    "        return\n",
    "    for site in range(len(remaining_sites)):\n",
    "        all_paths(start_path+[remaining_sites[site]], remaining_sites[:site]+remaining_sites[site+1:])\n",
    "        \n",
    "all_paths([], sites)\n",
    "# print(path_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(831, 75), (566, 103), (483, 179), (144, 307), (106, 453), (203, 389), (459, 384), (486, 269)]\n"
     ]
    }
   ],
   "source": [
    "shortest = sys.maxsize\n",
    "\n",
    "def shortest_path(start_path, remaining_sites):\n",
    "    if len(remaining_sites)==1:\n",
    "        global path_list\n",
    "        global shortest\n",
    "        if(total_distance(start_path+remaining_sites) < shortest):\n",
    "            path_list=start_path + remaining_sites\n",
    "            shortest=total_distance(path_list)\n",
    "        return\n",
    "    for site in range(len(remaining_sites)):\n",
    "        shortest_path(start_path+[remaining_sites[site]], remaining_sites[:site]+remaining_sites[site+1:])\n",
    "\n",
    "def brute_force(sites):\n",
    "    shortest_path([], sites)\n",
    "    return(path_list)\n",
    "\n",
    "print(brute_force(sites))\n",
    "window = tk.Tk()\n",
    "canvas = tk.Canvas(window, width=860, height=500)\n",
    "draw_map(brute_force(sites),canvas)\n",
    "canvas.pack()\n",
    "window.mainloop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![best path from exhaustive search](images/best_path.jpg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of sites: 5 , calculation time: 0.0021205000000037444\n",
      "Number of sites: 6 , calculation time: 0.014943700000003446\n",
      "Number of sites: 7 , calculation time: 0.06718379999999513\n",
      "Number of sites: 8 , calculation time: 0.47264979999999923\n",
      "Number of sites: 9 , calculation time: 4.462043000000008\n",
      "Number of sites: 10 , calculation time: 54.167457799999994\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYAAAAEGCAYAAABsLkJ6AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAASdUlEQVR4nO3de5BkZX3G8e8PkDIREBKGi1xcDSFKCEYcvATMipASFSVBohhvQS2qUsZgVUSjlLGSKauMpNSy1JgtcL0Gb0AwgjEiIE52AWfZRcBViygicdYdNF5QY8PML3+cM9lhtmemd3e63555v5+qru7Tfbr7YYrt57znGpmJJKk+e5UOIEkqwwKQpEpZAJJUKQtAkiplAUhSpfYpHWBXHHzwwblmzZrSMSRpRdm0adN9mTky//kVVQBr1qxhYmKidAxJWlEi4rvdnncVkCRVygKQpEpZAJJUKQtAkiplAUhSpYoXQETsHRGbI+JzpbNI0lCanIS1a2HbtmX92OIFAFwAbC0dQpKG1tgYjI8398uoaAFExJHAc4FLSuaQpKE1OQnr18PMTHO/jKOA0iOAdwNvAGYWmiEizo+IiYiYmJqaGlwySRoGY2PNjz/A9PSyjgKKFUBEnAlsz8xNi82XmesyczQzR0dGdjqSWZJWr9ml/06nme50lnUUUHIEcDLw/Ii4G/gE8MyI+FjBPJI0XOYu/c9axlFAsQLIzDdl5pGZuQY4F7guM19aKo8kDZ2NG3cs/c/qdGDDhmX5+BV1MjhJqsrmzX39+KEogMy8AbihcAxJqkrpvYAkSYVYAJJUKQtAkiplAUhSpSwASaqUBSBJlbIAJKlSFoAkVcoCkKRKWQCSVCkLQJIqZQFIUqUsAEmqlAUgSZWyACSpUhaAJFXKApCkSlkAklQpC0CSKmUBSFKlLABJqpQFIEmVsgAkqVIWgCRVygKQpEpZAJJUKQtAkiplAUhSpSwASaqUBSBJlSpWABFxVERcHxFbI+LOiLigVBZJqtE+Bb/7QeCvM/PWiNgf2BQRX8zMrxfMJEnVKDYCyMzJzLy1ffwzYCtwRKk8klSbodgGEBFrgCcCN3d57fyImIiIiampqUFHk6RVq3gBRMR+wOXA6zLzp/Nfz8x1mTmamaMjIyODDyhJq1TRAoiIh9H8+H88M68omUWSalNyL6AALgW2ZuY7S+WQpFqVHAGcDLwMeGZEbGlvzymYR5KqUmw30MwcB6LU90tS7YpvBJYklWEBSKrD5CSsXQvbtpVOMjQsAEl1GBuD8fHmXoAFIKkGk5Owfj3MzDT3jgIAC0BSDcbGmh9/gOlpRwEtC0DS6ja79N/pNNOdjqOAlgUgaXWbu/Q/y1EAYAFIWu02btyx9D+r04ENG8rkGSIlrwcgSf23eXPpBEPLEYAkVcoCkKRKWQCSVCkLQJIqZQFIUqUsAEmqlAUgSZWyACSpUhaAJFXKApCkSlkAklQpC0CSKmUBSFKlLABJqpQFIEmVsgAkqVIWgCRVygKQpEpZAJJUKQtAkiplAUhSpYoWQEScERHfjIi7IuJvSmaRpNoUK4CI2Bt4H/Bs4DjgxRFxXKk8klSbkiOAJwN3Zea3M7MDfAI4q2AeSapKyQI4AvjenOl72+ceIiLOj4iJiJiYmpoaWDhJWu1KFkB0eS53eiJzXWaOZuboyMjIAGJJUh1KFsC9wFFzpo8Evl8oiyRVp2QBfBX47Yh4TETsC5wLfLZgHkmqyj6lvjgzH4yIvwS+AOwNfDAz7yyVR5JqU6wAADLzGuCakhkkqVYeCSxJlbIAJKlSFoAkVarnbQARcRDwKOCXwN2ZOdO3VJKkvlu0ACLikcBrgBcD+wJTwMOBQyPiJuD9mXl931NKkpbdUiOAzwAfAZ6emT+e+0JEPAl4WUQ8NjMv7VdASVJ/LFUAr87M73Z7ITM3AZuWP5KkoTE5CeeeC5/8JBx2WOk0WmZLbQS+ciApJA2nsTEYH2/uteosVQDdTtgmqQaTk7B+PczMNPfbtpVOpGW21CqgIyLiPQu9mJl/tcx5JA2LsbHmxx9gerqZft/7ymbSslqqAH6J6/ml+swu/Xc6zXSn00y/5S1uC1hFliqAH2bmhweSRNLwmLv0P8tRwKqz1DaAzkBSSBouGzfuWPqf1enAhg1l8qgvlhoBnLvYixERwBGZee/yRZJU3ObNpRNoAJYqgIsjYi/gKpptAbNHAh8DnAqcBryV5upekqQVZNECyMw/jYjjgJcArwQOp9kwvBW4GnhbZv5v31NKkpbdkieDy8yvAxcNIIskaYB6OhtoRJzd5emfALdn5vbljSRJGoReTwf9KuBpwOyZP58B3AQcGxF/n5kf7UM2SVIf9VoAM8DjM/MHABFxKPBPwFOAGwELQJJWmF6vCLZm9se/tR04NjN/BDyw/LEkSf3W6wjgKxHxOeDT7fQ5wI0R8Qjgxwu/TZI0rHotgNcAZwOn0Jwh9MPA5ZmZNMcDSJJWmJ4KIDMzIsZpTg2RwC3tj78kaYXqaRtARLwQuIVm1c8LgZsj4px+BpMk9Vevq4AuAk6a3ec/IkaAa2muGSxJWoF63Qtor3kHfP1wF94rSRpCvY4A/j0ivgBc1k6/CLimP5EkSYPQ60bgCyPiBcDJNHsBrctMLxgvSStYryMAMvNy4PI+ZpEkDdCiBRARP6PZ7XOnl2j2Dj1gd740Ii4GnkezW+l/AedlpgeUSdIALbohNzP3z8wDutz2390f/9YXgeMz8wTgW8Cb9uCzJEm7ociePJn5H5n5YDt5E3BkiRySVLNh2JXzlcDnF3oxIs6PiImImJiamhpgLEla3XreCLyrIuJa4LAuL12UmVe181wEPAh8fKHPycx1wDqA0dFRTz8hScukbwWQmacv9npEvAI4EzjN8wpJ0uD1rQAWExFnAG8E1mbmL0pkkKTaldoG8F5gf+CLEbElIj5QKIckVavICCAzjynxvZKkHYZhLyBJUgEWgCRVygKQpEpZAJJUKQtAkiplAUi7anIS1q6FbdtKJ5H2iAUg7aqxMRgfb+6lFcwCkHbF5CSsXw8zM829owCtYBaAtCvGxpoff4DpaUcBWtEsAKlXs0v/nU4z3ek4CtCKZgFIvZq79D/LUYBWMAtA6tXGjTuW/md1OrBhQ5k80h4qcjI4aUXavLl0AmlZOQKQpEpZAJJUKQtAkiplAUhSpSwASaqUBSBJlbIAJKlSFoAkVcoCkKRKWQCSVCkLQJIqZQFIUqUsAEmqlAUgSZWyACSpUhaAJFXKApCkShUtgIh4fURkRBxcMock1ahYAUTEUcAfAfeUyiBJNSs5AngX8AYgC2aQpGoVKYCIeD7w35l5Ww/znh8RExExMTU1NYB0klSHvhVARFwbEXd0uZ0FXAT8bS+fk5nrMnM0M0dHRkb6FVeLmZyEtWth27bSSSQto74VQGaenpnHz78B3wYeA9wWEXcDRwK3RsRh/cqiPTQ2BuPjzb2kVWPgq4Ay8/bMPCQz12TmGuBe4MTMdPFyGE1Owvr1MDPT3DsKkFYNjwPQ4sbGmh9/gOlpRwHSKlK8ANqRwH2lc6iL2aX/TqeZ7nQcBUirSPEC0BCbu/Q/y1GAtGpYAFrYxo07lv5ndTqwYUOZPJKW1T6lA2iIbd5cOoGkPnIEIEmVsgAkqVIWgCRVygKQpEpZAJJUKQtAkiplAUhSpSwASaqUBSBJlbIAJKlSFoAkVcoCkKRKWQCSVCkLQJIqZQFIUqUsAEmqlAUgSZWyACSpUhaAJFXKApCkSlkAklQpC0CSKmUBSFKlLABJqpQFIEmVsgAkqVIWgCRVqlgBRMRrI+KbEXFnRLyjVA5JqtU+Jb40Ik4FzgJOyMxfRcQhJXJIUs1KjQD+Anh7Zv4KIDO3F8ohSdUqVQDHAk+PiJsj4ssRcdJCM0bE+RExERETU1NTu/dtk5Owdi1s27abcSVp9elbAUTEtRFxR5fbWTSrng4CngpcCHwqIqLb52TmuswczczRkZGR3QszNgbj4829JAnoYwFk5umZeXyX21XAvcAV2bgFmAEO7kuQyUlYvx5mZpp7RwGSBJRbBfSvwDMBIuJYYF/gvr5809hY8+MPMD3tKECSWqUK4IPAYyPiDuATwCsyM5f9W2aX/judZrrTcRQgSa0iBZCZncx8abtK6MTMvK4vXzR36X+WowBJAlb7kcAbN+5Y+p/V6cCGDWXySNIQKXIg2MBs3lw6gSQNrdU9ApAkLcgCkKRKWQCSVCkLQJIqZQFIUqWiH8df9UtETAHf7XH2g+nX0cX9Yd7+Mm9/raS8KykrLE/eR2fmTidTW1EFsCsiYiIzR0vn6JV5+8u8/bWS8q6krNDfvK4CkqRKWQCSVKnVXADrSgfYRebtL/P210rKu5KyQh/zrtptAJKkxa3mEYAkaREWgCRVakUXQER8MCK2txeWWWieZ0TEloi4MyK+PMh8XbIsmjciLmyzbmmvnzwdEb8x6Jxz8iyV95ER8W8RcVv79z1v0Bnn5Vkq70ERcWVEfC0ibomI4wedcU6WoyLi+ojY2v7tLugyT0TEeyLirjbziSWytll6yfu4iNgYEb+KiNeXyDknSy95X9L+Xb8WERsi4gklsrZZesl7Vpt1S0RMRMQpe/zFmblib8AfAicCdyzw+oHA14Gj2+lDhjnvvHmfB1w3zHmBNwP/0D4eAX4E7DvEeS8G3to+fhzwpYJZDwdObB/vD3wLOG7ePM8BPg8E8FTg5iHPewhwEvA24PWlsu5C3j8ADmofP3sF/H33Y8d22xOAb+zp967oEUBm3kjzo7OQP6O5+Pw97fzbBxJsAT3knevFwGV9jLOkHvImsH9EBM3/nD8CHhxEtq5hls57HPCldt5vAGsi4tBBZJsvMycz89b28c+ArcAR82Y7C/hINm4CDoyIwwccFegtb2Zuz8yvAg8UiPgQPebdkJn/007eBBw52JQPydJL3vuz/fUHHkHz72+PrOgC6MGxwEERcUNEbIqIl5cO1IuI+HXgDODy0lmW8F7g8cD3gduBCzJzZvG3FHUbcDZARDwZeDQF/9HPiog1wBOBm+e9dATwvTnT97JzSQzcInmHUo95X0Uz2ipusbwR8ScR8Q3gauCVe/pdq70A9gGeBDwXeBbwlog4tmyknjwP+M/M7HW0UMqzgC3Ao4DfB94bEQeUjbSot9MsEGwBXgtspuCIBSAi9qMp+tdl5k/nv9zlLUX3214i79DpJW9EnEpTAG8cZLYFsiyaNzOvzMzHAX8M7PHFzVf3JSGbJab7MvPnwM8j4kbgCTTr14bZuRRe/dOj84C3t8PSuyLiOzTr1m8pG6u79h/UedBsYAW+096KiIiH0fxj/3hmXtFllnuBo+ZMH0kz2iqih7xDpZe8EXECcAnw7Mz84SDzdcnS8983M2+MiN+KiIMzc7dPFLfaRwBXAU+PiH3a1SpPoVm3NrQi4pHAWprsw+4e4DSAdl367wDfLppoERFxYETs206+Grix1FJsW0CXAlsz850LzPZZ4OXt3kBPBX6SmZMDCzlHj3mHRi95I+Jo4ArgZZlZdKGwx7zHtPPR7hG2L7BHpbWijwSOiMuAZ9CcLvUHwFuBhwFk5gfaeS6kWeqbAS7JzHcXCUvPef8cOCMzzy2Tcoel8kbEo4AP0ezBEDSjgY8VCUtPeZ8GfASYptk77FVzNgIOOuspwFdotp3Mbjd5M3A0/H/eoNnOcgbwC+C8zJwoELfXvIcBE8AB7Tz30+zJMvCS7THvJcAL2HGK+Qez0FlCe8z7RuDlNBvZfwlcmJnje/S9K7kAJEm7b7WvApIkLcACkKRKWQCSVCkLQJIqZQFIUqUsAGmOiLh/D9//mYh4bPv47oi4fM5r50TEh9rHZ0bE3+1RWGkPWQDSMomI3wX2zsy5B8ONts/PdzXw/PYARakIC0Dqoj369uJorstwe0S8qH1+r4h4f3vO9s9FxDURcU77tpew8xHc/0hzQM9DtKfPuAE4s4//GdKiLACpu7NpTnD3BOB04OL2VMxnA2uA36M5ncTT5rznZGDTvM/5FHBiRBzT5TsmgKcvb2ypdxaA1N0pwGWZOZ2ZPwC+THOxk1OAT2fmTGZuA66f857Dgal5nzNNcyGaN3X5ju00Z1KVirAApO66nYp5seehOT/Lw7s8/1Gaq5UdPe/5h7fvkYqwAKTubgReFBF7R8QIzQ/4LcA48IJ2W8ChNCefm7UV2GlVT2Y+ALwLeN28l44FFryetdRvFoDU3ZXA12iuInYd8IZ2lc/lNOfpvwP4Z5qrNv2kfc/VPLQQ5rqUna+/cWr7HqkIzwYq7aKI2C8z74+I36QZFZycmdsi4tdotgmcnJnTS3zGocC/ZOZpA4gsdWUBSLsoIm4ADqS5IMc7MvNDc157Fs1FPe5Z4jNOAh7IzC19jCotygKQpEq5DUCSKmUBSFKlLABJqpQFIEmVsgAkqVL/ByZ8q1PKsnOwAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "N_list = [5,6,7,8,9,10]\n",
    "Time_list = []\n",
    "\n",
    "for N in N_list:\n",
    "   c = generate_map(840, 480, N)\n",
    "\n",
    "   ti = time.perf_counter()\n",
    "   brute_force(c)\n",
    "   ts = time.perf_counter()\n",
    "\n",
    "   print(\"Number of sites:\", N, \", calculation time:\", ts - ti)\n",
    "   Time_list.append(math.log(ts - ti))\n",
    "\n",
    "#print N_list, time_list\n",
    "plt.xlabel('log(N)')\n",
    "plt.ylabel('log(T)')\n",
    "plt.plot(np.log(N_list), Time_list, 'r^')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Branch and Bound Algorithm\n",
    "Given the enormous time it takes to search all possible paths, the **branch and bound algorithm** aims to eliminate all the solutions that we known will be bad solutions. For a given map, we can calculate the minimum bound for all paths. We can consider the length of a path as the sum of the weights on each movement from site to site. If we take the 2 nearest neighbors for every site, then the average of these two distances forms the lower bound. We can be sure that the best path is atleast greater than this average. Mathematically, for each site $i$, we note $(a_i, b_i)$ the distances to two nearest neighbors and then calculate the sum $\\frac{1}{2}\\sum_i (a_i +b_i)$.\n",
    "\n",
    "Once we decide to go to a stop, this has a consequence on the inferior bound, and we recalculate this bound after each stop. The branch and bound algorithm will recursively explore the possible set of paths and save in memory the best path it encounters. As soon as a branch incurs a cost greater than the current best path, this branch is then abandoned, without going any further. As a result the algorithm does not explore any of the sub branches from that branch as it knows for sure that they will all be atleast the same bound.\n",
    "\n",
    "The `min_bound()` calculates the minimum bound for a given path."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def min_bound(start_path, remaining_sites):\n",
    "    min_bound = 0\n",
    "\n",
    "    remaining_sites_copy = remaining_sites[:]\n",
    "    remaining_sites_copy.append(start_path[0])\n",
    "    remaining_sites_copy.append(start_path[-1])\n",
    "    distance_matrix = generate_distance_matrix(remaining_sites_copy)\n",
    "\n",
    "    l = len(distance_matrix)\n",
    "    for i in range(l-2):                                # trouve les deux plus petites distances entre sites restants et sites restants bis\n",
    "        min1, min2 = sys.maxsize, sys.maxsize\n",
    "        for j in range(l):\n",
    "            if j != i:\n",
    "                distance_i_j = distance_matrix[i][j]\n",
    "                if distance_i_j <= min1:\n",
    "                    min2 = min1\n",
    "                    min1 = distance_i_j\n",
    "                elif distance_i_j < min2:\n",
    "                    min2 = distance_i_j\n",
    "        min_bound += min1 + min2\n",
    "\n",
    "    for i in range(l-2, l):                     # trouve la plus petite distance entre entame [0], [-1] et sites restants\n",
    "        min = sys.maxsize\n",
    "        for j in range(l-2):\n",
    "            distance_i_j = distance_matrix[i][j]\n",
    "            if distance_i_j < min:\n",
    "                min = distance_i_j\n",
    "        min_bound += min\n",
    "\n",
    "    for i in range(0,len(start_path)-1):               # trouve la distance totales des points déjà visités\n",
    "        min_bound += distance(start_path, i, i+1)\n",
    "    for i in range(1,len(start_path)):\n",
    "        min_bound += distance(start_path, i-1, i)\n",
    "\n",
    "    return math.ceil(min_bound/2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20\n",
      "26\n"
     ]
    }
   ],
   "source": [
    "# illustrative example [a, b, c ,d ,e] centered around 'e'\n",
    "a, b, c, d, e = (3, 4), (6, 4), (9, 4), (3, 0), (0, 0)\n",
    "\n",
    "# we choose site (b,d)\n",
    "print(min_bound([b, d], [a, c, e])) # must be 20\n",
    "\n",
    "## choose a -> e -> c\n",
    "print(min_bound([a, e, c], [b, d])) # must be 26"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "best_bound= sys.maxsize\n",
    "    \n",
    "def shortest_path_branch_bound(start_path, remaining_sites):\n",
    "    if len(remaining_sites)==1:\n",
    "        global path_list\n",
    "        path_list=start_path + remaining_sites\n",
    "        return\n",
    "    for site in range(len(remaining_sites)):\n",
    "        if(min_bound(start_path, remaining_sites) < best_bound):\n",
    "            shortest_path_branch_bound(start_path+[remaining_sites[site]], remaining_sites[:site]+remaining_sites[site+1:])\n",
    "\n",
    "def branch_bound(sites):\n",
    "    shortest_path_branch_bound([sites[0]], sites[1:])\n",
    "    return(path_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Brute Force:  2927 , Branch and Bound:  2927\n"
     ]
    }
   ],
   "source": [
    "shortest_bb = branch_bound(sites)\n",
    "window = tk.Tk()\n",
    "canvas = tk.Canvas(window, width=860, height=500)\n",
    "draw_map(shortest_bb, canvas)\n",
    "canvas.pack()\n",
    "window.mainloop()\n",
    "print(\"Brute Force: \", total_distance(brute_force(sites)), \", Branch and Bound: \", total_distance(shortest_bb))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "OK\n",
      "OK\n",
      "OK\n",
      "OK\n"
     ]
    }
   ],
   "source": [
    "N_max = 7\n",
    "window = tk.Tk()\n",
    "canvas = tk.Canvas(window, width=860, height=500)\n",
    "\n",
    "for N in range(4, N_max+1):\n",
    "   c = generate_map(840, 480, N)\n",
    "   shortest1 = branch_bound(c)\n",
    "   shortest2 = brute_force(c)\n",
    "   if total_distance(shortest1) != total_distance(shortest2):\n",
    "       draw_map(shortest1, canvas)\n",
    "       draw_map(shortest2, canvas)\n",
    "       print(c)\n",
    "       break\n",
    "   else:\n",
    "       print('OK')\n",
    "\n",
    "canvas.pack()\n",
    "window.mainloop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of sites: 5 , Calculation time: 0.0026585999999895193\n",
      "Number of sites: 6 , Calculation time: 0.008084200000013197\n",
      "Number of sites: 7 , Calculation time: 0.05076069999998367\n",
      "Number of sites: 8 , Calculation time: 0.29727969999999004\n",
      "Number of sites: 9 , Calculation time: 2.390601800000013\n",
      "Number of sites: 10 , Calculation time: 23.6946078\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYAAAAEGCAYAAABsLkJ6AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAR00lEQVR4nO3dfZAkdX3H8fcXkDIRFJI7AXnwNIQoKkZcfAiQFSERjUqCRDFGDWpRZRmjVRGNUpaVbFllgqUpS425EtaHGBL1IBohMaLgudkD3OMOQU8t4gMS52TR+IAaB3a/+aN7c8ve7O4sOzM9s7/3q2prtmd6pj+3VTef/nXP9C8yE0lSeQ5oOoAkqRkWgCQVygKQpEJZAJJUKAtAkgp1UNMB1mLTpk25ZcuWpmNI0kjZuXPnXZm5een9I1UAW7ZsYWZmpukYkjRSIuLbne73EJAkFcoCkKRCWQCSVCgLQJIKZQFIUqEsAEkadq0WjI/D3r09fVkLQJKG3cQETE1Vtz1kAUjSMGu1YHIS5uer2x6OAiwASRpmExPVmz/A3FxPRwEWgCQNq4W9/3a7Wm63ezoKsAAkaVgt3vtf0MNRgAUgScNqx459e/8L2m2Ynu7Jy4/UxeAkqSi7dvX15R0BSFKhLABJKpQFIEmFsgAkqVAWgCQVygKQpEJZAJJUKAtAkgplAUhSoSwASSqUBSBJhbIAJKlQFoAkFcoCkKRCWQCSVCgLQJIKZQFIUqEaK4CIODYiro2IPRHx5Yh4TVNZJKlETU4JeS/w55l5U0QcCuyMiM9k5lcazCRJxWhsBJCZrcy8qf79J8Ae4Oim8khSaYbiHEBEbAGeANzQbBJJKkfjBRARhwDbgNdm5o87PH5hRMxExMzs7OzgA0rSBtVoAUTEA6je/D+SmVd0Wiczt2bmWGaObd68ebABJWkDa/JTQAFcCuzJzHc0lUOSStXkCOBU4MXA0yNid/3zrAbzSFJRGvsYaGZOAdHU9iWpdI2fBJYkNcMCkKRCWQCSVCgLQJIKZQFIUqEsAEkqlAUgSYWyACSpUBaAJBXKApCkQlkAklQoC0CSCmUBSFKhLABJKpQFIEmFsgAkqVAWgKQytFowPg579zadZGhYAJLKMDEBU1PVrQALQFIJWi2YnIT5+erWUQBgAUgqwcRE9eYPMDfnKKBmAUja2Bb2/tvtarnddhRQswAkbWyL9/4XOAoALABJG92OHfv2/he02zA93UyeIXJQ0wEkqa927Wo6wdByBCBJhbIAJKlQFoAkFcoCkKRCWQCSVCgLQJIKZQFIUqEsAEkqlAUgSYWyACSpUBaAJBWq0QKIiLMj4msRcVtE/EWTWSSpNI0VQEQcCLwHeCZwIvDCiDixqTySVJomRwBPAm7LzG9kZhv4J+CcBvNIUlGaLICjge8sWr6jvu8+IuLCiJiJiJnZ2dmBhZOkja7JAogO9+V+d2RuzcyxzBzbvHnzAGJJUhmaLIA7gGMXLR8DfLehLJJUnCYL4IvAr0fEIyLiYOB84JMN5pGkojQ2JWRm3hsRfwp8GjgQuCwzv9xUHkkqTaNzAmfm1cDVTWaQpFL5TWBJKpQFIEmFsgAkqVAWgCQVygKQpEJZAJJUKAtAkgplAUhSoSwASSqUBSBJhbIAJKlQFoAkFarri8FFxOHAw4CfA9/KzPm+pZIk9d2KBRARDwFeBbwQOBiYBR4IHBER1wPvzcxr+55SktRzq40APg58CDg9M3+4+IGIeCLw4oh4ZGZe2q+AkqT+WK0AXpGZ3+70QGbuBHb2PpIkaRBWOwl85UBSSJIGbrUCiIGkkDScWi0YH4e9e5tOoj5Y7RDQ0RHxruUezMw/63EeScNkYgKmpqrb97yn6TTqsdUK4Od4nF8qU6sFk5MwP1/dvvnNcOSRTadSD61WAN/PzA8OJImk4TIxUb35A8zNOQrYgFY7B9AeSApJw2Vh779dvwW029Wy5wI2lNUK4PyVHozKMT3MI2kYLN77X7AwCtCGsdohoEsi4gDgE1TnAha+CXw8cAZwJvAW4I5+hpQ0YDt27Nv7X9Buw/R0M3nUFysWQGb+YUScCLwIeBlwFNWJ4T3AVcBbM/N/+55S0mDt2tV0Ag3AqheDy8yvABcPIIskaYC6uhpoRJzb4e4fAbdk5p29jSRJGoRuLwf9cuCpwMKVP58GXA+cEBF/lZkf7kM2SVIfdVsA88CjM/N7ABFxBPB3wJOB7YAFIEkjptsZwbYsvPnX7gROyMwfAPf0PpYkqd+6HQF8ISI+BXysXj4P2B4RDwJ+uPzTJEnDqtsCeBVwLnAa1RVCPwhsy8yk+j6AJGnEdFUAmZkRMUV1aYgEbqzf/CVJI6qrcwAR8XzgRqpDP88HboiI8/oZTJLUX90eAroYOGXhM/8RsRm4hmrO4DWLiEuA51CNKP4LuGDpnMOSpP7q9lNAByz5wtf31/DcTj4DPDYzTwK+DrxxHa8lSbofuh0B/HtEfBq4vF5+AXD1/d1oZv7HosXrqQ4tSZIGqNuTwBdFxPOAU6k+BbQ1M3s1YfzLgH/u0WtJkrrU7QiAzNwGbOt2/Yi4Bug0f9zFmfmJep2LgXuBj6zwOhcCFwIcd9xx3W5ekrSKFQsgIn5C9bHP/R6i+nTog5d7bmaetcprvxR4NnDmSh8pzcytwFaAsbExP3oqST2y2nwAh/ZjoxFxNvAGYDwzf9aPbUiSVraeT/Ksx7uBQ4HPRMTuiHhfQzkkqVhdnwPopcw8vontSpL2aWoEIElqmAUgSYWyACSpUBaAJBXKApCkQlkAklQoC0CSCmUBSFKhLABJKpQFIEmFsgAkqVAWgCQVygKQpEJZANJatVowPg579zadRFoXC0Baq4kJmJqqbqURZgFIa9FqweQkzM9Xt44CNMIsAGktJiaqN3+AuTlHARppFoDUrYW9/3a7Wm63HQVopFkAUrcW7/0vcBSgEWYBSN3asWPf3v+Cdhump5vJI61TI5PCSyNp166mE0g95QhAkgplAUhSoSwASSqUBSBJhbIAJKlQFoAkFcoCkKRCWQCSVCgLQJIKZQFIUqEsAEkqlAUgSYWyACSpUBaAJBWq0QKIiNdFREbEpiZzSFKJGiuAiDgW+B3g9qYySFLJmhwBvBN4PZANZpCkYjVSABHxXOC/M/PmLta9MCJmImJmdnZ2AOkkqQx9mxIyIq4Bjuzw0MXAm4Df7eZ1MnMrsBVgbGzM0YIk9UjfCiAzz+p0f0Q8DngEcHNEABwD3BQRT8rMvf3KI0m6r4FPCp+ZtwAPXViOiG8BY5l516CzSFLJ/B6AJBVq4COApTJzS9MZJKlEjgAkqVAWgCQVygKQpEJZAJJUKAtAkgplAUhSoSwASSqUBSBJhbIAJKlQFoBW12rB+Djs9Vp90kZiAWh1ExMwNVXdStowLACtrNWCyUmYn69uHQVIG4YFoJVNTFRv/gBzc44CpA3EAtDyFvb+2+1qud12FCBtIBaAlrd473+BowBpw7AAtLwdO/bt/S9ot2F6upk8knqq8QlhNMR27Wo6gaQ+cgQgSYWyACSpUBaAJBXKApCkQlkAklQoC0CSCmUBSFKhLABJKpQFIEmFsgAkqVAWgCQVygKQpEJZAJJUKAtAkgplAUhSoSwASSpUGQXQasH4uHPZStIijRVARLw6Ir4WEV+OiL/p68YmJmBqyrlsJWmRRgogIs4AzgFOyszHAG/v28ZaLZicrCY3n5x0FCBJtaZGAK8E3paZvwDIzDv7tqWJierNH2BuzlGAJNWaKoATgNMj4oaI+HxEnLLcihFxYUTMRMTM7Ozs2raysPffblfL7bajAEmq9a0AIuKaiLi1w885wEHA4cBTgIuAj0ZEdHqdzNyamWOZObZ58+a1hVi897/AUYAkAdUbcV9k5lnLPRYRrwSuyMwEboyIeWATsMZd/FXs2LFv739Buw3T0z3djCSNor4VwCr+BXg6cF1EnAAcDNzV863s2tXzl5SkjaKpArgMuCwibgXawEvr0YAkaUAaKYDMbAN/3MS2JUmVMr4JLEnajwUgSYWyACSpUDFK514jYhb4dperb6IfnyzqH/P2l3n7a5TyjlJW6E3eh2fmfl+kGqkCWIuImMnMsaZzdMu8/WXe/hqlvKOUFfqb10NAklQoC0CSCrWRC2Br0wHWyLz9Zd7+GqW8o5QV+ph3w54DkCStbCOPACRJK7AAJKlQI10AEXFZRNxZX1RuuXWeFhG767mHPz/IfB2yrJg3Ii6qs+6u506Yi4hfGXTORXlWy/uQiPjXiLi5/vteMOiMS/KslvfwiLgyIr4UETdGxGMHnXFRlmMj4tqI2FP/7V7TYZ2IiHdFxG115pObyFpn6SbvoyJiR0T8IiJe10TORVm6yfui+u/6pYiYjojHN5G1ztJN3nPqrLvrSbJOW/eGM3Nkf4DfBk4Gbl3m8cOArwDH1csPHea8S9Z9DvC5Yc4LvAn46/r3zcAPgIOHOO8lwFvq3x8FfLbBrEcBJ9e/Hwp8HThxyTrPAv4NCKrJk24Y8rwPBU4B3gq8rqmsa8j7W8Dh9e/PHIG/7yHsO297EvDV9W53pEcAmbmd6k1nOX9ENfHM7fX6/Zt7uAtd5F3shcDlfYyzqi7yJnBoPZvbIfW69w4iW8cwq+c9Efhsve5XgS0RccQgsi2Vma3MvKn+/SfAHuDoJaudA3woK9cDh0XEUQOOCnSXNzPvzMwvAvc0EPE+usw7nZn/Uy9eDxwz2JT3ydJN3ruzfvcHHkT1/29dRroAunACcHhEXBcROyPiJU0H6kZE/DJwNrCt6SyreDfwaOC7wC3AazJzfuWnNOpm4FyAiHgS8HAa/E+/ICK2AE8Abljy0NHAdxYt38H+JTFwK+QdSl3mfTnVaKtxK+WNiD+IiK8CVwEvW++2NnoBHAQ8Efg94BnAm+sZyIbdc4D/zMxuRwtNeQawG3gY8JvAuyPiwc1GWtHbqHYIdgOvBnbR4IgFICIOoSr612bmj5c+3OEpjX5ue5W8Q6ebvBFxBlUBvGGQ2ZbJsmLezLwyMx8F/D6w7snNm5oRbFDuAO7KzJ8CP42I7cDjqY6vDbPzafjwT5cuAN5WD0tvi4hvUh1bv7HZWJ3V/6EugOoEK/DN+qcREfEAqv/sH8nMKzqscgdw7KLlY6hGW43oIu9Q6SZvRJwEvB94ZmZ+f5D5OmTp+u+bmdsj4tciYlNm3u8LxW30EcAngNMj4qD6sMqTqY6tDa2IeAgwTpV92N0OnAlQH0v/DeAbjSZaQUQcFhEH14uvALY3tRdbF9ClwJ7MfMcyq30SeEn9aaCnAD/KzNbAQi7SZd6h0U3eiDgOuAJ4cWY2ulPYZd7j6/WoPxF2MLCu0hrpbwJHxOXA06gul/o94C3AAwAy8331OhdR7fXNA+/PzL9tJCxd5/0T4OzMPL+ZlPusljciHgZ8gOoTDEE1GviHRsLSVd6nAh8C5qg+HfbyRScBB531NOALVOdOFs6bvAk4Dv4/b1CdZzkb+BlwQWbONBC327xHAjPAg+t17qb6JMvAS7bLvO8Hnse+S8zfmw1dJbTLvG8AXkJ1kv3nwEWZObWu7Y5yAUiS7r+NfghIkrQMC0CSCmUBSFKhLABJKpQFIEmFsgCkRSLi7nU+/+MR8cj6929FxLZFj50XER+of392RPzlusJK62QBSD0SEY8BDszMxV+GG6vvX+oq4Ln1FxSlRlgAUgf1t28viWpehlsi4gX1/QdExHvra7Z/KiKujojz6qe9iP2/wf12qi/03Ed9+YzrgGf38Z8hrcgCkDo7l+oCd48HzgIuqS/FfC6wBXgc1eUknrroOacCO5e8zkeBkyPi+A7bmAFO721sqXsWgNTZacDlmTmXmd8DPk812clpwMcycz4z9wLXLnrOUcDskteZo5qI5o0dtnEn1ZVUpUZYAFJnnS7FvNL9UF2f5YEd7v8w1Wxlxy25/4H1c6RGWABSZ9uBF0TEgRGxmeoN/EZgCnhefS7gCKqLzy3YA+x3qCcz7wHeCbx2yUMnAMvOZy31mwUgdXYl8CWqWcQ+B7y+PuSzjeo6/bcCf081a9OP6udcxX0LYbFL2X/+jTPq50iN8Gqg0hpFxCGZeXdE/CrVqODUzNwbEb9EdU7g1MycW+U1jgD+MTPPHEBkqSMLQFqjiLgOOIxqQo6/ycwPLHrsGVSTety+ymucAtyTmbv7GFVakQUgSYXyHIAkFcoCkKRCWQCSVCgLQJIKZQFIUqH+D9vTFnwEufvdAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "N_list = [5,6,7,8,9,10]\n",
    "Time_list = []\n",
    "\n",
    "for N in N_list:\n",
    "   c = generate_map(840, 480, N)\n",
    "\n",
    "   ti = time.perf_counter()\n",
    "   branch_bound(c)\n",
    "   ts = time.perf_counter()\n",
    "\n",
    "   print(\"Number of sites:\", N, \", Calculation time:\", ts - ti)\n",
    "   Time_list.append(math.log(ts - ti))\n",
    "\n",
    "#print N_list, time_list\n",
    "plt.xlabel('log(N)')\n",
    "plt.ylabel('log(T)')\n",
    "plt.plot(np.log(N_list), Time_list, 'r^')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Local Optimization Algorithm \"2-opt\"\n",
    "The local optimization algorithm **2-opt** allows us to improve the paths by deleting paths that cross each other. This is done by inversing the order of visiting these nodes.\n",
    "![2-opt algorithm](images/2opt.jpg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def two_opt(sites):\n",
    "    n = len(sites)\n",
    "    for i in range(n-3):\n",
    "        for j in range(i+2, n-1):\n",
    "            if (distance(sites, i, i+1) + distance(sites, j, j+1) > distance(sites, i, j) + distance(sites, i+1,j+1)):\n",
    "                L1=sites[:i+1]\n",
    "                L2=sites[i+1:j+1]\n",
    "                L2_inv=L2[::-1]\n",
    "                L3=sites[j+1:]\n",
    "                sites = L1 + L2_inv + L3\n",
    "    assert(n==len(sites)) # sanity check\n",
    "    return sites"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "For N: 5 , length of branch and bound: 1655 , length for two_opt: 1655\n",
      "For N: 6 , length of branch and bound: 1494 , length for two_opt: 1367\n",
      "For N: 7 , length of branch and bound: 1647 , length for two_opt: 1471\n",
      "For N: 8 , length of branch and bound: 2609 , length for two_opt: 1618\n",
      "For N: 9 , length of branch and bound: 3248 , length for two_opt: 2187\n",
      "For N: 10 , length of branch and bound: 2805 , length for two_opt: 2098\n",
      "For N: 11 , length of branch and bound: 4369 , length for two_opt: 2648\n"
     ]
    }
   ],
   "source": [
    "N_list = [5,6,7,8,9,10]\n",
    "for N in N_list:\n",
    "    c = generate_map(840, 480, N)\n",
    "    bb_length = total_distance(branch_bound(c))\n",
    "    to_length = total_distance(two_opt(c))\n",
    "    print(\"For N:\", N, \", length of branch and bound:\", bb_length, \", length for two_opt:\", to_length)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Nombre de sites: 5 , temps de calcul: 2.5899999968714837e-05\n",
      "Nombre de sites: 6 , temps de calcul: 4.8800000001847366e-05\n",
      "Nombre de sites: 7 , temps de calcul: 7.130000000188375e-05\n",
      "Nombre de sites: 8 , temps de calcul: 9.190000002945453e-05\n",
      "Nombre de sites: 9 , temps de calcul: 0.00012010000000373111\n",
      "Nombre de sites: 10 , temps de calcul: 0.0001527000000010048\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZcAAAEGCAYAAACpXNjrAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAaE0lEQVR4nO3de7hddX3n8fcHEWsrCEq4Y6MVtKiF2iOVsR1EURRbg1xsmD5qvQzTkc5UOzJKq7Vtap96aRl9ihcKRmwdbygDCmpFqTGTKD1puAQBzUhb05zI8V7b6tHkO3+sdWBz2OeSZO1Lwvv1PPvZa/0ue3/PeSCf81tr7bVTVUiS1KV9Rl2AJGnvY7hIkjpnuEiSOme4SJI6Z7hIkjq376gLGAcHH3xwLV++fNRlSNIeZcOGDd+oqmX9+gwXYPny5UxOTo66DEnaoyT5x/n6PCwmSerc2IVLkhOSfCHJjUkmk5zYZ8wpbf/s4wdJzmj73pPkzp6+E4b/U0jS/ds4HhZ7E/CHVfWJJKe3+0/tHVBV1wMnACR5GLAZ+JueIRdU1RXDKVeSNNfYrVyAAg5otx8KbF1k/NnAJ6rq3wZalSRpycYxXF4BvDnJ14C3ABcuMn4l8P45bW9IcnOSi5I8qN+kJOe1h90mp6end79qSdLdRhIuSa5LsqnPYwXwX4FXVtXRwCuByxZ4ncOBJwCf6mm+EHgs8CTgYcCr+82tqkuqaqKqJpYt63slnSTt3aam4OSTYdu2zl96JOFSVadW1eP7PK4CXgR8tB36YeA+J/R7PB+4sqp+1PPaU9X4IbB6kfmSdP+1ahWsXds8d2wcD4ttBU5ut58GfGWBsecy55BYu5ohSYAzgE0DqFGS9mxTU7B6NezY0Tx3vHoZx3D5z8CfJbkJ+BPgPIAkE0kunR2UZDlwNPC5OfPfl+QW4BbgYOCPh1CzJO1ZVq1qggVg+/bOVy/xy8JgYmKi/IS+pPuNqSl41KPgBz+4p+3BD4avfhUOO2zJL5NkQ1VN9Osbx5WLJGmQelctszpevRguknR/s349zMzcu21mBtat6+wtxvET+pKkQdq4ceBv4cpFktQ5w0WS1DnDRZLUOcNFktQ5w0WS1DnDRZLUOcNFktQ5w0WS1DnDRZLUOcNFktQ5w0WS1DnDRZLUOcNFktQ5w0WS1DnDRZLUOcNFktS5sQuXJMcnWZ/kliQfS3LAPOOeleSOJJuTvKan/ZFJvpjkK0k+mGS/4VUvSYIxDBfgUuA1VfUE4ErggrkDkjwAuBh4NnAccG6S49ruNwIXVdUxwLeBlw6laknS3cYxXB4DrGm3Pw2c1WfMicDmqvpqVc0AHwBWJAnwNOCKdtzlwBkDrleSNMc4hssm4Lnt9jnA0X3GHAl8rWd/S9v2cOA7VfXjOe33keS8JJNJJqenpzspXNL91NQUnHwybNs26krGxkjCJcl1STb1eawAXgKcn2QDsD8w0+8l+rTVAu33bay6pKomqmpi2bJlu/qjSBKsWgVr1zbPAmDfUbxpVZ26yJBnAiQ5FnhOn/4t3HtFcxSwFfgGcGCSfdvVy2y7JA3G1BSsXg07djTPr3sdHHbYqKsaubE7LJbkkPZ5H+C1wDv7DPs74Jj2yrD9gJXA1VVVwPXA2e24FwFXDb5qSfdbq1Y1wQKwfburl9bYhQvNlV9fBm6nWXWsBkhyRJJrAdpVyW8BnwJuAz5UVbe2818N/E6SzTTnYC4bcv2S7i9mVy0z7dH7mZlm33MvpPlj//5tYmKiJicnR12GpD3Ny18Ol112T7gA7LcfvOxlcPHFo6trSJJsqKqJfn3juHKRpD3D+vX3DhZo9tetG009Y2QkJ/Qlaa+wceOoKxhbrlwkSZ0zXCRJnTNcJEmdM1wkSZ0zXCRJnTNcJEmdM1wkSZ0zXCRJnTNcJEmdM1wkSZ0zXCRJnTNcJEmdM1wkSZ0zXCRJnTNcJEmdM1wkSZ0zXCRJnRu7cElyfJL1SW5J8rEkB/QZc3SS65PcluTWJL/d0/cHSf45yY3t4/Th/gSSpLELF+BS4DVV9QTgSuCCPmN+DPyPqvpZ4MnA+UmO6+m/qKpOaB/XDr5kSVKvcQyXxwBr2u1PA2fNHVBVU1X19+32vwC3AUcOrUJJ0oLGMVw2Ac9tt88Bjl5ocJLlwM8DX+xp/q0kNyd5d5KD5pl3XpLJJJPT09O7X7Uk6W4jCZck1yXZ1OexAngJzWGuDcD+wMwCr/MQ4CPAK6rqe23zO4CfAU4ApoA/6ze3qi6pqomqmli2bFmHP50kad9RvGlVnbrIkGcCJDkWeE6/AUkeSBMs76uqj/a89td7xvwl8PHdLlhSt6amYOVK+OAH4bDDRl2NBmDsDoslOaR93gd4LfDOPmMCXAbcVlV/Pqfv8J7d59EcZpM0TlatgrVrm2ftlcYuXIBzk3wZuB3YCqwGSHJEktkrv54CvAB4Wp9Ljt/UXsZ8M3AK8Moh1y9pIVNTsHo17NjRPG/bNuqKNAAjOSy2kKp6K/DWPu1bgdPb7bVA5pn/goEWKGn3rFrVBAvA9u3N/sUXj7YmdW4cVy6S9lazq5aZ9jqdmRlXL3spw0XS8PSuWmbNrl60VzFcJA3P+vX3rFpmzczAunWjqUcDM3bnXCTtxTZuHHUFGhJXLpKkzhkukqTOGS6SpM4ZLpKkzhkukqTOGS6SpM4ZLpKkzhkukqTOGS6SpM4ZLpKkzhkukqTOGS6SpM4ZLpKkzhkukqTOGS6SpM6NXbgkOT7J+iS3JPlYkgPmGfcP7Zgbk0z2tD8syaeTfKV9Pmh41UuSYAzDBbgUeE1VPQG4ErhggbGnVNUJVTXR0/Ya4DNVdQzwmXZfkjRE4xgujwHWtNufBs7ayfkrgMvb7cuBMzqqS5K0ROMYLpuA57bb5wBHzzOugL9JsiHJeT3th1bVFED7fEi/yUnOSzKZZHJ6erqj0iVJAPuO4k2TXAcc1qfr94CXAG9L8vvA1cDMPC/zlKramuQQ4NNJbq+qNfOMvY+qugS4BGBiYqJ26geQJC1oJOFSVacuMuSZAEmOBZ4zz2tsbZ/vSnIlcCLN4bSvJzm8qqaSHA7c1V3l0gBNTcHKlfDBD8Jh/f72kvYcY3dYrF2JkGQf4LXAO/uM+akk+89u04TRprb7auBF7faLgKsGXbPUiVWrYO3a5lnaw41duADnJvkycDuwFVgNkOSIJNe2Yw4F1ia5CbgBuKaqPtn2/SnwjCRfAZ7R7kvjbWoKVq+GHTua523bRl2RtFtGclhsIVX1VuCtfdq3Aqe3218Fjp9n/jeBpw+yRqlzq1Y1wQKwfXuzf/HFo61J2g3juHKR7l9mVy0z7bUrMzOuXrTHW3K4JDkoyeOSPKo9HyKpC72rllmzqxdpD7XgYbEkDwXOB84F9gOmgZ8ADk3yBeDtVXX9wKuU9mbr19+zapk1MwPr1o2mHqkDi51zuQJ4L/DLVfWd3o4kvwC8IMmjquqyQRUo7fU2bhx1BVLnFguXl1XVP/brqKoNwIbuS5Ik7ekWO3dy5VCqkCTtVRYLlwylCknSXmWxw2JHJnnbfJ1V9d87rkeStBdYLFz+Hc+rSJJ20mLh8s2qunyRMZIk3cti51zmu929JEnzWixcVi7UmcZRHdYjSdoLLHZY7M3trV6uojn3MvsJ/UcDp9DcIPL1wJZBFilJ2rMsGC5VdU6S44Bfp/mGyMNpTvLfBlwDvKGqfjDwKiVJe5RFb7lfVV+i+fphSZKWZEnf55LkzD7N3wVuqSq/RliSdC9L/bKwlwInAbN3QH4q8AXg2CR/VFV/NYDaJEl7qKWGyw7gZ6vq6wBJDgXeAfwisAYwXCRJd1vql34tnw2W1l3AsVX1LeBHXRaU5Pgk65PckuRjSQ7oM+YxSW7seXwvySvavj9I8s89fad3WZ8kaXFLXbl8PsnHgQ+3+2cDa5L8FPCd+aftkkuBV1XV55K8BLgAeF3vgKq6AzgBIMkDgH/m3ndwvqiq3tJxXZKkJVrqyuV8YDXNP+g/D1wOnF9V/1pVp3Rc02NoDrUBfBo4a5HxTwf+33zfOyNJGr4lhUtVFbAW+CxwHbCmbRuETcBz2+1zgKMXGb8SeP+ctt9KcnOSdyc5qOsCJUkLW1K4JHk+cAPN4bDnA19McvauvmmS65Js6vNYQfNhzfOTbAD2Z4H7myXZjyaIPtzT/A7gZ2hWWVPAn80z97wkk0kmp6end/VHkST1kaUsQJLcBDxj9jMtSZYB11XV8QMtLjkW+OuqOnGe/hU0h+eeOU//cuDjVfX4hd5nYmKiJicnd7NaSbp/SbKhqib69S31nMs+cz4s+c2dmLtTkhzSPu8DvBZ45wLDz2XOIbEkh/fsPo/mMJskaYiWGhCfTPKpJL+R5Ddo7it27YBqOjfJl4Hbga00FxKQ5Igkd79nkp8EngF8dM78N7WXMd9Mc3PNVw6oTknSPJZ0WAwgyVnAU4DQnNC/cpEpewwPi0nSzlvosNhSP+dCVX0E+EhnVUmS9loLhkuSfwH6LW1Cc4XyfT49L0nSYt/nsv+wCpEk7T0GcsWXJOn+zXCRJHXOcJEkdc5wkSR1znCRJHXOcJEkdc5wkSR1znCRJHXOcNHoTE3BySfDtm2jrkRSxwwXjc6qVbB2bfMsaa9iuGg0pqZg9WrYsaN5dvUi7VUMF43GqlVNsABs3+7qRdrLGC4avtlVy8xMsz8z4+pF2ssYLhq+3lXLLFcv0l7FcNHwrV9/z6pl1swMrFs3mnokdW7J30QpdWbjxlFXIGnARrZySXJOkluT7EgyMafvwiSbk9yR5LR55j8yyReTfCXJB5Ps17Y/qN3f3PYvH/xPI0nqNcrDYpuAM4E1vY1JjgNWAo8DngW8PckD+sx/I3BRVR0DfBt4adv+UuDbVfVo4KJ2nCRpiEYWLlV1W1Xd0adrBfCBqvphVd0JbAZO7B2QJMDTgCvapsuBM3rmX95uXwE8vR0vSRqScTyhfyTwtZ79LW1br4cD36mqH/cZc/f8tv+77fh7SXJekskkk9PT0x2WL0ka6An9JNcBh/Xp+r2qumq+aX3aaifGLGU+VXUJcAnAxMTEffolSbtuoOFSVafuwrQtwNE9+0cBW+eM+QZwYJJ929VJ75jZ+VuS7As8FPjWLtQhSdpF43hY7GpgZXvV1yOBY4AbegdUVQHXA2e3TS8CruqZ/6J2+2zgs+14SdKQjPJS5Ocl2QKcBFyT5FMAVXUr8CHgS8AngfOrans759okR7Qv8Wrgd5Jspjmnclnbfhnw8Lb9d4DXDOtnkiQ14h/1zTmXycnJUZchSXuUJBuqaqJf3zgeFpMk7eEMF0lS5wwXSVLnDBdJUucMF0lS5wwXSVLnDBdJUucMF0lS5wwXSVLnDBdJUucMF0lS5wwXSVLnDBdJUucMF0lS5wwXSVLnDBdJUucMF0lS5wwXSVLnDBdJUudGEi5Jzklya5IdSSbm9F2YZHOSO5KcNs/897X9m5K8O8kD2/anJvlukhvbx+8P4+eRJN3bqFYum4AzgTW9jUmOA1YCjwOeBbw9yQP6zH8f8FjgCcCDgZf19H2+qk5oH380iOIlSQsbSbhU1W1VdUefrhXAB6rqh1V1J7AZOLHP/GurBdwAHDXYiiVJO2PczrkcCXytZ39L29ZXezjsBcAne5pPSnJTkk8kedwCc89LMplkcnp6enfrliT12HdQL5zkOuCwPl2/V1VXzTetT1st8DZvB9ZU1efb/b8Hfrqqvp/kdOD/AMf0m1hVlwCXAExMTCz0HpKknTSwcKmqU3dh2hbg6J79o4Ct/QYmeT2wDPgvPe/5vZ7ta5O8PcnBVfWNXahFkrSLxu2w2NXAyiQPSvJImlXHDXMHJXkZcBpwblXt6Gk/LEna7RNpfr5vDqVySdLdRnUp8vOSbAFOAq5J8imAqroV+BDwJZrzKOdX1fZ2zrVJjmhf4p3AocD6OZccnw1sSnIT8DZgZXvSX5I0RPHf3uacy+Tk5KjLkKQ9SpINVTXRr2/cDotJkvYChoskqXOGiySpc4aLJKlzhoskqXOGiySpc4aLJKlzhoskqXOGiySpc4aLJKlzhoskqXOGiySpc4aLJKlzhoskqXOGiySpc4aLJKlzhoskqXOGiySpc4aLJKlzIwmXJOckuTXJjiQTc/ouTLI5yR1JTptn/nuS3JnkxvZxQtueJG9r59+c5InD+HkkSfe274jedxNwJvCu3sYkxwErgccBRwDXJTm2qrb3eY0LquqKOW3PBo5pH78IvKN9liQN0UhWLlV1W1Xd0adrBfCBqvphVd0JbAZO3ImXXgG8txpfAA5McngHJUuSdsK4nXM5Evhaz/6Wtq2fN7SHvi5K8qCdnZ/kvCSTSSanp6d3t25JUo+BhUuS65Js6vNYsdC0Pm3Vp+1C4LHAk4CHAa/eyflU1SVVNVFVE8uWLVugJEnSzhrYOZeqOnUXpm0Bju7ZPwrY2ue1p9rNHyZZDbxqZ+ZLkgZr3A6LXQ2sTPKgJI+kOTF/w9xBs+dRkgQ4g+YCgdn5L2yvGnsy8N2eIJIkDcmoLkV+XpItwEnANUk+BVBVtwIfAr4EfBI4f/ZKsSTXJjmifYn3JbkFuAU4GPjjtv1a4Ks0FwL8JfDygf4gU1Nw8smwbdtA30aS9jSp6ntK4n5lYmKiJicnd37iy18O73oX/OZvwsUXd1+YJI2xJBuqaqJf37gdFttzTE3B6tWwY0fz7OpFku5muOyqVauaYAHYvr3ZlyQBhsuumV21zMw0+zMzrl4kqYfhsit6Vy2zXL1I0t0Ml12xfv09q5ZZMzOwbt1o6pGkMTOqG1fu2TZuHHUFkjTWXLlIkjpnuEiSOme4SJI6Z7hIkjpnuEiSOue9xYAk08A/LnH4wcA3BlhO16x3sKx3sKx3sHa33p+uqr5fiGW47KQkk/PdqG0cWe9gWe9gWe9gDbJeD4tJkjpnuEiSOme47LxLRl3ATrLewbLewbLewRpYvZ5zkSR1zpWLJKlzhoskqXOGSx9J3p3kriSbFhjz1CQ3Jrk1yeeGWV+fWhasN8kFba03JtmUZHuShw27zp56Fqv3oUk+luSm9vf74mHXOKeexeo9KMmVSW5OckOSxw+7xjn1HJ3k+iS3tb+/3+4zJknelmRzW/cTR1FrW8tS6n1skvVJfpjkVaOos61jKbX+evs7vTnJuiTHj6LWtpal1LuirfXGJJNJfqmTN68qH3MewH8Enghsmqf/QOBLwCPa/UPGud45Y38V+Ow41wv8LvDGdnsZ8C1gvzGu983A69vtxwKfGfHv93Dgie32/sCXgePmjDkd+AQQ4MnAF8e83kOAJwFvAF415rX+B+CgdvvZe8Dv9iHcc/7954Dbu3hvVy59VNUamn/Q5vOfgI9W1T+14+8aSmHzWEK9vc4F3j/Acha1hHoL2D9JaP7D/xbw42HU1reYxes9DvhMO/Z2YHmSQ4dRWz9VNVVVf99u/wtwG3DknGErgPdW4wvAgUkOH3KpwNLqraq7qurvgB+NoMTeOpZS67qq+na7+wXgqOFWea9allLv96tNFuCnaP7/222Gy645Fjgoyd8m2ZDkhaMuaCmS/CTwLOAjo65lEX8B/CywFbgF+O2q2rHwlJG6CTgTIMmJwE8zwn9QeiVZDvw88MU5XUcCX+vZ38J9A2joFqh37Cyx1pfSrBBHbqF6kzwvye3ANcBLung/w2XX7Av8AvAc4DTgdUmOHW1JS/KrwP+tqqWuckblNOBG4AjgBOAvkhww2pIW9Kc0f2zcCPw3YCMjXGnNSvIQmj8kXlFV35vb3WfKSD+XsEi9Y2UptSY5hSZcXj3M2uapZcF6q+rKqnoscAawqov39GuOd80W4BtV9a/AvyZZAxxPczxznK1kxIfElujFwJ+2S/XNSe6kOZdxw2jL6q/9n/XF0JwoB+5sHyOT5IE0/5i8r6o+2mfIFuDonv2jaFaKI7GEesfGUmpN8nPApcCzq+qbw6yvTy1L/t1W1ZokP5Pk4KrarRtwunLZNVcBv5xk3/ZQ0y/SHMscW0keCpxMU/u4+yfg6QDtuYvHAF8daUULSHJgkv3a3ZcBa0b5l3cbcJcBt1XVn88z7Grghe1VY08GvltVU0MrsscS6x0LS6k1ySOAjwIvqKqR/sG5xHof3Y6jvWpwP2C3A9FP6PeR5P3AU2luR/114PXAAwGq6p3tmAto/lrdAVxaVf9rJMWy5Hp/A3hWVa0cTZX3WKzeJEcA76G50iU0q5i/HkmxLKnek4D3AttpriJ8ac8J3aFrLyX9PM35qtlzVb8LPALurjk057aeBfwb8OKqmhxBuUut9zBgEjigHfN9mquehhriS6z1UuAs7vkajx/XiO6UvMR6Xw28kOZiiX8HLqiqtbv93oaLJKlrHhaTJHXOcJEkdc5wkSR1znCRJHXOcJEkdc5wkYYgyfd3c/4VSR7Vbv9Dko/09J2d5D3t9q8k+cPdKlbqgOEijbkkjwMeUFW9HySdaNvnugZ4bvvhXmlkDBdpiNpPxL85zffq3JLk19r2fZK8vf3OjY8nuTbJ2e20X+e+d1Z4C82H4e6lvWXO3wK/MsAfQ1qU4SIN15k0N+M8HjgVeHN7q/szgeXAE2huIXNSz5ynABvmvM6HgCcmeXSf95gEfrnbsqWdY7hIw/VLwPurantVfR34HM2XYP0S8OGq2lFV24Dre+YcDkzPeZ3tNF9SdmGf97iL5o7S0sgYLtJw9bvV/ULt0Nzv6Sf6tP8VzbdkPmJO+0+0c6SRMVyk4VoD/FqSByRZRhMONwBrgbPacy+H0twoc9ZtwH0Of1XVj4CLgFfM6ToW2DSA2qUlM1yk4boSuJnm2ys/C/zP9jDYR2i+Y2UT8C6abwv8bjvnGu4dNr0u477fy3RKO0caGe+KLI2JJA+pqu8neTjNauYpVbUtyYNpzsE8paq2L/IahwL/u6qePoSSpXkZLtKYSPK3wIE0X9b0pqp6T0/faTRf+PRPi7zGk4AfVdWNAyxVWpThIknqnOdcJEmdM1wkSZ0zXCRJnTNcJEmdM1wkSZ37/9uUPT65UQaBAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "N_list = [5,6,7,8,9,10]\n",
    "Time_list = []\n",
    "\n",
    "for N in N_list:\n",
    "   c = generate_map(840, 480, N)\n",
    "\n",
    "   ti = time.perf_counter()\n",
    "   two_opt(c)\n",
    "   ts = time.perf_counter()\n",
    "\n",
    "   print(\"Nombre de sites:\", N, \", temps de calcul:\", ts - ti)\n",
    "   Time_list.append(math.log(ts - ti))\n",
    "\n",
    "#print N_list, time_list\n",
    "plt.xlabel('log(N)')\n",
    "plt.ylabel('log(T)')\n",
    "plt.plot(np.log(N_list), Time_list, 'r^')\n",
    "plt.show()"
   ]
  },
  {
   "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}