Permalink
Name already in use
A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
TSP-Guidance/Investigating TSP.ipynb
Go to fileThis commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
948 lines (948 sloc)
95.3 KB
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "cells": [ | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "<h1><center>Guide Notebook for the 380CT Assignment on TSP</center></h1>" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "_Kamal Bentahar_\n", | |
| "\n", | |
| "[https://github.coventry.ac.uk/380CT-1920JANMAY/TSP-Guidance](https://github.coventry.ac.uk/380CT-1920JANMAY/TSP-Guidance)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "# Notation and definitions" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "Let $G$ be a complete weighted graph with $n$ vertices...\n", | |
| "\n", | |
| "- **Complete**: the graph is undirected, has no self-loops, and each node is connected to all the other vertices.\n", | |
| "- **Weighted**: the edges have a weight (a positive integer).\n", | |
| "- **Cycle**: a path that visits every vertex once, and goes back to the start point.\n", | |
| "- **Total cost of the cycle**: sum of the edge weights of the cycle." | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "# Definition of the problem" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "Given $G$ as above, the versions of the TSP are defined as follows:\n", | |
| "\n", | |
| "* **Decisional TSP (D-TSP)**:\n", | |
| "> Given a total cost $k$, decide if $G$ is has a cycle of length $\\leq k$.\n", | |
| "\n", | |
| " **NP-complete**, because D-TSP $\\in$ NP and D-TSP $\\leq_p$ HAMCYCLE.\n", | |
| " \n", | |
| " * D-TSP $\\in$ NP: once a cycle is given (a certificate) we can quickly evaluate the its cost in $O(n)$ time to verify it is equal to $k$.\n", | |
| " * D-TSP $\\leq_p$ HAMCYCLE: Reduction from HAMCYCLE (Hoos and Stutzler, p.25).\n", | |
| "\n", | |
| "* **Search TSP**:\n", | |
| "> Given a total cost $k$, search for a cycle of length $\\leq k$ in $G$.\n", | |
| "> (If found then return it, otherwise say that there is no such cycle.)\n", | |
| " \n", | |
| "* **Optimization TSP**:\n", | |
| "> Given $G$, find a cycle of minimal total cost.\n", | |
| "\n", | |
| " **NP-Hard**, because the optimization version of (decision) NP-complete problems are automatically NP-Hard. (using the same method sketched above for **Search TSP**)\n", | |
| "\n", | |
| "The facts about the complexity classes memberships can also be found in (Garey and Johnson, 1979) and (Hoos and Stutzler, 2005)." | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "# Testing methodology" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "* **Exact methods**:\n", | |
| " Average time for instances with increasing $n$.\n", | |
| "\n", | |
| "* **Greedy and meta-heuristics**:\n", | |
| " Average \"quality\" as $n$ increases.\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "## Random instances sampling strategy" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "General TSP instances will be generated by creating symmetric adjacency matrices uniformly at random." | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "# Code" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "First start by importing relevant libraries." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 2, | |
| "metadata": { | |
| "collapsed": true | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "from random import randint, choice\n", | |
| "from pprint import pprint\n", | |
| "from itertools import permutations\n", | |
| "from math import inf as oo # Infinity (∞) is larger than any number\n", | |
| "from math import sqrt\n", | |
| "from time import time\n", | |
| "import matplotlib.pyplot as plt\n", | |
| "import copy" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "## Basics" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "Let the set of vertices be $\\{0, 1, 2,\\ldots, n-1\\}$.\n", | |
| "\n", | |
| "Without loss of generality, we can consider $0$ to be the start and end point of cycles." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 9, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "MAX_DISTANCE = 100\n", | |
| "\n", | |
| "def random_symmetric_graph(n):\n", | |
| " ''' Symmetric adjacency matrix of size nxn '''\n", | |
| " dist_matrix = [[oo for _ in range(n)] for _ in range(n)]\n", | |
| " for i in range(n):\n", | |
| " for j in range(i+1,n):\n", | |
| " v = randint(1,MAX_DISTANCE)\n", | |
| " dist_matrix[i][j] = v\n", | |
| " dist_matrix[j][i] = v\n", | |
| " return dist_matrix\n", | |
| "\n", | |
| "def random_euclidean_graph(n):\n", | |
| " ''' Symmetric adjacency matrix of a Euclidean graph of size nxn '''\n", | |
| " dist_matrix = [[oo for _ in range(n)] for _ in range(n)]\n", | |
| " points = []\n", | |
| " for p in range(n):\n", | |
| " x,y = randint(0,MAX_DISTANCE), randint(0,MAX_DISTANCE)\n", | |
| " points.append((x,y))\n", | |
| " for i in range(n):\n", | |
| " p1 = points[i]\n", | |
| " for j in range(i+1,n):\n", | |
| " p2 = points[j]\n", | |
| " distance = sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)\n", | |
| " dist_matrix[i][j] = distance\n", | |
| " dist_matrix[j][i] = distance\n", | |
| " return dist_matrix\n", | |
| "\n", | |
| "def show(G):\n", | |
| " ''' Show adjacency matrix. Useful for debugging. '''\n", | |
| " n = len(G)\n", | |
| " r = \" \"\n", | |
| " for i in range(n):\n", | |
| " r += f'{i:4}'\n", | |
| " r += '\\n -'+'-'*(4*n)+'\\n'\n", | |
| " for i in range(n):\n", | |
| " r += f'{i:2} | '\n", | |
| " for j in range(n):\n", | |
| " r += f'{G[i][j]:4}'\n", | |
| " r += '\\n'\n", | |
| " r = r.replace('inf', ' ∞')\n", | |
| " print(r)\n", | |
| "\n", | |
| "def cost(G, cycle):\n", | |
| " ''' Calculate the cost of the given cycle '''\n", | |
| " c = 0\n", | |
| " n = len(G)\n", | |
| " for i in range(n):\n", | |
| " a = cycle[i]\n", | |
| " b = cycle[(i+1)%n]\n", | |
| " c += G[a][b]\n", | |
| " return c" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 11, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| " 0 1 2 3 4\n", | |
| " ---------------------\n", | |
| " 0 | ∞63.19810123729984524.04163056034261545.011109739707630.0\n", | |
| " 1 | 63.198101237299845 ∞50.9901951359278518.97366596101027653.53503525729669\n", | |
| " 2 | 24.04163056034261550.99019513592785 ∞32.24903099319427.0710678118654755\n", | |
| " 3 | 45.011109739707618.97366596101027632.2490309931942 ∞35.4682957019364\n", | |
| " 4 | 30.053.535035257296697.071067811865475535.4682957019364 ∞\n", | |
| "\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "G=random_euclidean_graph(5)\n", | |
| "show(G)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Example" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 12, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| " 0 1 2 3 4\n", | |
| " ---------------------\n", | |
| " 0 | ∞ 12 19 68 74\n", | |
| " 1 | 12 ∞ 91 29 6\n", | |
| " 2 | 19 91 ∞ 50 55\n", | |
| " 3 | 68 29 50 ∞ 88\n", | |
| " 4 | 74 6 55 88 ∞\n", | |
| "\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "G=random_symmetric_graph(5)\n", | |
| "show(G)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "# Solution methods" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "## Exact methods - Exhaustive search" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "The idea is to:\n", | |
| "- Consider vertex $0$ as the start and end point.\n", | |
| "- Iterate over all permutations of the vertices $\\{1,2,\\ldots, n-1\\}$.\n", | |
| " - Calculate cost of each permutation and keep track of minimum cost permutation.\n", | |
| "- Return the cycle with minimum cost.\n", | |
| "\n", | |
| "More formally, the pseudo-code is as follows:\n", | |
| "\n", | |
| "**Input**: $G$.\n", | |
| "\n", | |
| "**Output**: a cycle in $G$ of shortest cost." | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "1. $bestcycle\\gets \\emptyset$\n", | |
| "2. $bestcost\\gets \\infty$\n", | |
| "3. **for all** possible cycles $p$ in $G$ (starting and ending at $0$) **do**\n", | |
| "4. $\\quad$ $c\\gets$ cost of $p$\n", | |
| "2. $\\quad$ **if** $c<bestcost$ **then**\n", | |
| "3. $\\qquad$ $bestcycle\\gets p$\n", | |
| "3. $\\qquad$ $bestcost\\gets c$\n", | |
| "4. $\\quad$ **end if**\n", | |
| "5. **end for**\n", | |
| "6. **return** $bestcycle, bestcost$" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "There are $(n-1)!$ possible cycles, and each computation of a cycle's cost costs $O(n)$. So this algorithm costs $$O((n-1)!\\cdot n)=O(n!).$$" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 13, | |
| "metadata": { | |
| "collapsed": true | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def exhaustive_search(G):\n", | |
| " n = len(G) \n", | |
| " best_cost = oo # infinity\n", | |
| " best_cycle = []\n", | |
| " for cycle in permutations(range(1,n)): # permutations of [1,2,...,n-1]\n", | |
| " cycle=[0]+list(cycle) # add the starting city: 0\n", | |
| " c = cost(G, cycle)\n", | |
| " if c < best_cost:\n", | |
| " best_cost = c\n", | |
| " best_cycle = cycle\n", | |
| " return (best_cycle, best_cost)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "## Testing exhaustive search time cost" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "Test completely random graphs:" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 5, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "8\t0.02001166343688965\n", | |
| "9\t0.12252664566040039\n", | |
| "10\t1.4062316417694092\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "pnts_n = []\n", | |
| "pnts_t = []\n", | |
| "\n", | |
| "n = 8\n", | |
| "t0 = t1 = 0\n", | |
| "\n", | |
| "while t1-t0<1: # in seconds; if it takes too long then stop testing\n", | |
| " G = random_symmetric_graph(n)\n", | |
| " t0 = time()\n", | |
| " exhaustive_search(G)\n", | |
| " t1 = time()\n", | |
| " # record time\n", | |
| " print( f\"{n}\\t{t1-t0}\" )\n", | |
| " pnts_n.append( n )\n", | |
| " pnts_t.append( t1-t0 )\n", | |
| " n += 1" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "Let us plot this data to see it visually." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 6, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD4CAYAAAD8Zh1EAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjAsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+17YcXAAAgAElEQVR4nO3deZhU1bnv8e8rigJxQGgCARk0mIgeErU1GqNiNBG9CmpMZDIOaD9yHSIOR45cPQaDE07XiNEOGsV0xAFjMEEEEcNVj0MbDyJyiX1RBAFpQVGCKMN7/1jVUlRXd1XTu2rX8Ps8Tz9Vtfeuqh+7Ny+btdZe29wdEREpfjvEHUBERKKhgi4iUiJU0EVESoQKuohIiVBBFxEpETvG9cWdO3f23r17x/X1IiJF6Y033vjY3SvSrYutoPfu3Zva2tq4vl5EpCiZ2ZKm1qnJRUSkRKigi4iUCBV0EZESoYIuIlIiVNBFREqECrqISL7U1EDv3rDDDuGxpibSj89Y0M3sATNbZWZvZ9juEDPbbGanRxdPRKRE1NRAVRUsWQLu4bGqKtKins0Z+oPAwOY2MLM2wM3AsxFkEhEpPWPHwvr12y5bvz4sj0jGgu7uc4E1GTa7GJgKrIoilIhIyfngg5Yt3w6tbkM3s+7AqcC9WWxbZWa1ZlZbX1/f2q8WESkeFWmv1oeePSP7iig6Re8ErnL3zZk2dPdqd69098qKpv5wIiKl5t13Yd06MNt2efv2MH58ZF8TRUGvBKaY2fvA6cA9ZnZKBJ8rIlL8Pv0UTj4Z2rWD226DXr1CYe/VC6qrYfjwyL6q1ZNzuXufhudm9iDwV3d/qrWfKyJS9DZtgjPOgMWL4bnn4KijYPTonH1dxoJuZo8AA4DOZrYM+E9gJwB3z9huLiJSti6/HGbOhEmTQjHPsYwF3d2HZvth7n52q9KIiJSK6mq4665wRj5yZF6+UleKiohEbc4cuPBCGDgQJkzI29eqoIuIRKmuDk4/Hfr2hSlToE2bvH21CrqISFTWroVBg8Lzp5+G3XfP69fHdgs6EZGSsnkzDBkSxpzPmgX77JP3CCroIiJRuPJKmDED7rsPBgyIJYKaXEREWuv+++GOO+CSS8IMijFRQRcRaY25c2HUKPjpT8OVoDFSQRcR2V6LF8Npp8Hee8Ojj8KO8bZiq6CLiGyPzz4Lc7Rs2RJGtOyxR9yJ1CkqItJimzfDsGGwaFG4tL9v37gTASroIiItN2YM/O1vcM898OMfx53ma2pyERFpiQcfhFtvDZf2jxoVd5ptqKCLiGTrxRfDsMRjjw3DFAuMCrqISDbefx9OPRV694bHH4eddoo7USMq6CIimXz+eZijZdOmMKKlY8e4E6WlTlERkeZs2QIjRsA778Azz8B3vhN3oiapoIuINOfqq2HaNPjtb+EnP4k7TbPU5CIi0pTJk+Hmm+GCC8KolgKngi4iks7LL8P558Mxx4RbyZnFnSijjAXdzB4ws1Vm9nYT64eb2VuJn5fN7HvRxxQRyaMlS8KIlr32KtgRLelkc4b+IDCwmfXvAUe7e3/geqA6glwiIvFYtw4GD4YNG8KIlk6d4k6UtYydou4+18x6N7P+5aSXrwA9Wh9LRCQGW7bAmWfC/Pnh0v799os7UYtEPcplJPBMxJ8pIpIf11wDTz0Fd94JA5trmChMkRV0MzuGUNB/1Mw2VUAVQM+ePaP6ahGR1qupgRtuCB2hl1wSd5rtEskoFzPrD0wCBrv76qa2c/dqd69098qKiooovlpEpPVefRVGjoSjj4a77y6KES3ptLqgm1lP4EngTHf/Z+sjiYjk0dKloRO0e3d44glo2zbuRNstY5OLmT0CDAA6m9ky4D+BnQDc/V7gWqATcI+Ff9U2uXtlrgKLiETmX/8KxXz9epg9Gzp3jjtRq2QzymVohvXnAedFlkhEJB+2bIGzzoJ588LwxP33jztRq2kuFxEpT9ddB1Onwm23wYknxp0mErr0X0TKz5QpcP31cO65MHp03Gkio4IuIuXltdfgnHPgRz8K9wQt0hEt6aigi0j5+PBDOOUU6NoVnnwSdt457kSRUhu6iJSH9evDiJbPP4eZM6EEr4VRQReR0ucemln+8Y9ws4oDDog7UU6ooItI6Rs3Dh57DG65BU46Ke40OaM2dBEpbY8/HoYo/vKXcMUVcafJKRV0ESldb7wRLh764Q+hurqkRrSko4IuIqVpxYrQCVpRAX/+c8mNaElHbegiUnq++CIU808/DfcG7dIl7kR5oYIuIqXFPVwBWlsbzsz79487Ud6ooItIaRk/Plzaf+ON4Sy9jKgNXURKx9Sp4TZyI0bAVVfFnSbvVNBFpDS8+WYYmnjYYfD735f8iJZ0VNBFpPitXAmDBkGnTqHdfJdd4k4UC7Whi0hx27AhTLi1Zg289FKYeKtMqaCLSPFyh/POCzd5njoVvv/9uBPFSk0uIlK8broJamrgN7+B006LO03sVNBFpDg99RRcfTUMHRoeJXNBN7MHzGyVmb3dxHozs7vMrM7M3jKzg6KPKSKSZN68MDTxkEPg/vvLckRLOtmcoT8IDGxm/QlA38RPFfC71scSEWnCRx+FES177AF/+Qu0axd3ooKRsaC7+1xgTTObDAYme/AKsIeZdYsqoIjI1778MrSV19eHG1V0U6lJFkUbendgadLrZYlljZhZlZnVmlltfX19BF8tImXDHaqqwmRbkyfDQWrdTRVFQU/XeOXpNnT3anevdPfKihK8n5+I5NCECaGQ//rXcPrpcacpSFEU9GXAXkmvewDLI/hcEZHg6adhzBj4xS/CXC2SVhQFfRrwy8Rol8OAte6+IoLPFRGB+fNh2DA4+GD4wx80oqUZGa8UNbNHgAFAZzNbBvwnsBOAu98LTAdOBOqA9cA5uQorImWmvj6MaNl11zDuvH37uBMVtIwF3d2HZljvwIWRJRIRga0jWlauhLlzoXvasRaSRHO5iEjhcYdRo+DFF8PNKg45JO5ERUGX/otI4bn99tBefs01cMYZcacpGiroIlJYpk+HK6+En/0Mrrsu7jRFRQVdRArHggUwZEiYBvehh2AHlaiW0N4SkcLw8cdw8snQoUO4rL9Dh7gTFR11iopI/L76KjSxLF8Of/879OgRd6KipIIuIvFyhwsvDEMTa2rgBz+IO1HRUpOLiMTrrrtg0qRwk4phw+JOU9RU0EUkPjNmwGWXwamnwvXXx52m6Kmgi0g8Fi4MY8z/7d/CLIoa0dJq2oMikn+rV4cRLe3ahREt3/hG3IlKgjpFRSS/Nm4M85kvXQovvAA9e8adqGSooItI/rjDxReHQj55Mhx+eNyJSoqaXEQkfyZOhPvug6uugjPPjDtNyVFBF5H8mDULLr00zG9+ww1xpylJKugiknuLFsHPfw79+sEf/6gRLTmivSoiubVmTRjR0rZtuDforrvGnahkqVNURHJn48ZwY+clS+D556FXr7gTlTQVdBHJndGjYfbscLOKI46IO03JU5OLiOTG734XRrVccQWcfXbcacpCVgXdzAaa2SIzqzOzMWnW9zSzOWb2ppm9ZWYnRh9VRIrG7NlhvPlJJ8FNN8WdpmxkLOhm1gaYCJwA9AOGmlm/lM3+F/CYux8IDAHuiTqoiBSJd98NI1q++90wHW6bNnEnKhvZnKEfCtS5+2J3/wqYAgxO2caB3RLPdweWRxdRRIrGp5+GES1t2oQRLbvtlvk9EplsOkW7A0uTXi8DUmegvw6YaWYXAx2A49J9kJlVAVUAPTV/g0hp2bQpzJ64eHFocunTJ+5EZSebM3RLs8xTXg8FHnT3HsCJwMNm1uiz3b3a3SvdvbKioqLlaUWkcF1+OcycGTpDjzwy7jRlKZuCvgzYK+l1Dxo3qYwEHgNw9/8CdgE6RxFQRIpAdXW489Do0TByZNxpylY2Bf11oK+Z9TGztoROz2kp23wAHAtgZvsRCnp9lEFFpEDNmRPuCXrCCTBhQtxpylrGgu7um4CLgGeBhYTRLAvMbJyZDUpsdjlwvpnNAx4Bznb31GYZESk1dXVhbvO+feGRRzSiJWZZXSnq7tOB6SnLrk16/g6gy8BEysnatWHmRAgjWnbfPd48okv/RWQ7bN4MQ4aEMeezZsE++8SdSFBBF5HtceWVMGNGuFnFgAFxp5EEzeUiIi1z//1wxx1wySVQVRV3Gkmigi4i2Zs7F0aNguOPh9tuizuNpFBBF5HsLF4Mp50Ge+8NU6bAjmqxLTQq6CKS2WefhTlatmwJI1r22CPuRJKG/okVkeZt3gzDhoX7gs6cGcacS0FSQReR5o0ZA3/7G9xzD/z4x3GnkWaoyUVEmvbgg3DrreHS/lGj4k4jGaigi0h6L74YhiUedxzceWfcaSQLKugi0tj778Opp4Y5zR97TCNaioQKuohs6/PPw4iWTZvCiJaOHeNOJFnSP7sistXmzTB8OCxcCM88A/vuG3ciaQEVdBHZauzYcFb+29/CT34SdxppITW5iEgweTLcfDNccEEY1SJFRwVdRODll+H888M487vuAkt3K2EpdCroIuVuyZIwoqVnT3j8cdhpp7gTyXZSQRcpZ+vWweDB8OWXoe18zz3jTiStoE5RkXK1ZQuceSbMnw/Tp8N3vxt3ImmlrM7QzWygmS0yszozG9PENr8ws3fMbIGZ/SnamCISuWuugaeegttvD/ObS9HLeIZuZm2AicBPgGXA62Y2LXFj6IZt+gL/ARzh7p+YWZdcBRaRCNTUwA03hI7QSy6JO41EJJsz9EOBOndf7O5fAVOAwSnbnA9MdPdPANx9VbQxRSQyr74KI0fC0UfD3XdrREsJyaagdweWJr1elliWbF9gXzN7ycxeMbOB6T7IzKrMrNbMauvr67cvsYhsv6VLQydo9+4wdSq0bRt3IolQNgU93T/fnvJ6R6AvMAAYCkwys0a3NHH3anevdPfKioqKlmYVkdb4179CMV+/Poxo6dQp7kQSsWwK+jJgr6TXPYDlabb5i7tvdPf3gEWEAi8ihWDLFjjrLJg3L9wPtF+/uBNJDmRT0F8H+ppZHzNrCwwBpqVs8xRwDICZdSY0wSyOMqiItMJ114UmlgkT4MQT404jOZKxoLv7JuAi4FlgIfCYuy8ws3FmNiix2bPAajN7B5gDXOnuq3MVWkRaYMoUuP56OPdcGD067jSSQ+ae2hyeH5WVlV5bWxvLd4uUjddeC6NZDjkEnntOnaAlwMzecPfKdOt06b9IqfrwQzjlFOjaVSNayoQu/RcpRevXhxEtn38OM2eCRpWVBRV0kVLjDuecA//4B0ybBgccEHciyRMVdJFSM25cuLHzLbfASSfFnUbySG3oIqXk8cfDEMWzzoIrrog7jeSZCrpIqXjjjVDIjzgC7rtPc7SUIRV0kVKwfDkMGgRdusCTT8LOO8edSGKgNnSRYvfFF2F44tq14d6gXTR7dblSQRcpZu7hCtDaWvjzn6F//7gTSYxU0EWK2fjx4dL+G28M486lrKkNXaRYTZ0abiN35plw1VVxp5ECoIIuUozefBN++Us47DCortaIFgFU0EWKz8qVYURLp07hJs+77BJ3IikQakMXKSYbNoQRLWvWwEsvwTe/GXciKSAq6CLFwh3OOy/c5HnqVPj+9+NOJAVGTS4ixeKmm6CmBn7zGzjttLjTSAFSQRcpBk89BVdfDcOGhUeRNFTQRQrdvHkwYgQceihMmqQRLdIkFXSRQvbRR2FES8eO4Sy9Xbu4E0kBU6eoSKH68svQVl5fDy++CN26xZ1IClxWZ+hmNtDMFplZnZmNaWa7083MzSztDUxFJEvuUFUVJtuaPBkOOijuRFIEMhZ0M2sDTAROAPoBQ82sX5rtdgUuAV6NOqRI2ZkwIRTyX/8aTj897jRSJLI5Qz8UqHP3xe7+FTAFSDcL0PXALcCGCPOJlJ+nn4YxY+CMM8JcLSJZyqagdweWJr1ellj2NTM7ENjL3f/a3AeZWZWZ1ZpZbX19fYvDipS8+fPD0MSDD4Y//EEjWqRFsino6Y4o/3ql2Q7AHcDlmT7I3avdvdLdKysqKrJPKVIO6uvDiJbddoO//EUjWqTFshnlsgzYK+l1D2B50utdgQOAFyycTXQFppnZIHevjSqoSElrGNGyciXMnQvf+lbciaQIZVPQXwf6mlkf4ENgCDCsYaW7rwU6N7w2sxeAK1TMRbLkDqNGhaGJU6bAIYfEnUiKVMYmF3ffBFwEPAssBB5z9wVmNs7MBuU6oEjJu/320F5+7bWhI1RkO5m7Z94qByorK722VifxUuamT4eTToKf/QwefRR20MXb0jwze8Pd017ro6NHJC4LFsCQIXDggfDQQyrm0mo6gkTi8PHHcPLJ0KFDGNHSvn3ciaQEaC4XkXz76qvQxLJ8Ofz979CjR9yJpESooIvkkztceGEYmlhTAz/4QdyJpISoyUUkn+66K8xpPnZsuCJUJEIq6CL5MmMGXHYZnHoqjBsXdxopQSroIvmwcGEYY96/Pzz8sEa0SE7oqBLJtdWrw4iWdu3CiJYOHeJOJCVKnaIiubRxY5jPfOlSeOEF6Nkz7kRSwlTQRXLFHS6+OBTyhx+Gww+PO5GUODW5iOTKxIlw333hZhUjRsSdRsqACrpILsyaBZdeCoMHw/jxcaeRMqGCLhK1RYvg5z+H/feHP/5RI1okb3SkiURpzZowoqVtW5g2Db7xjbgTSRlRp6hIVDZuhF/8ApYsgeefh1694k4kZUYFXSQql14Ks2fDgw/CEUfEnUbKkJpcRKJwzz3h58or4ayz4k4jZUoFXaS1Zs+GSy4Jdx668ca400gZU0EXaY133w0jWvbbD/70J2jTJu5EUsayKuhmNtDMFplZnZmNSbP+MjN7x8zeMrPZZqbeICl9n34aRrS0aRNGtOy6a9yJpMxlLOhm1gaYCJwA9AOGmlm/lM3eBCrdvT/wBHBL1EFFCsqmTWH2xMWL4cknoU+fuBOJZHWGfihQ5+6L3f0rYAowOHkDd5/j7usTL18BdE8tKW2XXw4zZ8K998KRR8adRgTIrqB3B5YmvV6WWNaUkcAz6VaYWZWZ1ZpZbX19ffYpRQpJdXW489Bll8G558adRuRr2RR0S7PM025oNgKoBCakW+/u1e5e6e6VFRUV2acUKRRz5oR7gp54ItyilkUpLNlcWLQM2CvpdQ9geepGZnYcMBY42t2/jCaeSAGpqwtzm++7LzzyiEa0SMHJ5gz9daCvmfUxs7bAEGBa8gZmdiBwHzDI3VdFH1MkZmvXwqBB4fm0abDbbvHmEUkj4xm6u28ys4uAZ4E2wAPuvsDMxgG17j6N0MTyDeBxMwP4wN0H5TC3SP5s2gRDhoQx57NmwT77xJ1IJK2s5nJx9+nA9JRl1yY9Py7iXCKF49//HWbMCJ2hAwbEnUakSbpSVKQ5998Pd9wBv/oVnH9+3GlEmqWCLtKUuXNh1Cg4/ni49da404hkpIIukqymBnr3DncZOuYY6NwZHn0UdtRM01L4VNBFGtTUQFVVuEGFO2zZAp98An/9a9zJRLKigi7lzT1MsrVwYbjyc/36bddv2ABjx8aTTaSF9P9IKU2bNsGqVbBiRfhZuXLbx4bnK1eGot2cDz7IT2aRVlJBl+Kybl36Ap1aqOvrw9l3qk6doGtX6NYNfvSj8NitW1g2ejR89FHj9/Tsmfs/l0gEVNAlflu2wMcfN1+gGx7XrWv8/p12CgW5a9fQoXn44VuLdsNjt27QpQvsvHPzOaqqtm12ad8exo+P/I8skgsq6JI7GzZkPpNesSKcFW/e3Pj9u+22tShXVm5boJMLdceOYVRKaw0fHh7Hjg3NLD17hmLesFykwKmgS8u4h5Efmc6kV6wInY2pdtghnCk3FOXvfS99oe7aNZwd59vw4SrgUrRU0CXYuDGcKWcq1CtXwpdpJtNs127rGfP++8OxxzY+k+7aFSoqNEuhSI6ooJcy98adiE01f3z8cfrP6Nx5a1H+znfSN3l07Rrup2npps4XkXxRQS9Gmzc37kRsqlCnjqsGaNt2a0Hee2844oimOxHbts3/n09EtosKeiH54ovmC3TD46pV6TsRd999azE+9ND0Z9INnYg6mxYpOSroueYOa9ZkN3Z67drG799hB/jmN7cW5QMPTF+ou3YN7dgiUrZU0LfXV1+FTsRsxk5v3Nj4/R06bC3G/fvDT3+avlB37qxORBHJigp6Mnf47LPsxk6vXp3+Myoqthbj/fZL3+TR0IkoIhKh4iroNTXbd9HH5s2h3TmbsdNffNH4/W3bbi3K3/42HHlk+kLdpUu4alFEJAbFU9AbpjZtGLWxZEm4g8yqVaEDsLlCvWpVuKw7VceOW4vxYYelP5Pu1g322EOdiCJS8MzTTWCUB5WVlV5bW5v9G3r3DkU8kzZttnYSNjXKo2H9Lrtsd34RkTiY2RvuXpluXVZn6GY2EPjfQBtgkrvflLJ+Z2AycDCwGjjD3d9vTehGmpvCdMaMbTsRo5jXQ0SkyGSsfGbWBpgInAD0A4aaWb+UzUYCn7j7t4E7gJujDtrkFKa9eoV7PvbvH9qwVcxFpExlU/0OBercfbG7fwVMAQanbDMYeCjx/AngWLOIG53Hj288WZOmNhUR+Vo2Bb07sDTp9bLEsrTbuPsmYC3QKfWDzKzKzGrNrLa+vr5lSYcPh+rqcEZuFh6rqzUznohIQjZt6OnOtFN7UrPZBnevBqohdIpm8d3b0tSmIiJNyuYMfRmwV9LrHsDyprYxsx2B3YE1UQQUEZHsZFPQXwf6mlkfM2sLDAGmpWwzDTgr8fx04HmPazykiEiZytjk4u6bzOwi4FnCsMUH3H2BmY0Dat19GnA/8LCZ1RHOzIfkMrSIiDSW1Th0d58OTE9Zdm3S8w3Az6ONJiIiLaFB2yIiJSK2S//NrB7I4lr+tDoDTdwzLVaFmgsKN5tytYxytUwp5url7hXpVsRW0FvDzGqbmssgToWaCwo3m3K1jHK1TLnlUpOLiEiJUEEXESkRxVrQq+MO0IRCzQWFm025Wka5WqaschVlG7qIiDRWrGfoIiKSQgVdRKREFFxBN7PRZrbAzN42s0fMbJeU9Tub2aNmVmdmr5pZ76R1/5FYvsjMjs9zrsvM7B0ze8vMZptZr6R1m83svxM/qfPg5DrX2WZWn/T95yWtO8vM3k38nNX403Oa646kTP80s0+T1uVyf/0qkWmBmV2aZr2Z2V2J4+gtMzsoaV0u91emXMMTed4ys5fN7HtJ6943s/mJ/dWC+zpGkmuAma1N+n1dm7RuYOLvYp2ZjclzriuTMr2dOKb2TKyLdH+Z2QNmtsrM3k5atqeZzUocK7PMrGMT7017TJnZwYmMdYnjMbv7S7h7wfwQ5lV/D2iXeP0YcHbKNv8TuDfxfAjwaOJ5P2AesDPQB/h/QJs85joGaJ94PqohV+L1uhj319nA3WneuyewOPHYMfG8Y75ypWx/MWGOoFzvrwOAt4H2hGkvngP6pmxzIvAMYUrow4BX87C/ssn1w4bvI9w97NWkde8DnWPaXwOAv6Z5b5vE38G9gbaJv5v98pUrZfuTCRMG5mR/AUcBBwFvJy27BRiTeD4GuDnN+5o8poDXgMMTx+EzwAnZZCm4M3TCL6idhWl429N4qt6m7o40GJji7l+6+3tAHeFuS3nJ5e5z3H194uUrhGmG8yHT/mrK8cAsd1/j7p8As4CBMeUaCjwS4Xc3ZT/gFXdf7+FGLH8HTk3ZZjAw2YNXgD3MrBu53V8Zc7n7y4nvhfwdX9nsr6Zkc6ezfOXK6fHl7nNpPF14cp16CDglzVvTHlOJ4203d/8vD9V9chPvb6SgCrq7fwjcCnwArADWuvvMlM2aujtSNndWymWuZCMJ/6o22MXCnZpeMbOsfjER5/pZ4r/qT5hZw9z2BbG/Ek1TfYDnkxbnZH8RzuqOMrNOZtaecDa+V8o2Te2XnO2vLHMlSz2+HJhpZm+YWVVEmVqS63Azm2dmz5jZ/ollBbG/EusHAlOTFudqfyX7pruvAEg8dkmzTXPH2rI0yzMqqIKeaGcaTPgL/i2gg5mNSN0szVu9meX5ytWw7QigEpiQtLinh8t8hwF3mtk+ecz1NNDb3fsT/mvacNZQEPuL0Gz2hLtvTlqWk/3l7gsJNzCfBcwgNANsSo2f7q3NLM9XrhDO7BhCQb8qafER7n4QoSnmQjM7Ko+5/kGYW+R7wG+BpxqipvvIPOZqcDLwkrsnn0HnZH9th8iPtYIq6MBxwHvuXu/uG4EnCW2HyZq6O1I2d1bKZS7M7DhgLDDI3b9sWO7uyxOPi4EXgAPzlcvdVydl+T1wcOJ57PsrYQgp/x3O4f7C3e9394Pc/SjCcfNuyiZN7Zdc7q9scmFm/YFJwGB3X5303ob9tQr4MxE2NWbK5e6fufu6xPPpwE5m1pkC2F8JzR1fke+vJB8lmk5IPK5Ks01zx1qPNMsza22HQJQ/wA+ABYQ2VyOcTV6css2FbNsp+lji+f5s2ym6mOg6RbPJdSChEyi106gjsHPieWfCgRdV51A2ubolPT+V0PYIoSPmvUS+jonne+YrV2K77xA6qCwf+yvxmV0Sjz2B/0tKxybwP9i2U/S1XO+vLHP1JPQL/TBleQdg16TnLwMD85ira8Pvj1AYP0jsux0Tfwf7sLVTdP985UqsazjZ65Dr/QX0ZttO0Qls2yl6S5r3NHlMEe4UdxhbO0VPzCpHVDs4wl/UrxO/oLeBhwkFehzhrBdgF+DxxMH9GrB30nvHEorqIrLsFY4w13PAR8B/J36mJZb/EJifOKDnAyPznOtGQnGdB8wBvpv03nMT+7EOOCefuRLbXAfclPK+XO+v/wO8k/j8YxPLLgAuSDw3YGLiOJoPVOZpf2XKNQn4JOn4qk0s3zvxnnmJ3/PYPOe6KOn4eoWkf3AIbdv/TOzLvOZKvD6bMFAi+X2R7y/C/wBWABsJZ9cjCf16swknJLPZWqgrgUmZjqnEdm8n9t3dJJ30NPejS/9FREpEobWhi4jIdlJBFxEpESroIiIlQgVdRKREqKCLiJQIFXQRkRKhgi4iUiL+PzsM6T8AAAAESURBVDitLtsUGvsKAAAAAElFTkSuQmCC\n", | |
| "text/plain": [ | |
| "<Figure size 432x288 with 1 Axes>" | |
| ] | |
| }, | |
| "metadata": { | |
| "needs_background": "light" | |
| }, | |
| "output_type": "display_data" | |
| } | |
| ], | |
| "source": [ | |
| "plt.plot(pnts_n, pnts_t, 'ro-')\n", | |
| "plt.show()" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "Let us see if the emperical times match the theoretical $O(n!)$ expectation.\n", | |
| "\n", | |
| "`pnts_t[i]` contains the time for `pnts_n[i]`, so we expect $\\text{pnts_t[i]} \\approx \\text{pnts_n[i]}!$.\n", | |
| "Hence, we must have\n", | |
| "\n", | |
| "$$\n", | |
| "\\frac{\\text{pnts_t[i]}}{\\text{pnts_t[i-1]}} \\approx \\frac{i!}{(i-1)!} = i.\n", | |
| "$$" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 7, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXAAAAD4CAYAAAD1jb0+AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjAsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+17YcXAAAgAElEQVR4nO3dd5hV1bnH8e9CkaY0QYpIEZSoKG1ERUS8JFeN144FUexYiIk1osQoUYI1MbEkYgMNYgFNjMaCBB0UAQeC0iwUKUoZQEA6M7PuH+8+OWeGGZiZU/Ypv8/zzDMze5/Dedlz+LFm7Xev7bz3iIhI5qkRdgEiIlI9CnARkQylABcRyVAKcBGRDKUAFxHJUHun8sWaNGni27Ztm8qXFBHJeDNmzFjjvW9adntKA7xt27YUFBSk8iVFRDKec25Jeds1hSIikqEU4CIiGUoBLiKSoRTgIiIZSgEuIpKhFOCS28aMgbZtoUYN+zxmTNgViVRaStsIRdLKmDEwaBBs2WLfL1li3wMMGBBeXSKVpBG45K6hQ6PhHbFli20XyQAKcMldS5dWbbtImlGAS+5q3bpq20XSjAJcctfpp++6rW5dGD489bWIVIMCXHLTl1/CqFFwyCE24nYO2rSBkSN1AlMyhrpQJPds2gTnngt16sCkSXDggWFXJFItCnDJLd7DNdfYCPz99xXektEU4JJb/vIXeOkluO8+6Ns37GpE4qI5cMkd06fDjTfCaafBHXeEXY1I3BTgkhvWrIF+/WzK5IUX7NJ5kQynKRTJfsXFcPHFsGoVTJkCjRuHXZFIQijAJfvddx+89x489RR07x52NSIJo98jJbu99x4MGwYDB8LVV4ddjUhCKcAley1dahfldOpk3SfOhV2RSEIpwCU77dgB559vn8eNs0vkRbKM5sAlO91yC0ybBuPHw6GHhl2NSFLscQTunHvOObfaOTcnZtt5zrm5zrkS51xecksUqaKXX4bHH4ebb4Zzzgm7GpGkqcwUyijglDLb5gDnAPmJLkgkLvPmwVVXQa9ecP/9YVcjklR7nELx3uc759qW2TYfwOmkkKSTTZvsYp169eCVV6BmzbArEkmqpM+BO+cGAYMAWmuhfEkW761N8Kuv4IMPoGXLsCsSSbqkd6F470d67/O893lNmzZN9stJrnriCZv7vu8+OOmksKsRSQm1EUrmmzrVTliefjrcfnvY1YikjAJcMlthIZx3HrRqBaNHa5EqySl7nAN3zo0F+gBNnHPLgbuBdcBjQFPgbefcLO/9ycksVGQXxcV2pWVhIXz6KTRqFHZFIilVmS6U/hXseiPBtYhUze9+BxMmwNNPQ9euYVcjknL6fVMy07vvwr33wmWXwZVXhl2NSCgU4JJ5liyxqZMjj7TuE12PIDlKAS6ZZft2O2lZVGTrnGiRKslhWsxKMsvNN8Nnn8Hrr0OHDmFXIxIqjcAlc7z0Ejz5JNx6K5x9dtjViIROAS6ZYe5cu1T+hBNgxIiwqxFJCwpwSX8//gjnngv77WeLVO2tmT8R0By4pDvvrU3wm29g4kRo0SLsikTShgJc0tuf/wyvvQYPPAB9+oRdjUha0RSKpK8pU+yE5Zlnwm23hV2NSNpRgEt6Wr3abkrcpg2MGqWLdUTKoSkUST/FxXDRRbB2rS1S1bBh2BWJpCUFuKSfe+6xE5bPPgtduoRdjUja0hSKpJd//cvuqnPFFfYhIhVSgEv6+PZbuPhiG3U//njY1YikPQW4pIfIIlUlJTBuHNSpE3ZFImlPc+CSHm68EQoK4O9/h/btw65GJCNoBC7h+9vf4K9/hV//2nq+RaRSFOASrtmzYdAgOPFEGD487GpEMooCXMKzcaMtUtWgAbz8shapEqki/YuRcHhvbYKLFsG//w3Nm4ddkUjGUYBLOB591G6J9tBD0Lt32NWIZCRNoUjqffKJnbA8+2y45ZawqxHJWApwSa3IIlVt28Lzz2uRKpE4aApFUqe4GPr3h3Xr7JL5Bg3CrkgkoynAJXV++1s7Yfn889C5c9jViGQ8TaFIarz1Fvz+93DVVXDZZWFXI5IVFOCSfIsXwyWXQNeu8NhjYVcjkjX2GODOueecc6udc3NitjV2zk1wzn0TfG6U3DIlY23bBv362dfjxkHt2uHWI5JFKjMCHwWcUmbbEGCi9/4QYGLwvciufvUrmDkTXngBDj447GpEQrF9OxQVJf7P3WOAe+/zgXVlNp8JjA6+Hg2cleC6JBuMHg0jR8KQIXD66WFXI5IymzfDBx/Yefs+fazhaurUxL9OdbtQmnnvVwB471c45w6o6IHOuUHAIIDWrVtX8+Uk43zxBVx7LZx0Etx7b9jViCTV+vXw8ceQn28fM2bYiLtGDejWDQYPhqZNE/+6SW8j9N6PBEYC5OXl+WS/nqSBDRtskapGjWDsWC1SJVln9WqYPNnC+qOPbLziPeyzD/ToYRca9+4NPXvCfvslr47q/sta5ZxrEYy+WwCrE1mUZLDIIlWLF8OHH0KzZmFXJBK3Zcuio+v8fPjyS9tep46F9LBhFtg9eqT2ZlLVDfA3gUuB+4PP/0hYRZLZ/vAHeP11eOQR6NUr7GpEqsx7WLjQRtaRwP72W9vXoIG9rS+/3AK7WzcbdYdljwHunBsL9AGaOOeWA3djwf2qc+5KYClwXjKLlAwxeTLcfrtNn9x0U9jViFRKSQnMm1d6hL1ihe1r2tSC+qab7PORR8Jee4Vbb6w9Brj3vn8Fu/omuBbJZCtXwgUXWKvgc89pkSpJW0VFMGtWNKwnT7bleQAOPNDOu/fubR8/+Ul6v5V1dkniV1Rki1StXw/vvQf164ddkch/bd9u98uOnHD85BPYtMn2degAZ50VDey2bdM7sMtSgEv87rrLTliOHm2/Y4qEaPNm67mOjLCnTrULggGOOMJWdYgEdsuW4dYaLwW4xOfNN+H+++3GxAMHhl2N5KANG2xUHTnpWFAQ7cHu2hWuu87CulcvaNIk7GoTSwEu1bdokYV2t27wpz+FXY3kiMLCaA92fr7NZ3sPNWvC0UfDbbdFe7CzfTZPAS7VE1mkqkYNLVIlSbV8eekOkfnzbXudOnDccXD33RbYxxwDdeuGW2uqKcClem64Af7zH1vnu127sKuRLOG9/WIXG9iLFtm++vVtGuTSSy2wu3cPtwc7HSjApeqefx6eeQaGDoXTTgu7GslgJSU2oo4N7O+/t337729BfcMN9rlz5/TqwU4HCnCpmlmz4PrroW9fu35YpAqKi+Hzz6MtfZMnw9q1tq9lSzjxxNI92DV0y5ndUoBL5a1fb/Pe++8PL72k4ZDs0Y4d0R7s/HzrFtm40fYdfDCccUY0sNu1y6we7HSgAJfK8d4WgFiyxIZOB1S4grDksC1bYNq0aEvf1KmwdavtO/xwuOgiC+sTToBWrcKtNRsowKVyHn4Y/v53+OMfrT9LBOvBnjIlOsL+7DPYudNG0l26wDXXRHuwk7Eedq5TgMue5efDHXfAeefZLdIkZ61Zs2sPdkmJLfl+9NFw880W2Mcfbyv3SXIpwGX3VqywRarat7fOE01S5pTvvisd2HPn2vbata0H+667LLCPPTb3erDTgQJcKlZUBBdeaGedJkzI/svacpz3dh+O2Ja+hQtt33772ah6wAAL7Lw8qFUr3HpFAS67M3So/St+8UXo1CnsaiTBvLc7y0Ra+vLzbcQN0LixBfXgwdEebN0ZL/3oRyLl+8c/4MEH7cbEF18cdjWSAMXFdu/G2BH2mjW2r0WL0j3Yhx2mHuxMoACXXS1YYNcr5+XBo4+GXY1U044ddnf0SFh//HG0B7tdO7uINhLY7dvr9EYmUoBLaVu3Rhepeu01TXRmkK1brQc7Etiffmp92WAj6v79oz3YBx0Ubq2SGApwKW3wYPs9++237fYkkrY2bizdgz19erQHu3NnuOqqaGDruqvspACXqGeftYWq7roLTj017GqkjLVrbRokEtgzZ0Z7sPPyojfePf54aNgw7GolFRTgYv7zHxt9/+xntsCyhG7FitInHOfMse21alnf9dChFtjHHQf16oVbq4RDAS7RRaqaNoUxY7RIVQi8t2VmYlv6Fiywffvua6PqyBz20Ufr1IQYBXiuKymxjpOlSy01tGBFSngPX31VeoS9bJnta9TIgjpyL8cuXdSDLeXT2yLXPfSQ3Zj4T3+y38UlKYqLYfbs0oFdWGj7mje3oL79dvt8xBHqwZbKUYDnsg8/hDvvhPPPt9ueSMLs3GknGWN7sNevt31t29o54kgPdocO6sGW6lGA56oVK2ydk0MP1SJVCbB1q7XxRQJ7ypRoD3bHjraQYySwW7cOt1bJHgrwXLRzp60w+OOPMHGirVQkVfLjj3ahTOSE4/TpduWjc3DUUXDlldEe7GbNwq5WspUCPBfdeaetETpmjE24yh6tW7drD3ZxsTXsdO9uy6RHerAbNQq7WskVcQW4c+5XwNWAA5723mvhjHT3+ut2d53rr7f7W0m5Vq60/+MiI+zZs217rVpwzDF2f4tID/a++4Zbq+Suage4c64TFt49gB3Au865t7333ySqOEmwb76x+1r26AF/+EPY1aSVSA925OPrr217vXo2qr7ggmgPdu3a4dYqEhHPCPwwYKr3fguAc+4j4GzgwUQUJgm2ZQucey7UrJnzi1R5bwEdG9hLl9q+hg1t3vrqqy2wu3a1QyaSjuIJ8DnAcOfc/sBW4OdAQdkHOecGAYMAWuv0ezi8tymTOXPgnXdyrg2ipMT+6rGBvWqV7WvWzIL61lttPexOndSDLZmj2gHuvZ/vnHsAmABsAj4Hisp53EhgJEBeXp6v7utJHJ55BkaPtjVOTj457GqSbudOW9olEtaTJ0d7sA86yJZ76d3bAvuQQ9RBKZkrrpOY3vtngWcBnHO/B5YnoihJoJkz7SKd//1fW2UwC23bBp99Fg3sTz6BzZtt36GH2jIvkR7sNm3CrVUkkeLtQjnAe7/aOdcaOAfQtdjp5IcfbN77gAOyapGqTZusBzsS2NOmwfbttu/II+Gyy2x0fcIJdpm6SLaKtw98fDAHvhMY7L3/IQE1SSKUlMDAgXaX2smToUmTsCuqth9+KN2DPWNGtAe7Wzf4xS9sdN2rl92MVyRXxDuFckKiCpEEe+ABeOsteOwxa1zOIKtW2f85kcD+4gs7D7vPPvZXGTIk2oOti0gll+lKzGw0aRL85je21sngwWFXs0fLlkUvmMnPt2VWAerWhZ49YdgwC+wePaBOnXBrFUknCvBs8913FtwdO8LTT6ddi4X3dqOC2Ja+b7+1fQ0a2Lx1ZB2Rbt3Ugy2yOwrwbBJZpGrzZlsqNg2u8S4pgblzSwf2ypW2r2lTC+rIvRyPPDJrzrOKpIQCPJsMGWI9dGPHwmGHhVJCURHMmlW6B3vdOtvXqhX07Rtt6evYMe1+QRDJKArwbDFunK1v8otf2BRKimzfvmsP9qZNtq9DBzjrrGhgt22rwBZJJAV4Nvj6a7jiCmvReOSRpL7U5s0wdWr05rvTptmFNGCXoQ8cGF0Hu2XLpJYikvMU4Jlu82a7WKdWLVukap99EvrHr19vo+rICLugwKZJatSwhZ6uu84umunVC/bfP6EvLSJ7oADPZN5bgs6dC++9Zwt9xKmwsPQ62J9/bi9Ts6a18d12m42we/aE+vUT8HcQkWpTgGeykSPhxRetUfpnP6vWH7F8eekOkfnzbXudOnahzD33WGAfc4x6sEXSjQI8UxUUwC9/CaecYhftVIL3sHBh6cBevNj21a9v0yCXXmqB3b17wmdjRCTBFOCZaN06W2KveXP4298qXMC6pMRG1LGB/f33tq9JEwvqyL0cjzpKPdgimUYBnmlKSuCSSyyJP/641JnD4uJde7DXrrV9LVvaycZIS99hh6mlTyTTKcAzzYgR8K9/wRNPsKNLDwqmRAP744/hxx/tYe3bwxlnRAO7XTsFtki2UYBnkC1vT2LqXZPI7zSO/HHnMPVW2LrV9h1+OAwYEA3sAw8Mt1YRST4FeBrbsAGmBCPsjyZsp2DG8ezkA2rM83Tp4rjmmug62E2bhl2tiKSaAjyNrFlTeh3sWbNsynvvvT1H1/6am2tO4MTHz6PnBQfRoEHY1YpI2BTgIYrcLCdy0cy8eba9dm3rwb7rLhthHzv+19R98mF45RU4P/6LdUQkOyjAU8R767mObelbuND27bcfHH+8NZdEerBr1Qqe+Oqr8OTD1u93/vmh1S8i6UcBniTew5dflr7TzHff2b7GjS2oBw+2z507w97l/SS+/NLubnDccfDggymtX0TSnwI8QYqL7d6NsSPsNWtsX4sWu/ZgV3DtTdTmzXaxTu3aNgrXZZEiUoYCvJp27LC7o8f2YG/caPvatYPTTosGdvv2VezB9h6uucYmxd9/3+6EICJShgK8krZutbWvI4H96aewZYvtO+ww6N8/ug523IsC/vWvMGYM3Hsv/PSncdcuItlJAV6BjRujPdj5+TB9ut1y0jmbs77qqmhgH3BAAl/4s8/gxhvh5z+HO+9M4B8sItlGAR5Yu9amQSKBPXNmpAcb8vKiN949/nho2DCJRfTrZ5PmL75YiYlyEcllORvgK1aUPuE4Z45tr1ULjj0Whg61wD7uOKhXLwUFRRapWrnSboHTuHEKXlREMllOBLj3sGRJ9D6O+fmwYIHt23dfG1VH5rCPPjqmBzuVhg+Hd96Bv/zFhvwiInuQlQHuPXz1VekR9rJltq9RI5u3vu46C+wuXSrowU6lCRPg7rvh4out+0REpBLiii7n3E3AVYAHZgOXe++3JaKwqigutimQ2ItmCgttX/PmFtS3326fjzgizaaWly2z4f/hh1v3idZ8FZFKqnaAO+cOBH4JHO693+qcexW4EBiVoNoqtHOnnWSM7cFev972tWkDp54a7cHu0CGNM3HHDjjvPPs8fnyKJttFJFvEO3mwN1DHObcTqAt8H39Ju9q2rXQP9pQp0R7sjh0tAyMtfW3aJKOCJLn1VvuLvfaa/UVERKqg2gHuvf/OOfcwsBTYCrzvvX8/YZXFuPZaGD3aRtJHHWXLg0QCu1mzZLxiCrz8Mjz2mPUn9usXdjUikoGc9756T3SuETAeuABYD7wGjPPe/63M4wYBgwBat27dfcmSJVV+rWnTYPVq6xbJiu66+fOt3aVLF5g0CWrWDLsiEUljzrkZ3vtd2tPimUL5KbDYe18YvMDrQE+gVIB770cCIwHy8vKq9b/FMcfEUWW62bQJzj3X5rtfeUXhLSLVFk+ALwWOdc7VxaZQ+gIFCakqW3kPgwZZj+OECbpxpYjEpdoNdd77acA4YCbWQliDYKQtFXjySRg71hap+p//CbsaEclw1Z4Dr468vDxfUJCjg/Rp0+ys68knwz/+kWbN6CKSziqaA1eKpMKaNdbreOCB8MILCm8RSYiwLyLPfsXFdon8qlXWwN6oUdgViUiWUIAn2333wXvvwVNP2d2KRUQSRL/LJ9O778KwYTBwIFx9ddjViEiWUYAny9KlMGAAdOpkS8Sm7YIsIpKpFODJsH27nbQsKrJFqurWDbsiEclCmgNPhltusZtojh8PhxwSdjUikqU0Ak+0l16CJ56wED/nnLCrEZEspgBPpHnz7GRlr14wYkTY1YhIllOAJ8qPP9oiVfvtp0WqRCQlNAeeCN7byPvrr2HiRGjZMuyKRCQHKMAT4fHHbdQ9YgT06RN2NSKSIzSFEq+pU+2E5emnw69/HXY1IpJDFODxKCy0fu9Wreyeb1qkSkRSSFMo1VVcbFdaFhbCp59qkSoRSTkFeHUNG2Z31Xn6aejaNexqRCQH6Xf+6njnHburzuWXw5VXhl2NiOQoBXhVLVli63t37mxXXGqRKhEJiQK8KrZvh379bJGqceOgTp2wKxKRHKY58Kq46SYoKIA33oAOHcKuRkRynEbglTVmjK3rfdttcNZZYVcjIqIAr5S5c2HQIOjdG37/+7CrEREBFOB7FrtI1csvw96adRKR9KA02h3vrU1wwQJbpKpFi7ArEhH5LwX47vz5z/Daa/DAA3DiiWFXIyJSiqZQKjJlCtx6K5x5pp24FBFJMwrw8qxeDeefD23awKhRulhHRNKSplDKKi6Giy6CtWttkaqGDcOuSESkXNUegTvnOjrnZsV8bHTO3ZjI4kJx9912wvLJJ6FLl7CrERGpULVH4N77r4AuAM65vYDvgDcSVFc43n4bhg+3zpPLLw+7GhGR3UrUHHhfYKH3fkmC/rzU+/ZbuOQSG3U/9ljY1YiI7FGiAvxCYGyC/qzU27bNFqkqKYHx47VIlYhkhLgD3Dm3D3AG8FoF+wc55wqccwWFhYXxvlxy3HgjzJgBL7wABx8cdjUiIpWSiBH4qcBM7/2q8nZ670d67/O893lNmzZNwMsl2IsvwlNPwe23wxlnhF2NiEilJSLA+5Op0yezZ8M110CfPnDffWFXIyJSJXEFuHOuLvAz4PXElJNCGzfaIlUNG8LYsVqkSkQyTlyp5b3fAuyfoFpSx3u44gpYtAgmTYLmzcOuSESkynJz2Pnoo9Zt8tBDcMIJYVcjIlItubcWyscf2+JUZ58Nt9wSdjUiItWWWwG+apUtUtWuHTz/vBapEpGMljtTKEVF0L8/rF8P774LDRqEXZGISFxyJ8B/+1s7YTlqFBx1VNjViIjELTemUP75TxgxAq6+Gi69NOxqREQSIvsDfNEiGDgQunWzW6SJiGSJ7A7wbdvgvPPs63HjoHbtcOsREUmg7J4D/+UvYeZMm0Jp1y7sakREEip7R+CjR8PTT8Mdd8D//V/Y1YiIJFx2BvgXX8C118JJJ8Hvfhd2NSIiSZF9Ab5hgy1S1aiRFqkSkayWXenmvd3LcvFi+PBDaNYs7IpERJImuwL8kUfgjTfsc69eYVcjIpJU2TOFkp8PQ4bY9MlNN4VdjYhI0mVHgK9cCRdcAO3bw3PPaZEqEckJmT+FUlQEF15oJy/ffx/q1w+7IhGRlMj8AP/Nb+Cjj+yO8kceGXY1IiIpk9lTKG++CQ88YDcmvuSSsKsREUmpzA3whQttkaru3e0WaSIiOSYzA3zrVujXD2rU0CJVIpKzMnMO/IYbYNYseOstaNs27GpEREKReSPw55+HZ5+FoUPhtNPCrkZEJDSZFeCzZsH110PfvjBsWNjViIiEKv0DfMwYmyapUQOOPtrmu196CfbaK+zKRERCld4BPmYMDBoES5bYQlVFRXYCc8KEsCsTEQldegf40KGwZUvpbdu323YRkRyX3gG+dGnVtouI5JC4Atw519A5N84596Vzbr5z7rhEFQZA69ZV2y4ikkPiHYH/CXjXe/8ToDMwP/6SYgwfDnXrlt5Wt65tFxHJcdUOcOdcfaA38CyA936H9359ogoDYMAAGDkS2rSxJWLbtLHvBwxI6MuIiGQi572v3hOd6wKMBOZho+8ZwK+895vLPG4QMAigdevW3ZcsWRJXwSIiucY5N8N7n1d2ezxTKHsD3YC/eO+7ApuBIWUf5L0f6b3P897nNW3aNI6XExGRWPEE+HJgufd+WvD9OCzQRUQkBaod4N77lcAy51zHYFNfbDpFRERSIN7VCG8Axjjn9gEWAZfHX5KIiFRGXAHuvZ8F7DKxLiIiyVftLpRqvZhzhUB121CaAGsSWE6iqK6qUV1Vo7qqJl3rgvhqa+O936ULJKUBHg/nXEF5bTRhU11Vo7qqRnVVTbrWBcmpLb3XQhERkQopwEVEMlQmBfjIsAuogOqqGtVVNaqratK1LkhCbRkzBy4iIqVl0ghcRERiKMBFRDJUWgS4c+4m59xc59wc59xY51ztMvtrOedecc4tcM5Nc861jdl3R7D9K+fcySmu62bn3Dzn3BfOuYnOuTYx+4qdc7OCjzdTXNdlzrnCmNe/Kmbfpc65b4KPS1Nc1x9javraObc+Zl8yj9evgprmOuduLGe/c879OXgffeGc6xazL5nHa091DQjq+cI5N8U51zlm37fOudnB8SpIcV19nHMbYn5ev43Zd0rwb3GBc26Xxe2SXNdtMTXNCd5TjYN9CTtezrnnnHOrnXNzYrY1ds5NCN4nE5xzjSp4brnvJ+dc96C+BcF70VWqGO99qB/AgcBioE7w/avAZWUecz3w1+DrC4FXgq8PBz4HagHtgIXAXims6ySgbvD1dZG6gu83hXi8LgMeL+e5jbElDxoDjYKvG6WqrjKPvwF4LgXHqxMwB6iLXXn8AXBImcf8HHgHcMCxwLQUHK/K1NUz8nrAqZG6gu+/BZqEdLz6AG+V89y9gn+DBwP7BP82D09VXWUefzrw72QcL+w+CN2AOTHbHgSGBF8PAR4o53kVvp+A6cBxwXvwHeDUytSSFiNw7AdSxzm3N/YD+r7M/jOB0cHX44C+wf9QZwIve++3e+8XAwuAHqmqy3s/yXsfuevyVKBVAl+72nXtxsnABO/9Ou/9D8AE4JSQ6uoPjE3ga1fkMGCq936L974I+Ag4u8xjzgRe8GYq0NA514LkHq891uW9nxK8LqTu/VWZ41WRHsAC7/0i7/0O4GXs2IZRV9LeX977fGBdmc2xGTUaOKucp5b7fgrea/W99596S/MXKnj+LkIPcO/9d8DDwFJgBbDBe/9+mYcdCCwLHl8EbAD2j90eWB5sS1Vdsa7E/ueMqO2cK3DOTXXOVeqHkeC6zg1+9R7nnDso2JYWxyuYamoH/Dtmc1KOFzZq6+2c2985VxcbbR9U5jEVHZekHa9K1hWr7PvLA+8752Y4u2lKolS2ruOcc587595xzh0RbEuL4xXsPwUYH7M5Wccropn3fgVA8PmAch6zu/fZ8nK271HoAR7MFZ2J/YNuCdRzzl1c9mHlPNXvZnuq6oo89mJsUa+HYja39nbZ7EXAo8659ims659AW+/9UdivmpGRQVocL2wabJz3vjhmW1KOl/d+PvAANtp5F/u1vqhs+eU9dTfbU1WXFefcSViA3x6z+XjvfTdsamWwc653Cuuaia3N0Rl4DPh7pNTy/sgU1hVxOvCJ9z52lJyU41VFCX+fhR7gwE+Bxd77Qu/9TuB1bO4v1i4hD0wAAAJrSURBVHKC/22DX88bYL/C/Hd7oBWVn05IRF04534KDAXO8N5vj2z33n8ffF4EfAh0TVVd3vu1MbU8DXQPvg79eAUupMyvt0k8Xnjvn/Xed/Pe98beN9+UeUhFxyWZx6sydeGcOwp4BjjTe7825rmR47UaeIMETh3uqS7v/Ubv/abg638BNZ1zTUiD4xXY3fsr4ccrsCqYCiH4vLqcx+zufdaqnO17Fu+EfrwfwDHAXGzO1GGjxRvKPGYwpU9ivhp8fQSlT2IuInEnMStTV1fspE3ZkzyNgFrB102wN1qiTuZUpq4WMV+fjc0dgp08WRzU1yj4unGq6goe1xE7oeRScbyCP/OA4HNr4EvKnIgETqP0SczpyT5elayrNXZep2eZ7fWA/WK+ngKcksK6mkd+flgQLg2O3d7Bv8F2RE9iHpGquoJ9kcFdvWQeL6AtpU9iPkTpk5gPlvOcCt9PwGfBey9yEvPnlaojUQc3zoMxLPiBzAFexAL5d9ioFqA28FrwZp4OHBzz3KFYiH5FJc/cJrCuD4BVwKzg481ge09gdvAGng1cmeK6RmBh+jkwCfhJzHOvCI7jAuDyVNYVPOYe4P4yz0v28ZqM3S3qc6BvsO1a4Nrgawc8EbyPZgN5KTpee6rrGeCHmPdXQbD94OA5nwc/56EprusXMe+vqcT8B4PNTX8dHMuU1hV8fxnW2BD7vIQeL2x0vwLYiY2er8TOyU3EBh8TiQZzHvDMnt5PwePmBMftcWIGOLv70KX0IiIZKh3mwEVEpBoU4CIiGUoBLiKSoRTgIiIZSgEuIpKhFOAiIhlKAS4ikqH+H5gA5XzV+nnhAAAAAElFTkSuQmCC\n", | |
| "text/plain": [ | |
| "<Figure size 432x288 with 1 Axes>" | |
| ] | |
| }, | |
| "metadata": { | |
| "needs_background": "light" | |
| }, | |
| "output_type": "display_data" | |
| } | |
| ], | |
| "source": [ | |
| "pnts_ratios = [pnts_t[i]/pnts_t[i-1] for i in range(1,len(pnts_n))]\n", | |
| "plt.plot(pnts_n[:-1], pnts_ratios, 'ro-')\n", | |
| "plt.plot(pnts_n,pnts_n,'b-') # theoretical ratios\n", | |
| "plt.show()" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 14, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "8\t0.011517763137817383\n", | |
| "9\t0.08803129196166992\n", | |
| "10\t0.8997573852539062\n", | |
| "11\t9.502121210098267\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "pnts_n = []\n", | |
| "pnts_t = []\n", | |
| "\n", | |
| "n = 8\n", | |
| "t0 = t1 = 0\n", | |
| "\n", | |
| "while t1-t0<1: # in seconds; if it takes too long then stop testing\n", | |
| " G = random_euclidean_graph(n)\n", | |
| " t0 = time()\n", | |
| " exhaustive_search(G)\n", | |
| " t1 = time()\n", | |
| " # record time\n", | |
| " print( f\"{n}\\t{t1-t0}\" )\n", | |
| " pnts_n.append( n )\n", | |
| " pnts_t.append( t1-t0 )\n", | |
| " n += 1" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 15, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD9CAYAAACsq4z3AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAF/5JREFUeJzt3XuYVXW9x/H3lwGVi6EkKkgDqaWG+piOHU6eeCzMwi6o\nHXss71nYxRuKXMRIDOSu4jXnwbyC6UNZmGZa6tGTZg5qykXyEnIQ0VETRQgY+J4/fpuYhhlmz95r\n79/aa39ezzPPvsya2Z8fS75+Wb+11s/cHRERqXydYgcQEZFkqKCLiGSECrqISEaooIuIZIQKuohI\nRqigi4hkRLsF3cx+bmZvmdnCZu/1MrOHzOyl3OOupY0pIiLtyadDvwX4cov3xgB/dPdPAH/MvRYR\nkYgsnwuLzGwA8Ft3PzD3eilwpLu/YWZ9gEfdfb9SBhURke0r9Bj6Hu7+Ru75KmCPhPKIiEiBOhf7\nC9zdzazNNt/MhgPDAbp3737Y/vvvX+xHiohUlQULFrzt7r3b267Qgv6mmfVpdsjlrbY2dPd6oB6g\nrq7OGxoaCvxIEZHqZGav5bNdoYdc5gOn5Z6fBvymwN8jIiIJyee0xTuBJ4H9zGyFmZ0JTAG+aGYv\nAUflXouISETtHnJx92+18a0hCWcREZEi6EpREZGMUEEXEckIFXQRkVKaMwcGDIBOncLjnDkl+6ii\nz0MXEZE2zJkDw4fD2rXh9WuvhdcAJ52U+MepQxcRKZVx47YW8y3Wrg3vl4AKuohIqSxf3rH3i6SC\nLiJSKnvt1fr7tbUl+TgVdBGRUtlnn23f69YNJk0qycepoIuIlMJzz8Fjj8HQodC/P5iFx/r6kkyI\ngs5yERFJnjtccAH06gVz58Iuu5TlY1XQRUSSNn8+PPIIXHtt2Yo56JCLiEiyNmyAkSPhgAPgrLPK\n+tHq0EVEknTddfDyy3D//dC5vCVWHbqISFLeeQcuuwy+9KUwGVpmKugiIkm59FL44AOYOTPKx6ug\ni4gkYckSuOGGcK+WgQOjRFBBFxFJwsiR0KMHTJgQLYImRUVEivXgg2ESdPp06N07Wgx16CIixWhq\nChcR7bMPnHNO1Cjq0EVEijF7NixaBL/8Jey4Y9Qo6tBFRAq1ejWMHw+DB8Nxx8VOo4IuIlKwSZPg\n7bfhiivCzbciU0EXESnEq6/CrFlw6qlw2GGx0wAq6CIihRk9Olzaf/nlsZP8iwq6iEhHPf44zJsX\ninrfvrHT/IsKuohIR2zeDCNGQL9+4WKiFNFpiyIiHXHHHbBgAdx+e1hOLkXUoYuI5OvDD2HsWDj8\ncPj2t2On2YY6dBGRfE2fDitXwt13Q6f09cPpSyQikkYrVsC0afDNb8IRR8RO0yoVdBGRfFx8cZgQ\nnTo1dpI2qaCLiLTn6afDJOiIETBgQOw0bVJBFxHZHvdQyHffPUyIplhRBd3MRpjZIjNbaGZ3mtlO\nSQUTEUmFefPgT3+CiRPhIx+JnWa7Ci7oZrYXcC5Q5+4HAjXAiUkFExGJ7p//hFGj4OCD4TvfiZ2m\nXcWettgZ6GpmG4FuwMriI4mIpMSsWbBsGfzhD1BTEztNuwru0N39dWAGsBx4A1jt7g8mFUxEJKo3\n3wy3x/3a12DIkNhp8lLMIZddgWHAx4G+QHczO7mV7YabWYOZNTQ2NhaeVESknMaPh3XrYMaM2Eny\nVsyk6FHA39290d03Ar8CPttyI3evd/c6d6/rHXHxVBGRvL3wQlha7kc/gk9+MnaavBVT0JcDg8ys\nm5kZMARYkkwsEZFI3MOizz17hi69ghQ8KeruT5nZPOAZoAl4FqhPKpiISBT33RcmQWfNgl69Yqfp\nEHP3sn1YXV2dNzQ0lO3zREQ6ZONGOOig8PyFF6BLl7h5csxsgbvXtbed7rYoIrLFDTfA0qVw772p\nKeYdoUv/RUQA3n0XLr0UjjoKvvKV2GkKooIuIgJw2WWwejVccQWYxU5TEBV0EZGlS+G66+DMM7ce\nQ69AKugiIqNGQdeu8NOfxk5SFE2Kikh1e/hhmD8fJk+GPfaInaYo6tBFpHpt2rR10Yrzz4+dpmjq\n0EWket18Mzz/PNx1F+xU+cs5qEMXker0wQdwySVhwecTToidJhHq0EWkOk2eHG6Re++9FXuaYkvq\n0EWk+ixbFs43P/lkOPzw2GkSo4IuItVnzBjo1Cl06Rmigi4i1eWJJ8Ik6EUXQb9+sdMkSgVdRKrH\n5s3hNMW+fcPFRBmjSVERqR533gl/+Qvccgt07x47TeLUoYtIdVi7Nhw7P+wwOOWU2GlKQh26iFSH\nmTNhxQqYOzdMiGZQNkclItLcypUwZQp84xvwuc/FTlMyKugikn3jxkFTE0ybFjtJSamgi0i2PfMM\n3HornHce7L137DQlpYIuItnlHk5T3G230KVnnCZFRSS77rkHHnssLP7cs2fsNCWnDl1Esmn9+nA1\n6MCB8N3vxk5TFurQRSSbrrkGXn0Vfv976FwdpU4duohkT2NjWB/0mGPg6KNjpykbFXQRyZ6f/AQ+\n/BBmzIidpKxU0EUkWxYtghtvhB/8AA44IHaaslJBF5FsufBC2Hnn0KVXmeqYKRCR6vC734VJ0Jkz\nw7nnVUYduohkQ1NT6M733RfOPjt2mijUoYtINtTXw5Il4WKiHXaInSYKdegiUvneew/Gj4cjj4Rh\nw2KniUYFXUQq38SJ8O67cOWVYBY7TTRFFXQz28XM5pnZi2a2xMz+M6lgIiJ5eflluPpqOOMMOOSQ\n2GmiKvYY+izgAXf/bzPbAeiWQCYRkfyNGhWOmU+cGDtJdAUXdDPrCQwGTgdw9w3AhmRiiYjk4dFH\nwyToxInQp0/sNNEVc8jl40AjcLOZPWtms81sm2W0zWy4mTWYWUNjY2MRHyci0symTXDBBVBbGx6l\nqILeGTgUuMHdPw18CIxpuZG717t7nbvX9e7du4iPExFp5rbb4Nlnw1qhXbvGTpMKxRT0FcAKd38q\n93oeocCLiJTWmjVw8cUwaBCceGLsNKlR8DF0d19lZv9nZvu5+1JgCLA4uWgiIm2YOhVWrQrHz6v4\nNMWWij3L5RxgTu4Ml1eBM4qPJCKyHcuXh9vifutboUOXfymqoLv7c0BdQllERNo3dmx4nDIlbo4U\n0pWiIlI5nnoK5s4NN+GqrY2dJnVU0EWkMrjDiBGw554wZpsT6gTdbVFEKsVdd8GTT8JNN0GPHrHT\npJI6dBFJv3XrYPTocK+W006LnSa11KGLSPpdeWU4u+XWW6GmJnaa1FKHLiLptmoVTJ4Mxx4b7ncu\nbVJBF5F0u+QSWL8epk+PnST1VNBFJL2eew5+/nM455ywVqhslwq6iKSTe7iLYq9e8OMfx05TETQp\nKiLpNH8+PPIIXHMN7LJL7DQVQR26iKTPhg0wciTsvz+cdVbsNBVDHbqIpM9114W1Qu+7D7p0iZ2m\nYqhDF5F0eecduOwyOPpoGDo0dpqKooIuIukyYQK8/z7MnKl7nXeQCrqIpMeLL8L118Pw4XDggbHT\nVBwVdBFJj5EjoXv3cMhFOkyToiKSDg89FCZBp00DLShfEHXoIhJfU1O4iGjvveHcc2OnqVjq0EUk\nvptugoULYd482HHH2Gkqljp0EYlr9epwaf/gwXD88bHTVDQVdBGJ6/LL4e234YordJpikVTQRSSe\nV1+Fq66CU0+Fww6LnabiqaCLSDyjR0PnzqFLl6KpoItIHI8/HiZBR4+Gvn1jp8kEFXQRKb/Nm2HE\nCOjXL1xMJInQaYsiUn533AELFsDtt0O3brHTZIY6dBEprw8/hLFj4fDD4dvfjp0mU9Shi0h5TZ8O\nK1fC3XdDJ/WUSdKfpoiUz4oV4V4t3/wmHHFE7DSZo4IuIuVz8cVhQnTq1NhJMkkFXUTK4+mnwyTo\niBEwYEDsNJmkgi4ipeceCvnuu4cJUSmJoidFzawGaABed/evFh9JRDJn3jz405+gvh4+8pHYaTIr\niQ79PGBJAr9HRLLon/+EUaPgoIPgO9+JnSbTiiroZtYP+AowO5k4IpI5s2bBsmXhboo1NbHTZFqx\nHfpVwChgcwJZRCRr3nwTJk2Cr34VjjoqdprMK7igm9lXgbfcfUE72w03swYza2hsbCz040SkEo0f\nD+vWwYwZsZNUhWI69COAr5vZMuAXwBfM7I6WG7l7vbvXuXtdby38KlI9XngBZs+GH/4Q9tsvdpqq\nUHBBd/ex7t7P3QcAJwIPu/vJiSUTkcrlDhdeCD17wk9+EjtN1dC9XEQkefffDw89FFYj6tUrdpqq\nYe5etg+rq6vzhoaGsn2eiESwcWM4RdEdFi6ELl1iJ6p4ZrbA3eva204duogk62c/g6VLYf58FfMy\n06X/IpKcf/wDLr0UhgwJpypKWamgi0hyLrsM3nsvXERkFjtN1VFBF5Fk/O1vcO21cOaZcPDBsdNU\nJRV0EUnGRRdB167w05/GTlK1NCkqIsV7+OEwCTp5MuyxR+w0VUsduogUZ9OmrYtWnH9+7DRVTR26\niBTn5pvh+efhrrtgp51ip6lq6tBFpHAffACXXBIWfD7hhNhpqp46dBEp3OTJ4Ra5996r0xRTQB26\niBRmy6IVJ58Mhx8eO42ggi4ihRozBjp1Cl26pIIKuoh03BNPhEnQiy6Cfv1ip5EcFXQR6ZjNm8Np\nin37hsWfJTU0KSoiHXPnnfCXv8Att0D37rHTSDPq0EUkf2vXhmPnhx4Kp5wSO420oA5dRPI3cyas\nWAFz5oQJUUkV7RERyc/KlTBlChx/PAweHDuNtEIFXUTyM24cNDXBtGmxk0gbVNBFpH3PPAO33grn\nngv77BM7jbRBBV1Ets89nKb40Y+G+7ZIamlSVES279e/hsceg+uvh549Y6eR7VCHLiJtW78+XA06\ncCB873ux00g71KGLSNuuvRZeeQUeeAA6q1yknTp0EWldY2NYH3ToUPjSl2KnkTyooItI6y69FNas\nCRcTSUVQQReRbS1eDDfeCN//PhxwQOw0kicVdBHZ1oUXQo8eoUuXiqFZDhH5dw88EL5mzoTddoud\nRjpAHbqIbNXUFLrzffeFs8+OnUY6SB26iGxVXx+On99zD+ywQ+w00kHq0EUkeO89GD8ejjwShg2L\nnUYKoIIuIsHEifDuu3DllWAWO40UoOCCbmYfM7NHzGyxmS0ys/OSDCYiZfTyy3D11XDGGXDIIbHT\nSIGKOYbeBFzo7s+Y2c7AAjN7yN0XJ5RNRMpl1KhwzHzixNhJpAgFd+ju/oa7P5N7/gGwBNgrqWAi\nUiaPPhomQceOhT59YqeRIiRyDN3MBgCfBp5q5XvDzazBzBoaGxuT+DgRScqmTXDBBVBbGx6lohVd\n0M2sB/BL4Hx3f7/l99293t3r3L2ud+/exX6ciCTpttvg2WfDWqFdu8ZOI0UqqqCbWRdCMZ/j7r9K\nJpKIlMWaNXDxxTBoEJx4Yuw0koCCJ0XNzICbgCXufkVykUSkLKZOhVWrwvFznaaYCcV06EcApwBf\nMLPncl/HJJRLREpp+XKYMSN05oMGxU4jCSm4Q3f3/wX0v3WRSjR2bHicMiVuDkmUrhQVqTZPPQVz\n54azWvr3j51GEqSCLlJN3GHECNhzTxgzJnYaSZjutihSTe66C558EmbPhp13jp1GEqYOXaRarFsH\no0eHe7WcfnrsNFIC6tBFqsVVV4WzW265BWpqYqeRElCHLlINVq2Cyy8P9zn//Odjp5ESUUEXqQY/\n/jGsXw/Tp8dOIiWkgi6SdX/9K9x0U1gj9BOfiJ1GSkgFXSTL3MP55r16hS5dMk2ToiJZdu+98PDD\ncM01sOuusdNIialDF8mqDRtg5EjYf38466zYaaQM1KGLZNX118NLL8F990GXLrHTSBmoQxfJonfe\ngQkT4OijYejQ2GmkTFTQRbJowgR4/32YOVP3Oq8iKugiWTFnDgwYAJ06hUnQz38eDjwwdiopIxV0\nkSyYMweGD4fXXgunKgI88UR4X6qGCrpIFowbB2vX/vt769aF96Vq6CwXkUrz1luwaBEsXhweFy0K\nnXlrli8vbzaJSgVdJK1aK9yLF8Pbb2/dpmdP+NSnoEcPWLNm299RW1u+vBKdCrpIbB0p3MceCwMH\nhucDB0LfvuEsli3H0JsfdunWDSZNKv94JBoVdJFySaJwt+Wkk8LjuHHhMEttbSjmW96XqmC+ZUa8\nDOrq6ryhoaFsnycSRUcK98CBHSvcUpXMbIG717W3nTp0kULlW7gHDtzacW8p3ircUgIq6CLtUeGW\nCqGCLrKFCrdUOBV0qT4q3JJRKuiSXSrcUmVU0KXyqXCLACroUklUuEW2SwVd0keFW6QgKugST0cK\n93HH/fuFOH36qHCLtKCCLoWZMyf/y8xVuEXKoqiCbmZfBmYBNcBsd5+SSCpJt5Y3gnrttfD6/ffD\nCvMq3CJRFFzQzawGuA74IrACeNrM5rv74qTCAR3rBCWsVtPUVNqvkSO3XUxh7Vr44Q+3vlbhFim7\nYjr0zwAvu/urAGb2C2AYkFxBb6sThLaLujts3lxYodq4sfTFMImv7eXcvDmxP/6CPPigCrdIJMUU\n9L2A/2v2egXwH8XFaaG1ZbXWroXTTgtdYltFLbaaGujcufCvnXYq7udb++rSJbnfdcQR8Prr2467\nf3/44hfL/+ctIkAZJkXNbDgwHKC2o6untLV81qZN8PWvJ1/0kiiKNTXZ70ynTtViCiIpVExBfx34\nWLPX/XLv/Rt3rwfqIdwPvUOfUFvb+lqJ/fvDjTd26FdJgrSYgkgqdSriZ58GPmFmHzezHYATgfnJ\nxMqZNCl0fs2pE0yHk06CZcvCMftly1TMRVKg4ILu7k3A2cDvgSXA3e6+KKlgQCgS9fWhIzcLj/X1\nKh4iIq3QEnQiIimX7xJ0xRxyERGRFFFBFxHJCBV0EZGMUEEXEckIFXQRkYwo61kuZtYItHKlUF52\nA95ud6vKoLGkT1bGARpLWhUzlv7u3ru9jcpa0IthZg35nLZTCTSW9MnKOEBjSatyjEWHXEREMkIF\nXUQkIyqpoNfHDpAgjSV9sjIO0FjSquRjqZhj6CIisn2V1KGLiMh2pK6gm9kIM1tkZgvN7E4z26nF\n983Mrjazl83seTM7NFbW9uQxliPNbLWZPZf7Gh8r6/aY2Xm5MSwys/Nb+X4l7ZP2xpLafWJmPzez\nt8xsYbP3epnZQ2b2Uu5x1zZ+9stmtjS3j8aUL3XrihzLMjN7Ibd/ot7tr41xnJD772uzmbV5VktJ\n9om7p+aLsKzd34Guudd3A6e32OYY4HeAAYOAp2LnLmIsRwK/jZ21nXEcCCwEuhEWRPkDsG+F7pN8\nxpLafQIMBg4FFjZ7bxowJvd8DDC1lZ+rAV4B9gZ2AP4KfKoSx5L73jJgt9j7YzvjOADYD3gUqGvj\n50qyT1LXoRP+onU1s86Ev3grW3x/GHCbB38GdjGzPuUOmaf2xlIJDiAU6LUe7oH/P8DxLbaplH2S\nz1hSy90fA95t8fYw4Nbc81uBY1v50X8t6O7uG4AtC7pHU8RYUqW1cbj7Endf2s6PlmSfpKqgu/vr\nwAxgOfAGsNrdH2yxWWuLU+9VnoT5y3MsAJ/NHab4nZkNLGvI/CwEPmdmHzWzboRu/GMttqmIfUJ+\nY4H075Pm9nD3N3LPVwF7tLJNpeyffMYC4MAfzGxBbs3iSlSSfZKqgp47ZjYM+DjQF+huZifHTVWY\nPMfyDFDr7gcD1wC/Lm/K9rn7EmAq8CDwAPAcsClqqALlOZbU75O2ePi3fCZOW2tnLP/l7ocAQ4Ef\nmdng8iVLt1QVdOAo4O/u3ujuG4FfAZ9tsU1ei1OnQLtjcff33X1N7vn9QBcz2638UbfP3W9y98Pc\nfTDwD+BvLTaplH3S7lgqZZ808+aWw1u5x7da2aZS9k8+Y9nyr1/c/S3gHsLhi0pTkn2StoK+HBhk\nZt3MzIAhhPVKm5sPnJo7s2IQ4VDGGy1/UQq0OxYz2zP3PczsM4T98U7Zk7bDzHbPPdYSjjnPbbFJ\npeyTdsdSKfukmfnAabnnpwG/aWWb0i/onox2x2Jm3c1s5y3PgaMJh9IqTWn2SexZ4lZmfycALxJ2\n0u3AjsD3ge/nvm/AdYQZ4hdoYxY5DV95jOVsYBFhhvvPwGdjZ25jHI8Di3M5h+Teq9R90t5YUrtP\ngDsJ8zEbCcdczwQ+CvwReIlw1k6v3LZ9gfub/ewxhH+NvAKMq9SxEM4K+Wvua1HssbQxjuNyz9cD\nbwK/L9c+0ZWiIiIZkbZDLiIiUiAVdBGRjFBBFxHJCBV0EZGMUEEXEckIFXQRkYxQQRcRyQgVdBGR\njPh/hmzs8qbbb5gAAAAASUVORK5CYII=\n", | |
| "text/plain": [ | |
| "<matplotlib.figure.Figure at 0x24f86844d68>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| } | |
| ], | |
| "source": [ | |
| "plt.plot(pnts_n, pnts_t, 'ro-')\n", | |
| "plt.show()" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Discussion" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "* Exhaustive search exhibits combinatorial running time $O(n!)$:\n", | |
| "* So it is only useful/possible when $n$ is small, up to about 13 on the current machine if it needs to finish within an hour." | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "# Approximation" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "## Greedy search" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "##### Nearest neigbours" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 16, | |
| "metadata": { | |
| "collapsed": true | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def greedy_nearest_neighbours(G):\n", | |
| " H = copy.deepcopy(G) # We need the original G. We work on/modify H\n", | |
| " n = len(H)\n", | |
| " cities = list(range(n))\n", | |
| " cycle = [] # solution to be built\n", | |
| " city = 0 # Start city\n", | |
| " while len(cities)>0:\n", | |
| " # Find nearest neighbour\n", | |
| " city_neighbours = H[city]\n", | |
| " smallest_distance = min(city_neighbours)\n", | |
| " nearest_city = city_neighbours.index(smallest_distance)\n", | |
| " # Update 'cycle' and 'cities' and H then 'city'\n", | |
| " cycle.append(city)\n", | |
| " cities.remove(city)\n", | |
| " for i in range(n): # 'city' is not to be used again!\n", | |
| " H[city][i] = oo\n", | |
| " H[i][city] = oo\n", | |
| " city = nearest_city\n", | |
| " return (cycle, cost(G, cycle))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "The while-loop costs $O(n)$, and the nested for-loop within it also costs $O(n)$, while the rest can be assumed to cost $O(1)$.\n", | |
| "So the total cost of this greedy approach is $O(n)\\times O(n) = O(n^2)$." | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Example" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 17, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| " 0 1 2 3\n", | |
| " -----------------\n", | |
| " 0 | ∞ 44 50 62\n", | |
| " 1 | 44 ∞ 70 51\n", | |
| " 2 | 50 70 ∞ 13\n", | |
| " 3 | 62 51 13 ∞\n", | |
| "\n" | |
| ] | |
| }, | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "([0, 1, 3, 2], 158)" | |
| ] | |
| }, | |
| "execution_count": 17, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "G=random_symmetric_graph(4)\n", | |
| "show(G)\n", | |
| "greedy_nearest_neighbours(G)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 18, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| " 0 1 2 3\n", | |
| " -----------------\n", | |
| " 0 | ∞114.3372205364464877.0778826901725482.38931969618392\n", | |
| " 1 | 114.33722053644648 ∞38.0788655293195496.42095207992918\n", | |
| " 2 | 77.0778826901725438.07886552931954 ∞68.94200461257273\n", | |
| " 3 | 82.3893196961839296.4209520799291868.94200461257273 ∞\n", | |
| "\n" | |
| ] | |
| }, | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "([0, 2, 1, 3], 293.9670199956052)" | |
| ] | |
| }, | |
| "execution_count": 18, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "G=random_euclidean_graph(4)\n", | |
| "show(G)\n", | |
| "greedy_nearest_neighbours(G)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Test time and quality cost" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "We will initially estimate the \"quality\" simply by comparing the length of the cycle found by the greed approach to the \"average length of a random cycle\".\n", | |
| "\n", | |
| "The average length of a random cycle is estimated to be the average length of a graph edge multiplied by the number of edges, i.e.\n", | |
| "\n", | |
| "$$\\frac{\\text{MAX_DISTANCE}}{2} \\times n.$$" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 23, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "10\t0.0496525764465332\t0.5082679999999999\n", | |
| "20\t0.1907353401184082\t0.319404\n", | |
| "30\t0.3874533176422119\t0.24130666666666664\n", | |
| "40\t0.7231287956237793\t0.19880899999999999\n", | |
| "50\t1.103902816772461\t0.1685712\n", | |
| "60\t1.5338325500488281\t0.14980266666666667\n", | |
| "70\t1.8535380363464355\t0.13568571428571427\n", | |
| "80\t2.7287096977233887\t0.123572\n", | |
| "90\t3.5187318325042725\t0.11156755555555554\n", | |
| "100\t4.073294162750244\t0.10502280000000001\n", | |
| "110\t4.978093862533569\t0.09801854545454546\n", | |
| "120\t6.004432439804077\t0.092656\n", | |
| "130\t7.973381757736206\t0.087268\n", | |
| "140\t8.291640758514404\t0.08288485714285714\n", | |
| "150\t8.916183471679688\t0.0789024\n", | |
| "160\t10.312152862548828\t0.07590525\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "MAX_REPETITIONS = 500\n", | |
| "\n", | |
| "pnts_n = []\n", | |
| "pnts_t = []\n", | |
| "pnts_q = []\n", | |
| "\n", | |
| "n = 10\n", | |
| "t = 0\n", | |
| "\n", | |
| "while t<10: # in seconds; if it takes too long then stop testing\n", | |
| " t = 0\n", | |
| " expected_cycle_length = (MAX_DISTANCE/2)*n # TODO: Better estimate?\n", | |
| " sum_of_distances = 0\n", | |
| " for repetitions in range(MAX_REPETITIONS):\n", | |
| " G = random_symmetric_graph(n)\n", | |
| " t0 = time()\n", | |
| " cycle, length = greedy_nearest_neighbours(G)\n", | |
| " t1 = time()\n", | |
| " sum_of_distances += length\n", | |
| " t += t1-t0\n", | |
| " # record time and quality\n", | |
| " q = (sum_of_distances/MAX_REPETITIONS)/expected_cycle_length\n", | |
| " pnts_n.append( n )\n", | |
| " pnts_t.append( t )\n", | |
| " pnts_q.append( q )\n", | |
| " print( f\"{n}\\t{t}\\t{q}\" )\n", | |
| " n += 10" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 24, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD8CAYAAABn919SAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAHEBJREFUeJzt3XmUVOWZx/HvI4ZdBQQR2RrEZYyjYlqjSJwIogYIRs8Y\nNUA0iRITl7iHxShoGExiGI1RIiLKkRYluBF3RXAPpHEgsqioyKIYGogiO4Rn/niL2PRCL7XcW7d+\nn3P6VNWtS9+HpvvH2+99F3N3REQk/+0VdQEiIpIZCnQRkYRQoIuIJIQCXUQkIRToIiIJoUAXEUkI\nBbqISEIo0EVEEkKBLiKSEHvn8mKtW7f2oqKiXF5SRCTvzZ07d427t6npvJwGelFREaWlpbm8pIhI\n3jOzZbU5T10uIiIJoUAXEUkIBbqISEIo0EVEEkKBLiKSEAp0EZFsKimBoiLYa6/wWFKStUvldNii\niEhBKSmBIUNg06bwetmy8Bpg4MCMX04tdBGRbBkx4qsw32XTpnA8CxToIiLZsnx53Y6nSYEuIpIt\nrVpVfbxTp6xcToEuIpINixfD+vXhZmh5TZvC6NFZuWSNgW5mE81stZktKHeslZm9aGZLUo8ts1Kd\niEg+2rgRzjkHWrSAO+6Azp3BLDyOH5+VG6JQuxb6A8AZFY4NBWa4+yHAjNRrEREBuPRSWLQojHK5\n7DL4+GPYuTM8ZinMoRaB7u6vAusqHD4TmJR6Pgn4XobrEhHJT/ffD5Mmwa9+BX365PTS9e1Db+vu\nq1LPPwPaVneimQ0xs1IzKy0rK6vn5URE8sCCBaF13qsX3Hhjzi+f9k1Rd3fA9/D+eHcvdvfiNm1q\nXJ9dRCQ/bdgQ+s333Td0tTRokPMS6jtT9B9m1s7dV5lZO2B1JosSEckr7nDJJfD++/DSS3DggZGU\nUd8W+nTggtTzC4AnM1OOiEgemjAhtMpHjoRTTomsjNoMW5wCvAUcZmYrzewnwK1AHzNbApyaei0i\nUnjmzYPLL4fTTsvalP7aqrHLxd3Pr+at3hmuRUQkv6xfH/rN998fJk+uPIkox7TaoohIfbjDxRfD\n0qUwcybEYNCHAl1EpD7GjYOpU2HMGPjWt6KuBtBaLiIidTd3Llx1FfTtC9dfH3U1/6ZAFxGpi88/\nD/3mBxwQZoRG3G9enrpcRERqyx1+/GNYsQJeeQVat466ot0o0EVEausPf4DHH4fbboMePaKuppL4\n/K4gIhJnc+bAddfBgAFw9dVRV1MlBbqISE3WrYPvfx8OOggeeCCsbR5D6nIREdkTd7jwQvj0U3j9\ndWgZ3/18FOgiInvy+9/DX/4Ct98Oxx8fdTV7pC4XEZHqvPkmDB0KZ58NV1wRdTU1UqCLiFRlzRo4\n99ywD+jEibHtNy9PgS4isktJCRQVhclCHTvCqlXw5z/DfvtFXVmtKNBFRCCE+ZAhsGxZuBG6ZUsI\n9sWLo66s1hToIiIQ1jLftGn3Y9u3R77GeV0o0EVEAJYvr9vxGFKgi0hh27ABhg0L3SxV6dQpt/Wk\nQYEuIoXJHR55BA4/HG69FXr2hCZNdj+naVMYPTqa+upBgS4ihWfBAujVC847LyyD+8Yb8NprcO+9\nYZiiWXgcPx4GDoy62lrTTFERKRyffw4jR8If/xiGIo4bF7aRa9AgvD9wYF4FeEUKdBFJvp07w2YU\nQ4dCWRn89Kfw61+HzZ0TRIEuIslWWgqXXQazZ8MJJ8Czz8Kxx0ZdVVaoD11EkmnNmtASP/54WLo0\nLHv7xhuJDXNQoItI0vzrX3D33XDooXDffXDllfD++3DBBbHa/zMbkv23E5FkK7/2SlER3HQTFBfD\npZfCMcfA/PkwdmzerMWSLvWhi0h+2rX2yq7p+suWwc03hw0oHnkEzjknL1ZIzCQFuojkp+HDK6+9\nAtC8edgurgAp0EUkf2zZArNmwfTp1a+xsnJlTkuKEwW6iMRbWRk8/XQI8RdegI0bw5T8Jk1g8+bK\n5+fR2iuZltZNUTO7yswWmtkCM5tiZo0zVZiIFCh3WLgwrK/Sowe0bQs/+hHMmQODB4dwX7s2TNNv\n2nT3P5tna69kWr0D3czaA1cAxe5+JNAAOC9ThYlIAlUclVJSEo5v3w4zZoQhht26wZFHhhUQt24N\nI1fmzoUVK8JU/b59oXHjMEV//Pi8Xnsl08yrWzKypj8YAv2vwNHAeuAJ4A/u/kJ1f6a4uNhLS0vr\ndT0RyXMVR6UANGwYJvosXgxffAGNGkHv3jBgAPTvD+3bR1dvjJjZXHcvrum8evehu/snZnYbsBzY\nDLywpzAXkQJX1Y5A27aFrpQLL4Tvfhf69IFmzSIpLwnqHehm1hI4E+gCfA782cwGufvkCucNAYYA\ndCrgmxUiBa+6USnuYUanpC2dm6KnAkvdvczdtwOPAT0qnuTu49292N2L27Rpk8blRCSvdexY9XE1\n9DImnUBfDpxgZk3NzIDeQP5sjy0iuXX66ZWPFfiolEyrd6C7+2xgGvA28E7qc43PUF0ikiRbtsBz\nz0GXLqFFrlEpWZHWxCJ3vwm4KUO1iEhS3XVXGHY4Y0bY+k2yQqstikh2ffEF/M//wGmnKcyzTIEu\nItn129/CunVh5qdklQJdRLJn1Sr43/+F886D7t2jribxFOgikj033xym9d9yS9SVFAQFuohkx5Il\nYQGtIUPC+iySdQp0EcmOG24Ia7P86ldRV1IwFOgiknlz58LUqXD11XDggVFXUzAU6CKSecOGwf77\nw3XXRV1JQdGORSKSWTNmwIsvwtixsO++UVdTUNRCF5HMcYehQ8P0/p/9LOpqCo5a6CKSOdOmQWkp\nPPBA2FVIckotdBHJjO3bwyYWX/86DBoUdTUFSS10EcmMiRPD2PMnn4QGDaKupiCphS4i6du0CUaN\ngpNOClvJSSTUQheR9N1xR1i3ZerUsNa5REItdBFJz7p18JvfQP/+0LNn1NUUNAW6iKRnzBhYvz6s\neS6RUqCLSP2tWAF33gmDB8N//mfU1RQ8BbqI1N/IkWEy0c03R12JoEAXkfpatChMIPr5z8OGzxI5\nBbqI1M+IEdCsWXiUWFCgi0jdvfUWPPFEWE2xdeuoq5EUBbqI1M2uBbjatoWrroq6GilHE4tEpG6e\nfRZefRX++Edo3jzqaqQctdBFpPZ27gybV3TtChdfHHU1UoFa6CJSe1OmwN//Dg89BA0bRl2NVKAW\nuojUzrZtYcPn7t3h3HOjrkaqoBa6iNTOPffA0qXw3HOwl9qCcaR/FRGp2Zdfwi23wCmnwGmnRV2N\nVEOBLiI1GzsWysrg1lu1PG6MpRXoZtbCzKaZ2btmttjMTsxUYSISsZISKCoK3SujRsFxx8Hxx0dd\nlexBui30O4Dn3P1w4GhgcfoliUjkSkpgyBBYtixMJHKHd94JxyW26h3oZrYfcDJwH4C7b3P3zzNV\nmIhEaMSIsK1ceVu2aN2WmEunhd4FKAPuN7P/M7MJZtas4klmNsTMSs2stKysLI3LiUjOLF9et+MS\nC+kE+t7AscA4d+8ObASGVjzJ3ce7e7G7F7dp0yaNy4lIzrRrV/XxTp1yW4fUSTqBvhJY6e6zU6+n\nEQJeRPLZu+/Cxo2VjzdtCqNH574eqbV6B7q7fwasMLPDUod6A4syUpWIRGPBAviv/4LGjcMQxc6d\nwzDFzp1h/HgYODDqCmUP0p0pejlQYmYNgY+AH6VfkohEYt48OPVUaNQIXn4ZDjsMfvnLqKuSOkgr\n0N19HlCcoVpEJCqlpWEGaPPmIcy7dYu6IqkHzRQVKXRvvQW9e0OLFmGdc4V53lKgixSy114LLfO2\nbeGVV8LMUMlbCnSRQvXyy3DGGdChA8yaBR07Rl2RpEmBLlKInn8e+vULOw/NmgUHHRR1RZIBCnSR\nQvPUUzBgABx+OMycGbpbJBEU6CKF5PHH4eyz4aijYMYMaN066ookgxToIoVi6lQ45xwoLoaXXoJW\nraKuSDJMgS5SCCZPhvPPhx49Qv/5fvtFXZFkgQJdJOkmToQf/hC+/W149lnYZ5+oK5IsUaCLJNk9\n98BPfhLGmj/1FDSrtMK1JIgCXSSp7rwTLrkE+veHJ56AJk2irkiyTIEukhTl9wBt2RKuuALOOgse\nfTSsniiJl+5qiyISB7v2AN21bdznn0ODBvC970HDhtHWJjmjFrpIElS1B+i//gU33hhNPRIJBbpI\nEmgPUEGBLpL/1qypvltFe4AWFAW6SD57/3044QTYsaNyqGsP0IKjQBfJV6++GsJ8/fqwrvnEidoD\ntMBplItIPnrwwTBh6OCD4emnwzK4J56oAC9waqGL5BN3GDkyTOXv2RPefDOEuQhqoYvkj61b4aKL\nwkJbF14YpvVrjLmUo0AXyQdr14ZZn6+9Fm50DhsW+spFylGgi8TdBx9A375hTPmUKXDeeVFXJDGl\nQBeJs9dfD9P3IewwdNJJ0dYjsaaboiJxNWUK9O4N++8Pf/2rwlxqpEAXiRt3+PWv4Qc/COPM33oL\nunWLuirJA+pyEYmTbdvCqomTJsHgwXDvvdCoUdRVSZ5QC10kLv75Tzj99BDmo0aFR4W51IECXSQq\n5TekaN8ejjgiTBR68MGw7K2GJUodpd3lYmYNgFLgE3fvn35JIgWg4oYUn34aHm+4AQYNiq4uyWuZ\naKH/Alicgc8jUjiq2pACQutcpJ7SCnQz6wD0AyZkphyRAqENKSQL0m2h3w5cD+zMQC0iyTdvHvTr\nF4YmVkUbUkga6h3oZtYfWO3uc2s4b4iZlZpZaVlZWX0vJ5LfliwJU/a7dw/jys89F5o02f0cbUgh\naUqnhX4SMMDMPgYeBnqZ2eSKJ7n7eHcvdvfiNm3apHE5kTy0cmW4+fkf/wF/+UvoO//oI3j44TDG\nXBtSSAaZV/erX10+idm3gWtrGuVSXFzspaWlaV9PJPbWrIExY+Cuu2DnTrjkkhDmbdtGXZnkITOb\n6+7FNZ2nmaIimfTllzB2LPz+97BxY5jtOXJkGG8ukmUZCXR3nwXMysTnEslLW7bA3XeHVvmaNXD2\n2XDLLWGykEiOaKaoSDp27IAJE+CQQ+Caa8JNzzlz4NFHFeaScwp0kdooP02/qChsAzd1Knz963Dx\nxWHq/ssvwwsvwHHHRV2tFCj1oYvUpOI0/WXLwibN7iHQn3gCBgzQ2isSOQW6SE2qmqbvHjaemD8f\nGjSIpi6RCtTlIlKT6qbjr1unMJdYUaCL7MnmzdCsWdXvaZq+xIwCXaQ6770XtoDbsAH2rtA7qWn6\nEkMKdJGqTJkCxcXwySfwzDPwwAOapi+xp5uiIuVt3gxXXhkCu2fPEOwdOoT3FOASc2qhi+yyq4tl\n/HgYOhRmzvwqzEXygFroIgAPPQQ//WnYlPmZZ+A734m6IpE6UwtdCtvmzWHS0MCBcMwxYQMKhbnk\nKQW6FK5dXSz33qsuFkkEdblIYXroodAyb9xYXSySGGqhS2Ep38XSvbu6WCRRFOhSONTFIgmnQJdk\nqrjc7aWXwje+8dVEoTFjKs/+FMlz+o6W5Klqudu774ZDD4UZM9Qql8RSC12Sp6rlbiFsE6cwlwRT\noEvyVLfc7YoVua1DJMcU6JIs7tCiRdXvablbSTgFuiTH9u3w85/DP/9ZeeMJLXcrBUCBLsmwdi2c\nfjr86U/wy1/C/fdruVspOBrlIvlv8WL47ndDH/mkSWEDZ4DBg6OtSyTHFOiS3557Ds49N0zhnzkT\nevSIuiKRyKjLRfKTO9x+O/TrB126wJw5CnMpeAp0yT/btoWJQ1ddBQMGwOuvh35ykQKnQJf8smYN\n9OkDEyaECUSPPgrNm0ddlUgsqA9d8sfCheHm56efhun9P/hB1BWJxIoCXfLD00/D+edDs2bwyivw\nzW9GXZFI7NS7y8XMOprZTDNbZGYLzewXmSxMBAg3P2+7LbTMDzkE/vY3hblINdJpoe8ArnH3t81s\nH2Cumb3o7osyVJsUuq1b4Wc/C5OE/vu/4YEHQgtdRKpU7xa6u69y97dTz78EFgPtM1WYFLjVq+HU\nU0OY33gjPPKIwlykBhkZ5WJmRUB3YHYV7w0xs1IzKy0rK8vE5SSJym9IcdBBcMQRUFoKDz8Mo0aF\n4yKyR2n/lJhZc+BR4Ep3X1/xfXcf7+7F7l7cpk2bdC8nSbRrQ4ply0Kf+apVsG4dDB8eZoGKSK2k\nFehm9jVCmJe4+2OZKUkKzvDhlTekcIf77oumHpE8Ve+bomZmwH3AYncfm7mSpCBs3QqzZsH06dVv\nSFHdcRGpUjqjXE4CBgPvmNm81LHh7v5M+mVJIq1ZEzZonj4dnn8eNmwI65Q3aQKbN1c+XxtSiNRJ\nvQPd3V8HLIO1SBK9914I8OnT4c03YefOcNNz4MCwDsspp8Bjj+2+qTNoQwqRetDQAamf8qNSiorC\na4AdO+DVV+Haa+HQQ+Hww+H660Nr/IYbwsSgFSvCRhR9+4bW+cCBYQMKbUghkhZz95xdrLi42EtL\nS3N2PcmSXaNSyreoGzaE444Lm02sWwdf+xr06hVa4f37q/tEJA1mNtfdi2s6T2u5SN2NGFF5VMq2\nbfDWWzBoUAjx006DffaJpj6RAqVAl9pzD10my5ZV//6kSbmtSUT+TX3oUrMNG+Dee+Eb3wgLY1k1\n98LVrSISKQW6VG/BArjsMmjfPvSZ79gBd98dblg2bbr7uRqVIhI5dbnI7rZuhWnTwiiU11+HRo3g\nnHPCqocnnvhV67xJk9CXvnx5aJmPHq1RKSIRU6BL8OGHcM89YXXDNWugW7ewDvkFF0Dr1pXPHzhQ\nAS4SMwr0QrZjBzz1FIwbBy+8AA0awJlnhtZ4r15a4VAkzyjQC0FJye7dI9deC2vXhhudn3wS+shH\njYKLLgqzOEUkLynQk67iJKBly+Dyy8PzM86Au+6Cfv1gb30riOQ7/RQn3XXXVZ4EBKEl/uyzua9H\nRLJGnaRJtGoVjB0Lxx4bnld3jogkigI9KTZsgMmT4fTToUMHuOaa0I3SsmXV52sSkEjiKNDz2Y4d\nYV3xwYPhwAPD4/vvhx2AFi+GOXPgzjs1CUikQKgPPd+4w7x5oTX+0EPw2WfQokUYEz5oEJx00u7D\nDXeNFdckIJHEU6DHUcVhhqNHw8knh+OTJ8PChWF52n79Qqu8b19o3Lj6z6dJQCIFQYEeN1UNM/zh\nD8NOPxBa4OPGwfe/D61aRVeniMSOAj1uhg6tPMxw507Ybz94+23o2jWaukQk9hTocfCPf8CTT4a9\nNVeurPqc9esV5iKyRwr0qCxdCo8/Hj7eeCPc7Dz4YNh33xDeFWmYoYjUQMMWc8U93My85ZYw4adr\n1zBWfP16uOkmmD8fliwJ641rmKGI1IMCPRNKSsLO93vtFR5LSsLxnTth9uzQL37YYXDkkXDjjWEt\n8d/9Dj74IAT5TTfBUUeFtcYHDgwbSHTuHF537hxea5SKiNTA3D1nFysuLvbS0tKcXS8nKo5KgbAp\nxMknw6JFYTXDvfeGU06Bs84Ky9NqRUMRqQMzm+vuxTWdpz70dA0fXnlUytat8NJLIbzHjIH+/auf\ngi8ikiEK9LrYujW0uufPD7M1580Lk3+q8/jjuatNRApe4QV6VbMwq+qfXrs2BHf58F60KKyfAuFG\n5VFHQfPmYWGsijQqRURyrLACvapZmEOGwOrVIYDLh/eKFV/9uXbt4OijwxT7Y44JH926hS3bqupD\n16gUEYlA4QT65s1Vb/awaRNcfXV4vtdecPjh0LPnV8F99NHQtm31n1eLX4lITKQV6GZ2BnAH0ACY\n4O63ZqSq8mrbReIeZlx+9FH4+PDD3Z/XtKHDnDlhWGGTJnWvUYtfiUgM1DvQzawBcBfQB1gJ/M3M\nprv7okwVV2UXyUUXhS6Rzp13D+2PPtq99W0WNj/u2jXsndm1K9xxB6xZU/k6nTvDccdlrGwRkSik\n00I/HvjA3T8CMLOHgTOBzAX6iBGVu0i2bIHbbgvPmzYNQX3wwdCnT3i+63XnzpWXlO3SRf3dIpJY\n6QR6e6DcnUNWAt9Mr5wKqhsSaBa6UA44IDyvLfV3i0iCZf2mqJkNAYYAdKrrUL5OnUI3S1XH93Sj\nck/U3y0iCZXOWi6fAB3Lve6QOrYbdx/v7sXuXtymTZu6XWH0aC1UJSJSS+kE+t+AQ8ysi5k1BM4D\npmemrBQtVCUiUmv17nJx9x1mdhnwPGHY4kR3X5ixynZRF4mISK2k1Yfu7s8Az2SoFhERSYPWQxcR\nSQgFuohIQijQRUQSQoEuIpIQOd2CzszKgCpmCkWiNVDFwi6xohrTF/f6IP41xr0+SH6Nnd29xok8\nOQ30ODGz0trs0Rcl1Zi+uNcH8a8x7vWBatxFXS4iIgmhQBcRSYhCDvTxURdQC6oxfXGvD+JfY9zr\nA9UIFHAfuohI0hRyC11EJFEKItDNrKOZzTSzRWa20Mx+kTreysxeNLMlqceWEdfZwMz+z8yeiml9\nLcxsmpm9a2aLzezEONVoZlel/n0XmNkUM2scdX1mNtHMVpvZgnLHqq3JzIaZ2Qdm9p6ZnR5hjb9L\n/Tv/3cweN7MWcaux3HvXmJmbWeuoaqyuPjO7PPV1XGhmv816fe6e+A+gHXBs6vk+wPvAEcBvgaGp\n40OB30Rc59XAQ8BTqddxq28ScFHqeUOgRVxqJOygtRRokno9Fbgw6vqAk4FjgQXljlVZU+p7cj7Q\nCOgCfAg0iKjG04C9U89/E8caU8c7ElZ8XQa0jqrGar6GpwAvAY1Srw/Idn05+8aO0wfwJGFz6/eA\ndqlj7YD3IqypAzAD6FUu0ONU336pwLQKx2NRI19tidiKsIroU6lQirw+oKjCD3qVNQHDgGHlznse\nODGKGiu8dxZQEscagWnA0cDH5QI9khqr+HeeCpxaxXlZq68gulzKM7MioDswG2jr7qtSb30G1HNf\nu4y4Hbge2FnuWJzq6wKUAfenuoUmmFkzYlKju38C3AYsB1YBX7j7C3Gpr4Lqaqpqn972uSysGj8G\nnk09j02NZnYm8Im7z6/wVlxqPBT4lpnNNrNXzOy41PGs1VdQgW5mzYFHgSvdfX359zz8VxnJkB8z\n6w+sdve51Z0TZX0pexN+pRzn7t2BjYTugn+L+GvYEjiT8B/PQUAzMxtU/pwYfA0riWNN5ZnZCGAH\nUBJ1LeWZWVNgOHBj1LXswd6E3xhPAK4DpprVZVf7uiuYQDezrxHCvMTdH0sd/oeZtUu93w5YHVF5\nJwEDzOxj4GGgl5lNjlF9EFoRK919dur1NELAx6XGU4Gl7l7m7tuBx4AeMaqvvOpqqtU+vbliZhcC\n/YGBqf94ID41Hkz4z3t+6uemA/C2mR1IfGpcCTzmwRzCb9+ts1lfQQR66n/F+4DF7j623FvTgQtS\nzy8g9K3nnLsPc/cO7l5E2Jv1ZXcfFJf6ANz9M2CFmR2WOtQbWER8alwOnGBmTVP/3r2BxTGqr7zq\napoOnGdmjcysC3AIMCeC+jCzMwhdgAPcfVO5t2JRo7u/4+4HuHtR6udmJWHgw2dxqRF4gnBjFDM7\nlDCQYE1W68vFzYyoP4CehF9r/w7MS330BfYn3IhcQrgb3SoGtX6br26Kxqo+4BigNPV1fAJoGaca\ngVHAu8AC4EHCKIJI6wOmEPr0txNC5yd7qgkYQRj18B7wnQhr/IDQz7vr5+VPcauxwvsfk7opGkWN\n1XwNGwKTU9+PbwO9sl2fZoqKiCREQXS5iIgUAgW6iEhCKNBFRBJCgS4ikhAKdBGRhFCgi4gkhAJd\nRCQhFOgiIgnx/xmt4HL/3qYvAAAAAElFTkSuQmCC\n", | |
| "text/plain": [ | |
| "<matplotlib.figure.Figure at 0x24f870a6940>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| } | |
| ], | |
| "source": [ | |
| "plt.plot(pnts_n, pnts_t, 'ro-')\n", | |
| "plt.show()" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 25, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAG8dJREFUeJzt3XmUlNWZx/HvQ7eIqEGERmXrxrgQl0hIi0uauC9Rz7iM\nZ0ZtnHEmkRCPMa4jisctITOo0ThGJYzRMbHV8WggTMSgzjjKyERo3NhEUVnD0gbFaIOAPPPHraar\nm6ru6u7qeqve9/c5p07Xu3TXQwO/unXf+95r7o6IiMRLj6gLEBGR/FO4i4jEkMJdRCSGFO4iIjGk\ncBcRiSGFu4hIDCncRURiSOEuIhJDCncRkRgqj+qF+/fv71VVVVG9vIhISZo3b95H7l7R3nmRhXtV\nVRX19fVRvbyISEkys+W5nKduGRGRGFK4i4jEkMJdRCSGFO4iIjGkcBcRiaHSCve6Oqiqgh49wte6\nuqgrEhEpSpENheywujoYOxYaG8P28uVhG6C2Nrq6RESKUOm03CdMaA72Jo2NYb+IiLSQU7ib2elm\ntsTMlprZ+AzHjzezjWb2Zupxc94rXbGiY/tFRBKs3W4ZMysD7gdOAVYBc81sursvanXqLHc/qxtq\nDIYODV0xmfaLiEgLubTcRwFL3f0Dd98CPAmc3b1lZTBxIvTu3XJf795hv4iItJBLuA8CVqZtr0rt\na+1YM3vbzJ4zs0PzUl262lqYMgUqK8O2GUyerIupIiIZ5OuC6uvAUHf/OnAfMC3TSWY21szqzay+\noaGh469SWwvLlsFjj4E7HH54V2oWEYmtXMJ9NTAkbXtwat8O7v6pu3+Wej4D2MXM+rf+Qe4+xd2r\n3b26oqLdGSuzq6kJX//3fzv/M0REYiyXcJ8LHGhmw8ysJ3ABMD39BDPb18ws9XxU6uf+Od/F7lBZ\nCUOGKNxFRLJod7SMu28zs8uBmUAZ8LC7LzSzcanjk4HzgR+Y2TZgE3CBu3s31h1a7y+/HLpnwvuK\niIik5HSHaqqrZUarfZPTnv8C+EV+S2tHTQ088UQYHqkVnUREWiidO1Rba+p3nzUr2jpERIpQ6Yb7\noYdCnz7qdxcRyaB0w72sDI49VuEuIpJB6YY7wOjRsGgR/Ln7BuaIiJSi0g73pn732bOjrUNEpMiU\ndrgfeST07KmuGRGRVko73Hv1gupqjZgREWmltMMdQtdMfT1s2hR1JSIiRSMe4b51K8ydG3UlIiJF\no/TD/dhjw1f1u4uI7FD64d6vX7ihSeEuIrJD6Yc7hK6Z2bPhyy+jrkREpCjEJ9w3boSFC6OuRESk\nKMQn3EFDIkVEUuIR7pWVMGiQ+t1FRFLiEe5mofU+a1ZYvENEJOHiEe4QJhFbvRpWrIi6EhGRyMUn\n3LVotojIDvEJ98MOg698ReEuIkKcwr1p8Q6NmBERiVG4Q+iaWbgQNmyIuhIRkUjFL9xBi3eISOLF\nK9xHjYJddlG/u4gkXrzCfbfdwuIdCncRSbh4hTuErpm5c2Hz5qgrERGJTDzDfcsWLd4hIokWv3DX\n4h0iIjEM9/794WtfU7iLSKLFL9whzDPz6quwfXvUlYiIRCKe4a7FO0Qk4eIb7qCuGRFJrHiGe1UV\nDByoeWZEJLHiGe5Ni3eo5S4iCRXPcIcQ7itXavEOEUmk+Ib76NHhq1rvIpJA8Q33ww+HPfdUuItI\nIsU33JsW71C4i0gC5RTuZna6mS0xs6VmNr6N8440s21mdn7+SuyCmhpYsAA+/jjqSkRECqrdcDez\nMuB+4DvAIcCFZnZIlvMmAc/nu8hOq6kBdy3eISKJk0vLfRSw1N0/cPctwJPA2RnO+yHwDLA+j/V1\njRbvEJGEyiXcBwEr07ZXpfbtYGaDgHOBB/NXWh707g3f/KbCXUQSJ18XVH8OXO/ubc7UZWZjzaze\nzOobGhry9NLtqKmBOXO0eIeIJEou4b4aGJK2PTi1L1018KSZLQPOBx4ws3Na/yB3n+Lu1e5eXVFR\n0cmSO6hp8Y558wrzeiIiRSCXcJ8LHGhmw8ysJ3ABMD39BHcf5u5V7l4FPA1c5u7T8l5tZ2jxDhFJ\noHbD3d23AZcDM4HFwFPuvtDMxpnZuO4usMsqKmD4cE0iJiKJUp7LSe4+A5jRat/kLOde0vWy8qym\nBp5+Oize0SO+922JiDRJRtKNHg2ffAKLFkVdiYhIQSQj3LV4h4gkTDLCfdgw2G8/hbuIJEYywl2L\nd4hIwiQj3CGE+/LlYQEPEZGYS1a4g1rvIpIIyQn3r39di3eISGIkJ9zLy+GYYxTuIpIIyQl3CF0z\n8+eHMe8iIjGWvHB3h//7v6grERHpVskK91GjQveM5pkRkZhLVrjvvjuMHKl+dxGJvWSFO4R5ZubM\ngS++iLoSEZFuk7xwr6kJwa7FO0QkxpIX7t/6VviqrhkRibHkhXtFBRx8sMJdRGIteeEOoWvm1VfD\n4h0iIjGU3HDfsAEWL466EhGRbpHMcB89OnxV14yIxFQyw33//WHffRXuIhJbyQx3Ld4hIjGXzHCH\nEO7LlsGqVVFXIiKSd8kOdwijZkREYia54X7EEbDHHppETERiKbnhrsU7RCTGkhvuELpm3n4bNm6M\nuhIRkbxSuGvxDhGJoWSH+1FHQVmZumZEJHaSHe5avENEYirZ4Q7Qrx+8/DL06AFVVVBXF3VFIiJd\nluxwr6uDl14Kz91h+XIYO1YBLyIlL9nhPmHCzsvtNTaG/SIiJSzZ4b5iRcf2i4iUiGSH+9ChHdsv\nIlIikh3uEydC794t9+26a9gvIlLCkh3utbUwZQpUVoZpgMvKYOBAuPDCqCsTEemSZIc7hIBftiys\np/rww/Dhh/D441FXJSLSJTmFu5mdbmZLzGypmY3PcPxsM3vbzN40s3ozq8l/qQUwZgxUV8P48fD5\n51FXIyLSae2Gu5mVAfcD3wEOAS40s0NanfZfwBHuPgL4R+ChfBdaED16wD33wOrVcNddUVcjItJp\nubTcRwFL3f0Dd98CPAmcnX6Cu3/m7p7a3B1wSlVNDfzN38CkSVqlSURKVi7hPghYmba9KrWvBTM7\n18zeAZ4ltN53YmZjU9029Q0NDZ2ptzAmTQp98DfeGHUlIiKdkrcLqu4+1d2HA+cAP85yzhR3r3b3\n6oqKiny9dP5VVcHVV8NvfgNz5kRdjYhIh+US7quBIWnbg1P7MnL3V4D9zax/F2uL1g03wD77wFVX\nhXlnRERKSC7hPhc40MyGmVlP4AJgevoJZnaAmVnq+UhgV+DP+S62oPbcM9zMNHs2PPVU1NWIiHRI\nu+Hu7tuAy4GZwGLgKXdfaGbjzGxc6rS/BhaY2ZuEkTV/m3aBtXRdcgmMGAHXXw+bNkVdjYhIziyq\nDK6urvb6+vpIXrtDXnoJTjwxtOJ1gVVEImZm89y9ur3zdIdqe044Ac45B/75n2HNmqirERHJicI9\nF3feGeZ9v+mmqCsREcmJwj0XBxwAV1wBjzwCb7wRdTUiIu1SuOfqppvCeqsaGikiJUDhnqu99oLb\nbw+LaU+bFnU1IiJtUrh3xKWXwqGHwnXX7bz2qohIEVG4d0R5Odx9N7z/Ptx3X9TViIhkpXDvqFNP\nhTPOgB//GIp58jMRSTSFe2f87GdhMY+bb466EhGRjBTunTF8OFx2WVh/dcGCqKsREdmJwr2zbrkF\n+vQJUwNraKSIFBmFe2f16xcC/oUXYMaMqKsREWlB4d4Vl10GBx8M11wDW7dGXY2IyA4K967YZZew\nkPaSJfDgg1FXIyKyg8K9q848E045BW69FTZsiLoaERFA4d51ZuHGpo0b4bbboq5GRARQuOfHYYeF\nqQnuvx/eeSfqakREFO55c/vtsPvucO21UVciIqJwz5sBA8K0wM8+C/vsAz16QFUV1NVFXZmIJFB5\n1AXEyoABoQ9+/fqwvXw5jB0bntfWRleXiCSOWu75dMstO9+t2tgIEyZEU4+IJJbCPZ9WrOjYfhGR\nbqJwz6ehQzu2X0Skmyjc82niROjde+f9J59c+FpEJNEU7vlUWxumAa6sDBdWhwyBI46AX/0K7r03\n6upEJEE0WibfamtbjozZsgUuugiuvDIs8HHjjdHVJiKJoZZ7d+vZE558EsaMCaNmJkzQ/O8i0u3U\nci+E8nJ49NHQH//Tn4YW/D33hK4bEZFuoHAvlB49YPLkEPA//3kY//7gg1BWFnVlIhJDCvdCappB\ncvfdw8iaxkb4938PLXsRkTxSqhSaGfzkJ6EFP2ECbN4Mjz8e+uZFRPJEF1SjcuONoXvmmWfg3HNh\n06aoKxKRGFG4R+lHPwrj4p97Lqzo9NlnUVckIjGhcI/apZfCr38Nr7wCp50Gn3wSdUUiEgMK92Iw\nZgw89RTMnQsnnQQffRR1RSJS4hTuxeK882DaNFi0CI4/HtaujboiESlhCvdicsYZMGMGLFsG3/42\nrFwZdUUiUqJyCnczO93MlpjZUjMbn+F4rZm9bWbzzWy2mR2R/1IT4oQT4PnnYd06GD0a3n8/6opE\npAS1G+5mVgbcD3wHOAS40MwOaXXah8Bx7n448GNgSr4LTZRjj4WXXgqjZ6qrYeBArckqIh2SS8t9\nFLDU3T9w9y3Ak8DZ6Se4+2x3/zi1+UdgcH7LTKCRI+G668LomTVrwmRjTWuyKuBFpB25hPsgIL3z\nd1VqXzbfBZ7LdMDMxppZvZnVNzQ05F5lUj344M77tCariOQgrxdUzewEQrhfn+m4u09x92p3r66o\nqMjnS8eT1mQVkU7KJdxXA0PStgen9rVgZl8HHgLOdvc/56e8hMu29qoZTJ1a2FpEpKTkEu5zgQPN\nbJiZ9QQuAKann2BmQ4HfAhe7+7v5LzOhMq3J2qtXWL7vvPPg4ovh448zf6+IJFq74e7u24DLgZnA\nYuApd19oZuPMbFzqtJuBfsADZvammdV3W8VJ0npN1spKeOgheO89uOUWeOIJOPxwmDkz6kpFpMiY\nR7TkW3V1tdfX6z2gS+rr4e/+DhYvhnHj4M47YY89oq5KRLqRmc1z9+r2ztMdqqWsuhpefx2uuQZ+\n+Us44giYNSvqqkSkCCjcS12vXnDXXfDyy2H7uOPg2mvDIiAiklgK97gYPRreegu+/3342c/CTVDq\n9hJJLIV7nOyxR7jx6Q9/gE8/haOPDhdet26NujIRKTCFexyddhrMnw8XXQS33w5HHQULFkRdlYgU\nkMI9rvr2DSs8PfMMrFoF3/wm3HEHfPll1JWJSAEo3OPuvPNCq/3MM+H668M88XffHWaY1EyTIrFV\nHnUBUgADBoQWfF1dmFVy9uzmY00zTUK4aUpEYkEt96QwC2u17r33zsc006RI7Cjck+ZPf8q8f/ly\nePPNwtYiIt1G4Z40bc00+Y1vQE0N/Md/aPikSIlTuCdNppkme/eGyZPDzU9r1sAFF4RJym67Ddau\njaZOEekShXvSZJppcsqUcFH16qvDjJPPPgsjRsCtt4aW/kUXhYuwEU0yJyIdp1khJbv33oMHHoBH\nHoGNG0O3zeWXw4UXwm67RV2dSCJpVkjpugMPhHvuCTdBTZ4MW7bAd78LgweHMfPLloXz6uo0bl6k\nyKjlLrlzD7NP/uIXMG1a2B4xAhYuhC++aD6vd+/Q1aNx8yJ5p5a75J8ZHH88PP00fPgh3HBDGD6Z\nHuygcfMiRUDhLp0zZAj85CfZL7I2jZvXRViRSCjcpWuyjZuHcAH2q18NK0W9+ips3164ukQSTuEu\nXZNt3PwDD8C//RsMHw733Rdujho4MKz1OnNmuDgrIt1G4S5dk23c/A9+AN/7HsyYAQ0N8PjjYUbK\nxx6D008Pk5mNGRMmNPv886j/FCKxo9EyUlibNsGLL8LUqfC738GGDWEd2NNOC9MTn3UWPPdcuCC7\nYkXo9pk4USNvRFJyHS2jcJfobNsGs2aFoJ86NYynNwuP9P55Da0U2UFDIaX4lZfDCSfAv/5raKXP\nmQN77rnzhdfGxjA1QmNjNHWKlCCFuxQHMzjySPjLXzIfX78+LB140kkwaRK88YZG34i0QeEuxSXb\n0MoBA+CHP4SPPoLx42HkSNh339BV8+ij2eepF0kohbsUl2xDK+++G+66C956KwT5r38dLsK++CJc\ncgkMGgSHHRa6b/7wh5ZdOJr7RhJIF1Sl+NTV5T5aZvt2mD8fnn8+PGbNCtMh9OwJo0dD//5hVM7m\nzc3fowu0UsI0WkaSadOmEPBNYT9/fubzKiubZ7UUKSG5hnt5IYoRKZjddoNTTw0PCF0xmRowy5fD\nlVfCKafAccfBHnsUtk6RbqY+d4m3bBdoe/WCX/4y3DS1994h4CdODMMxv/yysDWKdAOFu8Rbtgu0\nDz0EH38ML7wAV10VhmDedBMcdRRUVMD554d++Q8/jKZukS5SuEu8ZZv7prY2tN5PPjmMm3/9dVi3\nLsyBc8458Npr8P3vw/77wwEHhLlypk6FTz4JP1cjcKTI6YKqSCbu8M47oWX/wgvwP/8Dn30WwnzY\nsDCSZ+vW5vM1AkcKRBdURbrCDL72tfC44oowRfEf/xiC/o47WgY7hHH148bB2rVw0EHhMWxYGJIp\nEgG13EU6KtsInNbKykKXTVPYNz0OPDCsZNUjrVe0I2P7JdHy2nI3s9OBe4Ey4CF3/5dWx4cDjwAj\ngQnuflfHSxYpEUOHhqGUrVVWwrx58N578O67zV/ffRdeeaXlvPW9eoW+/IMOCp8Knn++eQGT5cth\n7NjwXAEvndRuuJtZGXA/cAqwCphrZtPdfVHaaRuAK4BzuqVKkWIycWII3/QpDnr3Dvv79QuPo49u\n+T3usGZNc9g3Bf+iRaFvv7XGxnBBd82a0DU0fHj4FFBW1q1/NImPXFruo4Cl7v4BgJk9CZwN7Ah3\nd18PrDezM7ulSpFi0tSa7kg3illYZnDgQDj++JbHsnXzfP45XHdd8/auu4aW/vDh4dEU+gcfvPNw\nT3XzJF4u4T4IWJm2vQo4qnvKESkRtbX5C8u2unlefx2WLIHFi0MLf/HiMN3xM8+0nPK4srI58Ddu\nDEM6v/giHFM3TyIVdLSMmY0FxgIMzXbnoEjStNXNs/fecMwx4ZFu82ZYurQ59JuCf9aszIuaNDaG\nsfpr14Y3gqZHRUX4VJELfRooKbmE+2pgSNr24NS+DnP3KcAUCKNlOvMzRGKnM908vXqFKY4PO6zl\n/u3bwwpXmbp5/vIXuPbalvt22y28XmVl89f0x6BB4efV1bV8A9KngaLX7lBIMysH3gVOIoT6XOAi\nd1+Y4dxbgc9yGS2joZAi3aSqKnM3z9Ch8Oab4Vi2R0NDy+8pKwsBv25dczdPuiFDwhuSFEzehkK6\n+zYzuxyYSRgK+bC7LzSzcanjk81sX6Ae+Aqw3cyuBA5x90+79KcQkY7L1s3z05+GpQr79oURIzJ/\nb2NjCOumsG96/thjmc9fuRL22ae5pV9VtXPrv0+fzN+rbp5upZuYROIo38GZ7dNAnz5hkrX0N4PW\nLfw+fXYO/JUrw3QNWkSlw7RYh4jkT+s+d8gcxtu3h8XMs3X7LFuWfRF0CNcA/uEfwpDR/fZrfgwc\nGFbV6tHGXIcJ+SSguWVEJH9yvejbo0dYuHzffcP0ya25h5k1+/XLfNF30yZ44okwHXNr5eWhCyhT\n8C9ZAvff3/xJQBd81XIXkQhk6+ZpWv5w8+Zwd276409/2nn7o4/afp1eveC888KbQqbHgAGwyy6Z\nv7dIPwmo5S4ixautsf0QQnnYsPBoy5YtYSRPZWXmTwKbN4fZPNetazm3T7q+fXcO/TVrYPr0lvP9\nXHpp6Ha6+OKO/3mbFPANQy13EYlGPoOuvU8CEMJ93brcHp+2MdCvT5/mUUd9+4YbzXJ5/p//GeYL\nau+6RTt0QVVEkiPXC765amta5yuuCNcENmwIX9OfN7X0OyL9DSgH6pYRkeTozF2+bWlrvp977838\nPe7hgnB66KcH/zXXZP6+broJTC13EZHW8v1JAHLrOspBri13LZAtItJaWwurd9bEiTtPzZx+ETnP\n1C0jIpJJPqd1bvp5ULDRMgp3EZFCyfcbRhvULSMiEkMKdxGRGFK4i4jEkMJdRCSGFO4iIjEU2U1M\nZtYAZBjRH5n+QDtTzEWq2OuD4q+x2OsD1ZgPxV4fdK3GSnevaO+kyMK92JhZfS53fUWl2OuD4q+x\n2OsD1ZgPxV4fFKZGdcuIiMSQwl1EJIYU7s2mRF1AO4q9Pij+Gou9PlCN+VDs9UEBalSfu4hIDKnl\nLiISQ4kLdzMbYmYvmdkiM1toZj9K7d/bzF4ws/dSX/tGXGeZmb1hZr8v0vr2MrOnzewdM1tsZscU\nYY1Xpf6OF5jZE2bWK+oazexhM1tvZgvS9mWtycxuMLOlZrbEzE6LqL47U3/Pb5vZVDPbK6r6stWY\nduwaM3Mz6x9VjdnqM7Mfpn6PC83sjm6vz90T9QD2A0amnu8JvAscAtwBjE/tHw9MirjOq4HHgd+n\ntoutvkeB76We9wT2KqYagUHAh8Buqe2ngEuirhH4NjASWJC2L2NNqX+XbwG7AsOA94GyCOo7FShP\nPZ8UZX3ZakztHwLMJNw/07/IfocnAC8Cu6a2B3R3fQX7R12sD+B3wCnAEmC/1L79gCUR1jQY+C/g\nxLRwL6b6+qSC01rtL6YaBwErgb0JU1v/PhVSkdcIVLX6j5+xJuAG4Ia082YCxxS6vlbHzgXqoqwv\nW43A08ARwLK0cC+K3yGhcXFyhvO6rb7EdcukM7Mq4BvAa8A+7r4mdWgtsE9EZQH8HPgnYHvavmKq\nbxjQADyS6jp6yMx2p4hqdPfVwF3ACmANsNHdn6eIakyTraamN6gmq1L7ovSPwHOp50VTn5mdDax2\n97daHSqWGg8CRpvZa2b2spkdmdrfbfUlNtzNbA/gGeBKd/80/ZiHt9BIhhGZ2VnAenefl+2cKOtL\nKSd87HzQ3b8BfE7oTtgh6hpT/dZnE96IBgK7m9mY9HOirjGTYqypiZlNALYBdVHXks7MegM3AjdH\nXUsbygmfIo8GrgOeMjPrzhdMZLib2S6EYK9z99+mdq8zs/1Sx/cD1kdU3reAvzKzZcCTwIlm9lgR\n1QehdbHK3V9LbT9NCPtiqvFk4EN3b3D3rcBvgWOLrMYm2WpaTehHbjI4ta/gzOwS4CygNvUGBMVT\n31cJb+Jvpf7fDAZeN7N9KZ4aVwG/9WAO4VN5/+6sL3Hhnnq3/BWw2N3vTjs0Hfj71PO/J/TFF5y7\n3+Dug929CrgA+G93H1Ms9QG4+1pgpZkdnNp1ErCIIqqR0B1ztJn1Tv2dnwQsprhqbJKtpunABWa2\nq5kNAw4E5hS6ODM7ndBN+Ffu3ph2qCjqc/f57j7A3atS/29WEQZNrC2WGoFphIuqmNlBhEEIH3Vr\nfYW4+FFMD6CG8LH3beDN1OMMoB/hIuZ7hKvaexdBrcfTfEG1qOoDRgD1qd/jNKBvEdZ4G/AOsAD4\nDWFEQqQ1Ak8QrgFsJYTQd9uqCZhAGEGxBPhORPUtJfQLN/1/mRxVfdlqbHV8GakLqkX0O+wJPJb6\nt/g6cGJ316c7VEVEYihx3TIiIkmgcBcRiSGFu4hIDCncRURiSOEuIhJDCncRkRhSuIuIxJDCXUQk\nhv4fQW0BVLWREV4AAAAASUVORK5CYII=\n", | |
| "text/plain": [ | |
| "<matplotlib.figure.Figure at 0x24f8710d6a0>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| } | |
| ], | |
| "source": [ | |
| "plt.plot(pnts_n, pnts_q, 'ro-')\n", | |
| "plt.show()" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 19, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "10\t0.06430292129516602\t143.42119902704604\n", | |
| "20\t0.17042922973632812\t142.83896438342083\n", | |
| "30\t0.48963046073913574\t142.04123881625168\n", | |
| "40\t0.776923418045044\t141.14993333691754\n", | |
| "50\t1.0704421997070312\t140.34975785979168\n", | |
| "60\t1.514561414718628\t140.55813580788916\n", | |
| "70\t2.0883636474609375\t138.78251853848585\n", | |
| "80\t2.5483763217926025\t138.66092482047029\n", | |
| "90\t3.320828914642334\t137.51922662536322\n", | |
| "100\t4.0691139698028564\t138.2574686102402\n", | |
| "110\t4.8069376945495605\t137.42881961473122\n", | |
| "120\t5.977138519287109\t137.11342466295704\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "MAX_REPETITIONS = 500\n", | |
| "\n", | |
| "pnts_n = []\n", | |
| "pnts_t = []\n", | |
| "pnts_q = []\n", | |
| "\n", | |
| "n = 10\n", | |
| "t = 0\n", | |
| "\n", | |
| "while t<5: # in seconds; if it takes too long then stop testing\n", | |
| " t = 0\n", | |
| " expected_cycle_length = 0.71*sqrt(n) # TODO: Better estimate?\n", | |
| " sum_of_distances = 0\n", | |
| " for repetitions in range(MAX_REPETITIONS):\n", | |
| " G = random_euclidean_graph(n)\n", | |
| " t0 = time()\n", | |
| " cycle, length = greedy_nearest_neighbours(G)\n", | |
| " t1 = time()\n", | |
| " sum_of_distances += length\n", | |
| " t += t1-t0\n", | |
| " # record time and quality\n", | |
| " q = (sum_of_distances/MAX_REPETITIONS)/expected_cycle_length\n", | |
| " pnts_n.append( n )\n", | |
| " pnts_t.append( t )\n", | |
| " pnts_q.append( q )\n", | |
| " print( f\"{n}\\t{t}\\t{q}\" )\n", | |
| " n += 10" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 20, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "image/png": "iVBORw0KGgoAAAANSUhEUgAAAW4AAAD8CAYAAABXe05zAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAG1tJREFUeJzt3XmYVNWd//H3FwQUEdGABERokmDAEAXTgyhJgLgTlIlb\nVDSiGJwZf9GfcQYXzGhUVNRoGNe0NK6tjlFcggQlAhpcwGZAR4QYAW3EhVZGFltl+84fp3pomiq6\nmu5bt27V5/U8/XTXrUv39zzAh8O5ZzF3R0REkqNF3AWIiEjjKLhFRBJGwS0ikjAKbhGRhFFwi4gk\njIJbRCRhFNwiIgmj4BYRSRgFt4hIwuwSxTft2LGjl5SURPGtRUQK0vz58z91907Z3BtJcJeUlFBZ\nWRnFtxYRKUhm9n6292qoREQkYRTcIiIJo+AWEUkYBbeISMJkFdxm1sHMHjezJWa22MwOjbowERFJ\nL9se90Rgurv3Bg4CFkdXkohIwlRUQEkJtGgRPldURPrjGpwOaGZ7Aj8GRgG4+wZgQ6RViYgkRUUF\njBkDNTXh9fvvh9cAI0dG8iOz6XH3BKqBe81sgZlNMrPd699kZmPMrNLMKqurq5u9UBGRvDRu3NbQ\nrlVTE65HJJvg3gU4GLjL3fsDXwCX1r/J3cvcvdTdSzt1ymrxj4hI8lVVNe56M8gmuD8APnD3uanX\njxOCXERE9tsv/fXu3SP7kQ0Gt7t/DKwws++mLh0OvB1ZRSIiSTJs2PbX2raF8eMj+5HZ7lXyK6DC\nzFoDy4CzI6tIRCQpli8PDyf33x+++gpWrAg97fHjI3swCVkGt7svBEojq0JEJGk2bYIzzwQzeO65\nMA0wRyLZHVBEpODdcAO8/DI8+GBOQxu05F1EpPHmzYOrroLTTot0SCQTBbeISGOsXx/Cet994c47\nw1BJjmmoRESkMS66CJYuhVmzoEOHWEpQj1tEJFtPPgmTJsEll8DgwbGVoeAWEcnGhx/CL38JBx8M\nv/1trKUouEVEGrJlC5x9dtiDpKICWreOtRyNcYuINOS22+D55+Guu6B377irUY9bRGSH/vu/w5j2\nccfBeefFXQ2g4BYRyeyrr8LUvz33DA8lY5j6l46GSkREMrn88tDjfvZZ2GefuKv5P+pxi4ikM2MG\n3HornH9++h0AY6TgFhGp77PPYNQo6NMHbrop7mq2o6ESEZG63MOZkdXVYYhkt93irmg7Cm4Rkbru\nvRemTIEbb4R+/eKuJi0NlYiI1Hr3XbjgAhg6FC6+OO5qMlJwi4gAbNwIZ5wBrVrB/fdDi/yNRw2V\niIgAXHstzJ0L//mfmQ8AzhP5+0+KiEiuvPxyCO5f/AJOOSXuahqk4BaR4rZ2bRgi6dEj7EmSABoq\nEZHi9qtfQVUV/PWv0L593NVkRT1uESlejz0GDzwAV1wBhx0WdzVZU3CLSHFasSLs9nfIIfCb38Rd\nTaMouEWk+GzZAmedFaYAPvQQ7JKsUeOsqjWz94B1wGZgk7uXRlmUiEikfve7cNhveTl85ztxV9No\njflnZqi7fxpZJSIiubBgAYwbByecEI4jSyANlYhI8aipCQcjdOoEZWV5czBCY2Ub3A78xczmm9mY\nKAsSEYnM2LGweDHcdx984xtxV7PTsh0q+aG7rzSzfYAZZrbE3V+qe0Mq0McAdO/evZnLFBFpomnT\n4I474KKL4Mgj466mSczdG/cLzK4C1rv7zZnuKS0t9crKyiaWJiLSTFatgu9/Hzp3hnnzYNdd465o\nO2Y2P9uJHw0OlZjZ7ma2R+3XwFHAW00rUUQkR9xh9GhYswYefjgvQ7uxshnj7gzMMbM3gHnAs+4+\nPdqyRESaoKICSkrC1qwdO8LUqTBhAvTtG3dlzaLBMW53XwYclINaRESarqIiHD1WUxNer14dAjzB\nDyPr03RAESks48ZtDe1aW7aE/UgKhIJbRApLVVXjrieQgltECkvXrumvF9A0ZQW3iBSOxYvhyy+3\nv962LYwfn/t6IqLgFpHC8PLLMGhQOOz32mvDiTZm4XNZWVjqXiCStZehiEg6Tz4Jp58ehkOmT4ee\nPcNDygKlHreIJNudd8KJJ0K/fqHX3bNn3BVFTsEtIsnkDpdfDuefD8OHwwsvhMU2RUBDJSKSPBs3\nwrnnhvMif/nL0OtO2Ck2TaEet4gky7p1cNxxIbSvvhr+8IeiCm1Qj1tEkuTjj+GnP4U33oBJk8Lm\nUUVIwS0iyfDOO3DMMfDJJ/D00yHAi5SCW0Ty39y54QEkhEN+BwyIt56YaYxbRPLb1KkwdCi0bw+v\nvlr0oQ0KbhHJZ/fcAyNGwPe+B6+8At/5TtwV5QUFt4jkH3e46qqwr/ZRR4Xhkc6d464qb2iMW0Ty\ny6ZN8E//BOXlMGpU2GekVau4q8or6nGLSP744gv4x38MoX3FFTB5skI7DfW4RSQ/VFeHmSOVlXDX\nXaHXLWkpuEUkfkuXhjnaH3wAU6aEB5KSkYJbROJVWRkW02zaFDaKOuywuCvKexrjFpH4TJ8OQ4bA\nbruFLVkV2llRcItIPO6/P2wW1atXWFjTu3fcFSWGgltEcqOiAkpKoEUL2GuvMNVvyBB48UXo0iXm\n4pJFY9wiEr2KirCYpqYmvP78c2jZEs44Iyxll0bJusdtZi3NbIGZTY2yIBEpQOPGbQ3tWps3w5VX\nxlNPwjVmqORCYHFUhYhIAauqatx12aGsgtvMugE/BSZFW46IFJyVKzOfUNO9e25rKRDZ9rh/D4wF\ntmS6wczGmFmlmVVWV1c3S3EiknBLloQpfi1aQJs2277Xti2MHx9PXQnXYHCb2XBglbvP39F97l7m\n7qXuXtqpU6dmK1BEEuq112DQIPjqq7Ala3k59OgBZuFzWRmMHBl3lYmUzaySQcDxZjYM2BVob2YP\nufsZ0ZYmIok1bRqcdBJ07QrPPQff/jYcfLCCupk02ON298vcvZu7lwCnAjMV2iKS0X33wfHHQ58+\nYTXkt78dd0UFRwtwRKR5uMOECXD22eGosdmzdfhBRBq1AMfdZwOzI6lERJJryxb49a9h4kQ49dSw\nnL1167irKljqcYtI02zYEFZATpwIF14YVkkqtCOlJe8isvPWrYMTToC//AVuuAHGjg2zRiRSCm4R\n2TmrVsGwYbBwIdx7b9g0SnJCwS0ijbdsGRx9dFgV+fTT4SAEyRkFt4g0zoIFcOyxsHEjzJwJAwfG\nXVHR0cNJEcnezJkweHB4+DhnjkI7JgpuEcnOY4+FA327dw9L2Pv0ibuioqXgFpGG3XZbmJ99yCHw\n179Ct25xV1TUFNwikpl7OAThggtgxAh4/vlw7JjESg8nRSS9TZvgvPNg8uRw7Ngdd2TeV1tySj1u\nEdleTU1YWDN5Mvz7v8Pddyu084h+J0RkW6tXw3HHwauvwp13wj//c9wVST0KbhHZasWKsLBm6dIw\ni+Skk+KuSNJQcItIsGhRmO63dm04/GDIkLgrkgw0xi1SrCoqoKQknAf5zW/CgAHhgeRLLym085x6\n3CLFqKIizBSpqQmvP/kk7Oo3fjwcdFC8tUmD1OMWKUbjxm0N7Vru8Pvfx1OPNIqCW6QYVVU17rrk\nFQW3SLFxh/bt07/XvXtua5GdouAWKSZbtoTl62vWQMuW277Xtm0Y45a8p+AWKRYbN8JZZ8Htt8O/\n/ms40LdHj/BQskcPKCuDkSPjrlKyoFklIsXgq6/glFPgT3+C666DSy8Nga2gTiQFt0ihW7cOjj8e\nXnxRS9gLhIJbpJB9+mk4ZmzhQnjoITj99LgrkmbQYHCb2a7AS0Cb1P2Pu/uVURcmIk20ciUceSQs\nXw5PPaUDfQtINj3ur4GfuPt6M2sFzDGzP7v7axHXJiI76913Q2h/9hlMnx7OiZSC0WBwu7sD61Mv\nW6U+PMqiRKQJ3nwTjjoq7Dsyaxb84AdxVyTNLKvpgGbW0swWAquAGe4+N9qyRGSnvPpq6F23ahXO\nhlRoF6SsgtvdN7t7P6AbMMDM+ta/x8zGmFmlmVVWV1c3d50i0pAZM+CII6BjR5gzR6ewF7BGLcBx\n98+BWcAxad4rc/dSdy/t1KlTc9UnItl44onw8LFXrxDaPXrEXZFEqMHgNrNOZtYh9fVuwJHAkqgL\nE5EsTZ4cFtf8wz/A7NnQuXPcFUnEsulxdwFmmdmbwOuEMe6p0ZYlIlm55RYYPTrMIHn+eejQIe6K\nJAeymVXyJtA/B7WISLbcw+nr114LJ58cFte0bh13VZIjWjkpkjRbtsCFF4bNokaPhj/8Yfud/qSg\naXdAkSSpv8PfPfcotIuQetwiSZFphz8pOgpukSTQDn9Sh4JbJN/V7vC3YIF2+BNAwS2S3+rv8Dd8\neNwVSR5QcIvkK+3wJxloVolIvqiogJISaNECunYNG0StWxd2+FNoSx3qcYvkg4oKGDMGamrC648+\nCjNGJkzQDn+yHfW4RfLBuHFbQ7uWO9xxRzz1SF5TcIvEzR2qqtK/l+m6FDUFt0icXnkFBg0K4Z1O\n9+65rUcSQcEtEoelS8PmUIMGwXvvwbnnQtu2297Tti2MHx9LeZLfFNwiubR6Nfz61+F0mmnT4Kqr\n4J13wp4jZWXhAASz8LmsDEaOjLtiyUOaVSKSC19/HZaqX3MNrFkD55wDV18NXbpsvWfkSAW1ZEU9\nbpEoucMf/wgHHBB62gMGwMKFoYddN7RFGkHBLRKVV18NY9innAK77x5WP06fDt//ftyVScIpuEWa\n29KlIawPOyw8eCwvDxtEHX103JVJgdAYt0hzWb06HCV2++3QqlV48HjxxdCuXdyVSYFRcIs0Vd0H\nj59/vvXBY9eucVcmBUpDJSI7yx0ef3z7B4+TJim0JVIKbpGdUfvg8eSTt33weOCBcVcmRUDBLbIj\ndbdaLSmBW2/d+uBx+fLQu9aDR8kxjXGLZFJ/q9X33w9DIq1awZVXhlPW9eBRYqDgFskk3VarAPvs\nE2aMiMSkwaESM9vPzGaZ2dtmtsjMLsxFYSKxy7Sl6ocf5rYOkXqy6XFvAi529/8ysz2A+WY2w93f\njrg2kXi4wwMPZH5fW61KzBrscbv7R+7+X6mv1wGLgX2jLkwkFtXVcOKJMGoU7L8/7Lbbtu9rq1XJ\nA42aVWJmJUB/YG6a98aYWaWZVVZXVzdPdSK5NHVq2Efk2Wfhpptg0aKwGZS2WpU8Y57p5I36N5q1\nA14Exrv7lB3dW1pa6pWVlc1QnkgOrF8flqaXlYV52A8+qPnYknNmNt/dS7O5N6set5m1Ap4AKhoK\nbZFEeeUV6Ncv9KzHjoV58xTakveymVViQDmw2N1vib4kkRzYsCFM9/vRj2DzZpg9GyZMgDZt4q5M\npEHZ9LgHAWcCPzGzhamPYRHXJRKdt9+GgQPhuuvCQ8g33oAf/zjuqkSy1uB0QHefA1gOahGJ1pYt\n8B//AZdeCu3bw1NPwYgRcVcl0mhaOSnFoaoKzj4bZs6E444LY9qdO8ddlchO0SZTUtjc4aGHwgPH\nefNCYD/9tEJbEk3BLYXrs8/g5z+HM8+Evn3DWPa554Y52SIJpuCWwlR7KO9TT8H118OLL8K3vhV3\nVSLNQsEtheWLL+Bf/gWOPRb23jsMj1x6KbRsGXdlIs1GwS2FY+5c6N8f7r47rISsrAyLa0QKjIJb\nkm/jxnCwwaBB4eDemTPh5pth113jrkwkEgpuSZb6R4nddFM4Ruzqq8PmT2++CUOGxFykSLQ0j1uS\nI91RYmPHhsN6H388bMcqUgTU45bkyHSUWIcOCm0pKgpuSQ4dJSYCaKhEkqCmBm67LfP7OkpMiox6\n3JK/Nm0KS9R79QpzsQ86aPuZIjpKTIqQglvyjztMmRKWqY8ZE44Me+klWLAAJk3SUWJS9DRUIvll\n9uzQu547F/r0CUvWjz9+6/4iI0cqqKXoqcct+eGNN2DYMBg6FFauhPLyMCd7xAhtCiVSj4Jb4rV8\nedi9r39/eO01uPFGeOcdOOcc2EX/IRRJR38zJB7V1XDttXDXXWEDqEsuCYtp9tor7spE8p6CW3Jr\n/Xq45Zawl0hNTehZX3kl7Ltv3JWJJIaCW3Jjw4Ywte/qq2HVKjjhhDCNr3fvuCsTSRwFt0RryxZ4\n7LGwXH3ZMhg8GJ55Bg45JO7KRBJLDyclOjNmQGkpnHYatGsH06bBrFkKbZEmUnBL09TfZrWiIhxg\ncMQRcNRR8D//Aw8+GBbPHHuspvaJNAMNlcjOS7fN6llnwebN0LEjTJwI550HbdrEW6dIgWkwuM1s\nMjAcWOXufaMvSRIj3TarmzfDnnvC0qXQvn08dYkUuGyGSu4Djom4DkmaqqrQw05n7VqFtkiEGgxu\nd38JWJ2DWiTfrV4dNnUaPDhs8JSJtlkViZTGuGXHvvwS/vSnMJ795z+Hg3l794ZrrglHhl1xxbbD\nJdpmVSRyzRbcZjYGGAPQXT2uZNu0KZyU/vDDYXvVdeuga1e44AI4/fSwr0jt7JB99glj3VVVoac9\nfrx27xOJmLl7wzeZlQBTs304WVpa6pWVlU2rTHLLPUzjq6iARx+FTz4JDxlPPDEE8eDBYU8REYmE\nmc1399Js7tVQSbH7+99DWD/8cPi6dWsYPjyE9bBh2584IyKxy2Y64CPAEKCjmX0AXOnu5VEXJhH6\n+OPQq374YXj99TDsMXRoOMDghBPCqekikreymVVymrt3cfdW7t5NoZ0A6VYzrl0L998fVjPuuy9c\ndFEYy775ZlixAl54IezUp9AWyXsaKik0mVYzmoWg7tkTLr88PGTs0yfeWkVkpyi4C83ll6dfzdiu\nHTz/PAwcqP1CRBJOwV0I3MNY9SOPhGl56XzxBRx6aG7rEpFIKLiTbNGiENaPPhr2BmndGnbbLSya\nqU9z60UKhrZ1TZply+C66+DAA6FvX7j+evjWt2Dy5DD3+p57wurFurSaUaSgqMedBB99FE6ReeQR\nmDs3XDvsMLjtNjj5ZOjceeu9tasWtZpRpGApuPPV6tXwxBMhrGfPDuPY/frBhAnw85/veJOnkSMV\n1CIFTMGdT9avD+cxPvIIPPdc2NCpVy/4zW/g1FM1fU9EAAV3/L7+Ouy69+ijIbS//BK6dQsbOp12\nGhx8sKbvicg2FNy5UFGx7ZjzNdfAN78ZetZTpsCaNeGor1GjQlgPGhRWPYqIpKHgjlq6lYy/+EX4\neo894Gc/C2F9+OHQqlV8dYpIYii4o3bJJduvZITQw66qCvOuRUQaQf8fj8KGDWFGyLBhsHJl+ns+\n+0yhLSI7RT3u5rRoEZSXw4MPwqefhl342rcPO/PVp5WMIrKT1ONuqrVrw2rFgQPDSsbbbw+nxUyb\nFsaz77xTKxlFpFmpx70z3GHOnNC7/uMfwxj2AQfA734HZ54JnTptvVcrGUWkmSm4G+Ojj8JhBJMn\nh2O+9tgjBPDo0TBgQOb51lrJKCLNSMHdkI0bw7BHeXn4vHkz/OhHoQd90kmw++5xVygiRUbBncmS\nJaFn/cADYde9Ll3g3/4Nzj4b9t8/7upEpIgV58PJdGcyQtgrZPJk+OEPw74gt94aDh945pkwPn39\n9QptEYld8fW4061kHD06zAyZPz+E93e/CzfeGFY41t0yVUQkDxRfcKc7k/Hrr+Gll8IwyOjRoZet\njZ1EJE8VXnBv3gwffgjLl2/9eO+9rV+vWJH515aX56xMEZGdlT/BXX8HvUxznd2hunrbYK4b0O+/\nH2aC1DKDrl2hZ08YMiSMV69Zs/331UpGEUmIrILbzI4BJgItgUnufkOzVpFu3Pncc6GyEvbbb/tw\nrj/U0alTCOYf/ABOPDF8XfvRvTu0aZP5Z4FWMopIopi77/gGs5bAO8CRwAfA68Bp7v52pl9TWlrq\nlZWV2VdRUhLCOpP27bcN49qPkpLw0a5d9j8Lsu/di4jkiJnNd/fSbO7Npsc9AHjX3ZelvvmjwAgg\nY3A3WlVV+utmYRe9vfZqth8FaCWjiCRaNvO49wXqPtH7IHWt+WQaX+7evflDW0Qk4ZptAY6ZjTGz\nSjOrrK6ubtwvHj9eO+iJiGQpm+BeCexX53W31LVtuHuZu5e6e2mnurvjZWPkSCgrgx49wvBIjx7h\ntYYzRES2k80Y9+tALzPrSQjsU4HTm70SjTuLiGSlweB2901m9v+A5wjTASe7+6LIKxMRkbSymsft\n7tOAaRHXIiIiWSjO3QFFRBJMwS0ikjAKbhGRhGlwyftOfVOzamAHa9jzRkfg07iLiFAht09tS65C\nbl9T2tbD3bOaSx1JcCeFmVVmuzdAEhVy+9S25Crk9uWqbRoqERFJGAW3iEjCFHtwl8VdQMQKuX1q\nW3IVcvty0raiHuMWEUmiYu9xi4gkTtEEt5ntZ2azzOxtM1tkZhemru9tZjPM7O+pz4ndANzMWprZ\nAjObmnpdSG3rYGaPm9kSM1tsZocWSvvM7KLUn8m3zOwRM9s1qW0zs8lmtsrM3qpzLWNbzOwyM3vX\nzP5mZkfHU3X2MrTvptSfyzfN7Ekz61DnvUjaVzTBDWwCLnb3A4CBwPlmdgBwKfCCu/cCXki9TqoL\ngcV1XhdS2yYC0929N3AQoZ2Jb5+Z7QtcAJS6e1/CRm6nkty23QccU+9a2rak/v6dCnwv9WvuTB2V\nmM/uY/v2zQD6uvuBhGMeL4OI2+fuRfkBPE04R/NvQJfUtS7A3+KubSfb043wl+InwNTUtUJp257A\nclLPZOpcT3z72HrC1N6ETd+mAkcluW1ACfBWQ79PqYC7rM59zwGHxl1/Y9tX772fARVRt6+Yetz/\nx8xKgP7AXKCzu3+UeutjoHNMZTXV74GxwJY61wqlbT2BauDe1FDQJDPbnQJon7uvBG4GqoCPgDXu\n/jwF0LY6MrUl+mMRc+8c4M+pryNrX9EFt5m1A54A/r+7r637nod/FhM3zcbMhgOr3H1+pnuS2raU\nXYCDgbvcvT/wBfWGDpLavtR47wjCP05dgd3N7Iy69yS1bekUUlvqM7NxhCHZiqh/VlEFt5m1IoR2\nhbtPSV3+xMy6pN7vAqyKq74mGAQcb2bvAY8CPzGzhyiMtkHoqXzg7nNTrx8nBHkhtO8IYLm7V7v7\nRmAKcBiF0bZamdqS1bGISWBmo4DhwMjUP04QYfuKJrjNzIByYLG731LnrWeAs1Jfn0UY+04Ud7/M\n3bu5ewnhYchMdz+DAmgbgLt/DKwws++mLh0OvE1htK8KGGhmbVN/Rg8nPHgthLbVytSWZ4BTzaxN\n6mjEXsC8GOprEjM7hjBMeby719R5K7r2xT3Qn8MHCj8k/BftTWBh6mMY8A3CQ72/A38B9o671ia2\ncwhbH04WTNuAfkBl6vfvKWCvQmkf8FtgCfAW8CDQJqltAx4hjNVvJPxPafSO2gKMA5YSHmAeG3f9\nO9m+dwlj2bW5cnfU7dPKSRGRhCmaoRIRkUKh4BYRSRgFt4hIwii4RUQSRsEtIpIwCm4RkYRRcIuI\nJIyCW0QkYf4X3GmNLIbrjy8AAAAASUVORK5CYII=\n", | |
| "text/plain": [ | |
| "<matplotlib.figure.Figure at 0x24f8382db38>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| } | |
| ], | |
| "source": [ | |
| "plt.plot(pnts_n, pnts_t, 'ro-')\n", | |
| "plt.show()" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 22, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXoAAAD8CAYAAAB5Pm/hAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XmUVNW5/vHv2wxKYzRcmVSG5ucYFVTSAioqigIiguJI\nGmMURa9KEuNwRVSMBmPEqIkzCuJQQpQEB5IYjSRR1OhtEAScUZpBCa3EqCAo8P7+2NWXounqsapP\n1enns1avrjp1uurdS3x69z777G3ujoiIxFdB1AWIiEh2KehFRGJOQS8iEnMKehGRmFPQi4jEnIJe\nRCTmFPQiIjGnoBcRiTkFvYhIzDWPugCAtm3belFRUdRliIjklblz537q7u1qOi8ngr6oqIjS0tKo\nyxARyStmVlab8zR0IyIScwp6EZGYU9CLiMScgl5EJOYU9CIiMZffQZ9IQFERFBSE74lE1BWJiOSc\nnJheWS+JBIweDevWhedlZeE5QElJdHWJiOSY/O3Rjxu3JeQrrFsXjouIyP/J36Bftqxux0VEmqj8\nDfouXao+vuuujVuHiEiOy9+gnzABCgu3Pf7ZZzB5Mrg3fk0iIjkof4O+pAQmTYKuXcEsfL/1Vujd\nG849FwYODBdoRUSauPwNeghhv3QpbN4cvl9yCcyeDXfdBa+8AvvvD/fcE14XEWmi8jvoq1JQABde\nCIsWQZ8+4XH//vDhh1FXJiISifgFfYWiInjuObj/fpg3D7p3h9/+Vr17EWly4hv0EMbuzz0XFi+G\nfv3gJz+BI46A996LujIRkUYT76Cv0KkTzJoFDz0UQv+AA+CWW2DTpqgrExHJuqYR9BB69z/8Ibz1\nVpiRc/nlcOih4bmISIzVGPRmNsXMVpvZoipeu9TM3MzaJp/3MrP5ya8FZnZSNopukF12gZkz4bHH\nYMkSOOgguPFG2Lgx6spERLKiNj36qcCgygfNrDMwAEhdc2ARUOzuByZ/5j4zy72F08xgxIgwjDNs\nWFgfp3dvePPNqCsTEcm4GoPe3V8E1lTx0m3AFYCnnLvO3Su6xtunvpaTOnSAxx+HGTNgxQooLoaf\n/xy++SbqykREMqZeY/RmNgxY6e4Lqnitt5ktBhYCF6QEf+XzRptZqZmVlpeX16eMzDn55NC7P/VU\nuO46OPjgMCVTRCQG6hz0ZlYIXAVcW9Xr7v6au+8HHAyMNbPt05w3yd2L3b24Xbt2dS0j89q2DWvc\nP/UUlJdDr15hSGfDhqgrExFpkPr06HcHugELzGwp0AmYZ2YdU09y97eBr4D9G1pkoxo6NPTuR44M\nF2l79oTXX9duViKSt+p8odTdFwLtK54nw77Y3T81s27AcnffaGZdgX2ApRmqtfG0aQNTp8Lpp4dd\nq3r3hubNt8zM0W5WIpJHajO9chrwKrC3ma0ws1HVnN6X0NOfD8wELnT3TzNTagSOOy6smbPDDttO\nv9RuViKSJ2rs0bv7iBpeL0p5/AjwSMPLyiE77QRr11b9mnazEpE80HTujG2IdLtZpTsuIpJDFPS1\nkW43q3331WqYIpLzFPS1UXk3qy5dYMAA+POfw/o5usFKRHKYgr62UnezKiuDZ58N0y8TCTjhBPjy\ny6grFBGpkoK+vsxg7FiYMgVeeAGOPhpWr466KhGRbSjoG+rss+HJJ8NNVocdpi0LRSTnKOgzYciQ\n0KtfsyascT9/ftQViYj8HwV9phxyCMyZAy1bhu0K//a3qCsSEQEU9Jn1ve/BK6+EWTmDBsETT0Rd\nkYiIgj7jOnWCl14Kq1+efjrceWfUFYlIE6egz4Y2beC558JKmGPGwNVXg+f2HiwiEl8K+mxp1Srs\nXHXeeeHO2vPO0760IhKJ3NvPNU6aN4f77oOOHeGGG8I8++nTq15OQUQkS9SjzzYzuP56uPtumDUL\njj02TMMUEWkkCvrG8t//HTYiLy2Fvn1h+fKoKxKRJkJB35hOOQX+8hdYuTLcWLV4cdQViUgToKBv\nbP36wYsvhguzhx8OL78cdUUiEnMK+igccEC4saptWzjmGHj66agrEpEYU9BHpVu30Jvv3h1OOgkm\nT466IhGJKQV9lNq1g9mzw0ycc88N8+11Y5WIZJiCPmo77ADPPAMjR4Y7aMeMgU2boq5KRGJEQZ8L\nWrSAhx6Cyy6Du+6CM84Iz4uKoKAgfE8koq5SRPJUjUFvZlPMbLWZLaritUvNzM2sbfL5sWY218wW\nJr8fnY2iY6mgACZOhF//OiydcM45YctC9/B99GiFvYjUS2169FOBQZUPmllnYACwLOXwp8AJ7t4d\nOAt4JAM1Ni0/+xnsvHPYmzbVunUwblw0NYlIXqsx6N39RaCqe/ZvA64APOXcN9z94+TTxUArM9su\nE4U2KemWSFi2rOrjIiLVqNcYvZkNA1a6+4JqTjsZmOfuG+pVWVPWpUvdjouIVKPOQW9mhcBVwLXV\nnLMf8Cvg/GrOGW1mpWZWWl5eXtcy4m3ChG1XuDSDK66Iph4RyWv16dHvDnQDFpjZUqATMM/MOgKY\nWSdgJvBDd1+S7k3cfZK7F7t7cbt27epRRoyVlMCkSdC1awj4Dh3Cksd33QX/+lfU1YlInqlz0Lv7\nQndv7+5F7l4ErAB6uvsqM/su8EfgSnfXIi4NUVICS5eGi7KrVsHzz4fn/fuHde1FRGqpNtMrpwGv\nAnub2QozG1XN6RcDewDXmtn85Ff7DNXatB15ZFjP/sMPw/o4Gu4SkVoyz4Fb7ouLi720tDTqMvLD\nCy/AkCGw117hcdu2UVckIhExs7nuXlzTebozNt/07x+WTHjvvdCz/+yzqCsSkRynoM9HxxwDTz0F\n77yjrQlFpEYK+nw1YAA8+WTYperYY+Hf/466IhHJUQr6fDZoEMycCYsWheD//POoKxKRHKSgz3eD\nB8Pvfw8LFoSw/89/oq5IRHKMgj4OhgwJYT9/PgwcCF98EXVFIpJDFPRxccIJ8MQTMHduGNJR2ItI\nkoI+ToYNg8cfh//9XzjuOPjyy6grEpEcoKCPm5NOgunT4bXXwvj9V19FXZGIRExBH0cnnwzTpsGr\nryrsRURBH1unnhq2Hnz55XCxdu3aqCsSkYgo6OPs9NPh0UfhpZfCxdp166KuSEQioKCPuxEj4OGH\n4R//gKFD4euvo65IRBqZgr4pKCmBqVNh9uwwM0dhL9KkKOibijPPhAcfhL/+FU48Edavj7oiEWkk\nCvqm5KyzYPLksFvVSScp7EWaCAV9U3P22XD//fDss2Ea5oYNUVckIlmmoG+KRo2C++6DP/0JTjlF\nYS8Scwr6pmr0aLj33rAP7WmnwUMPQVERFBSE74lE1BWKSIY0j7oAidD558OmTXDRRfDHP4bHAGVl\n4RcBhBk7IpLX1KNv6i68ENq02RLyFdatg3HjoqlJRDJKQS/pd6Zatqxx6xCRrKgx6M1sipmtNrNF\nVbx2qZm5mbVNPt/ZzP5mZl+Z2Z3ZKFiyoEuXuh0XkbxSmx79VGBQ5YNm1hkYAKR2+9YD1wCXZaI4\naSQTJkBh4dbHzOCSS6KpR0Qyqsagd/cXgTVVvHQbcAXgKeeudfc5hMCXfFFSApMmQdeuIeA7dIDt\nt4ebb4aFC6OuTkQaqF5j9GY2DFjp7gsyXI9EpaQEli6FzZth1Sp4/fVw/PDDw+qXIpK36hz0ZlYI\nXAVc25APNrPRZlZqZqXl5eUNeSvJhv33h1degY4dYcAAeOqpqCsSkXqqT49+d6AbsMDMlgKdgHlm\n1rEub+Luk9y92N2L27VrV48yJOu6doU5c+CAA2D4cHjggagrEpF6qHPQu/tCd2/v7kXuXgSsAHq6\n+6qMVyfRa9sWXngBBg6E886DX/wC3Gv+ORHJGbWZXjkNeBXY28xWmNmoGs5fCtwK/Ch5/r4ZqVSi\n07p1GLo580y45hoYM2bbG6xEJGfVuASCu4+o4fWi6p5LTLRoETYv6dABbrkFVq+GRx6B7baLujIR\nqYHWupHaKyiAiRPDBdrLLoPPPoOZM2HHHaOuTESqoSUQpO4uvTT05l98Efr1C9MxRSRnKeilfkaO\nhGeegXffhcMOgyVLoq5IRNJQ0Ev9DRoUNhz/z3/g0ENh3ryoKxKRKijopWF694aXXw5LJhx5ZJiK\nKSI5RUEvDbf33uEu2qIiOO44ePzxqCsSkRQKesmM3XYLF2f79IEzzoA7c2iV6kRC2yRKk6agl8xp\n0wb+8hcYOjTcVHX11dHfRZtIhG0Ry8pCLRXbJCrspQlR0EtmtWoFM2aE5RImTAjfN26Mppavvw5T\nQdet2/q4tkmUJkY3TEnmNW8O990Xbqy64QYoL4fp08MvgWxasyZcGJ4zJyytXFoK335b9bnaJlGa\nEAW9ZIcZXH99WDJhzJiw1PHTT4fhnUwpK9sS6nPmwOLF4XiLFnDwwWGHrAcfDL9oKtM2idKEKOgl\nuy66CNq3DzdYHXEEPPtsuHBbV5s3hyCvCPU5c2D58vDajjuGefwjRoSNUg4+eMtfDz16hDH51OGb\nVq3CsJJIE6Ggl+w79VTYeWc48cQQyBdfDHfdFYZPunQJoVtSsvXPbNgQhl4qgv3ll+Hzz8Nru+wS\nAv2KK6BvX+jeHZo1q/qzK9533Ljwee5w/PHbfp5IjJlHPSsCKC4u9tLS0qjLkGx7442wNs4XX2x9\nvLAQbr899PQreuuvvx7CHmCffUKw9+0bvrp1C0ND9TF0aHj/pUu1GJvkPTOb6+7FNZ6noJdGtdtu\n8PHH6V9v3hx69twS7IcdBpncgWzuXCguDhuoaOaN5LnaBr2GbqRxffJJ+tdeeCEsqdC6dfY+//vf\nhyFD4NZb4cc/hu98J3ufJZIjNI9eGle62S5du8LRR2c35CuMHx+mYubS3bsiWaSgl8Y1YUIYk09V\nWNi4s2CKi2Hw4LBT1pdfNt7nikREQS+Nq6QEJk0KPXiz8H3SpMafBVPRq7/rrsb9XJEI6GKsNF2D\nB4fZPUuXwg47RF2NSJ3V9mKsevTSdI0fH/a9vfvuqCsRySoFvTRdvXvDwIFhw/Ovvoq6GpGsUdBL\n0zZ+PHz6KdxzT9SViGRNjUFvZlPMbLWZLaritUvNzM2sbcqxsWb2gZm9a2YDM12wSEYdckhYcG3i\nRFi7NupqRLKiNj36qcCgygfNrDMwAFiWcmxf4Axgv+TP3G1maRYhEckR48eHFS7Vq5eYqjHo3f1F\nYE0VL90GXAGkTtsZBkx39w3u/hHwAdArE4WKZM2hh8Ixx4RefeVNSkRioF5j9GY2DFjp7gsqvbQb\nsDzl+YrksareY7SZlZpZaXlV64WLNKbx42H1arj33qgrEcm4Oge9mRUCVwHXNuSD3X2Suxe7e3G7\nTC5aJVIffftC//7wq1+pVy+xU58e/e5AN2CBmS0FOgHzzKwjsBLonHJup+QxkdxX0au/776oKxHJ\nqDoHvbsvdPf27l7k7kWE4Zme7r4KeBo4w8y2M7NuwJ7A6xmtWCRbDj88LKx2881hY3GRmKjN9Mpp\nwKvA3ma2wsxGpTvX3RcDjwNvAc8CF7n7pkwVK5J148fDqlVh/R2RmNBaNyKVHXUUvPMOfPjhlr1n\nRXKQ1roRqa+KXv3990ddiUhGKOhFKuvXD448Em66Cdavj7oakQZT0ItUZfz4sO2hevUSAwp6kar0\n6xdm4ahXLzGgoBepihlcdx18/DFMnhx1NSINoqAXSeeoo8Ids7/8JWzYEHU1IvWmoBdJxyyM1a9c\nqV695DUFvUh1+vcPq1uqVy95TEEvUp2KsfoVK+DBB6OuRqReFPQiNTnmmLAT1Y03qlcveUlBL1KT\nirH65cth6tSoqxGpMwW9SG0MGAB9+oRe/TffRF2NSJ0o6EVqo6JXv2yZevWSdxT0IrU1cCD06qVe\nveQdBb1IbVX06svK4OGHo65GpNYU9CJ1cdxxcPDBMGECfPtt1NWI1IqCXqQuKnr1S5eqVy95Q0Ev\nUleDB0NxsXr1kjcU9CJ1ZQbXXgsffQSPPhp1NSI1UtCL1MeQIdCzJ/ziF+rVS85T0IvUR8VY/Ycf\nQiIRdTUi1VLQi9TXCSfAQQeFXv3GjVFXI5JWjUFvZlPMbLWZLUo5doOZvWlm883sOTPbNXm8pZk9\naGYLzWyBmfXLYu0i0aro1S9ZAo89FnU1ImnVpkc/FRhU6dhEd+/h7gcCs4Brk8fPA3D37sCxwK/N\nTH81SHwNHQoHHgg33KBeveSsGkPY3V8E1lQ69kXK09aAJx/vC8xOnrMa+BwozkilIrmoYgbOBx/A\ntGlRVyNSpXr3ts1sgpktB0rY0qNfAAw1s+Zm1g34PtC54WWK5LBhw6BHD43VS86qd9C7+zh37wwk\ngIuTh6cAK4BS4HbgFWBTVT9vZqPNrNTMSsvLy+tbhkj0CgrCWP1778H06VFXI7INc/eaTzIrAma5\n+/5VvNYF+FOa114BznX3t6p7/+LiYi8tLa1tzSK5Z/PmMFb/zTeweDE0axZ1RdIEmNlcd69xeLxe\nPXoz2zPl6TDgneTxQjNrnXx8LLCxppAXiYWCgjBW/+678LvfRV2NyFaa13SCmU0D+gFtzWwFMB4Y\nbGZ7A5uBMuCC5Ontgb+Y2WZgJXBmNooWyUnDh8P++8P118Ppp6tXLzmjxqB39xFVHJ6c5tylwN4N\nrEkkP1X06k87DTp2hM8+gy5dwuJnJSVRVydNWI1BLyJ1sGFDmHL56afheVkZjB4dHivsJSIKepFM\nuvpqqDzBYd06uOACWL4cdt99y9dOO0VTozQ5CnqRTFq2rOrjX30FY8dufaxt2xD4e+yx9S+APfaA\n9u3DXwY1SSRg3LjwuRomkjQU9CKZ1KVLGK6prGtXWLgwrHa5ZEm4k3bJkvD18svhrtrNm7ec37r1\n1sGf+rhz53ChN5EIw0Lr1oWf0TCRpFGrefTZpnn0EhuVwxegsBAmTao+fL/5JmxPWBH+qb8IPvww\njP1XaNECiorCUND69du+V9eu4b0k9mo7j149epFMqgjzug6ntGwJe+0VvirbvBlWrtwS/BW/CN5/\nv+r3Sjd8JE2WevQi+aqoKP0wkXr0TUJW74wVkRwwYUIYFkpVUBBu2BJJoaAXyVclJWHsv2vXMEOn\nbdswzPPGG1FXJjlGQS+Sz0pKwjDN5s1QXg4//jHcfjs8/njUlUkOUdCLxMnEiXDIITBqFLz9dtTV\nSI5Q0IvEScuWoTffqhWcfHK4UUuaPAW9SNx06hRuwHr3XTjvvG2XZJAmR0EvEkf9+4etDadPhzvv\njLoaiZiCXiSu/ud/4IQT4Gc/g1dfjboaiZCCXiSuCgrgoYfC3bmnngqrV0ddUd0lEuHGsIKC8D2R\niLqivKSgF4mzNm3g978Pm6CMGAGbNkVdUe1VrBtUVhauM1Qs2qawrzMFvUjcHXgg3H03zJ4ddsDK\nF+PGbb04HITn48ZFU08eU9CLNAVnnw3nngs33gjPPBN1NbWTbnE2LdpWZwp6kabijjugZ08488yw\n9HEuSyTSTwvt0qVxa4kBBb1IU7H99jBjRlgX5+ST4euvo65oW5s3h6GZkSNhn33CjV+VnXJK49eV\n5xT0Ik1Jt27w6KMwfz5cfHHU1Wxt7dowO+jGG8Mw04IFcP/9WxZt69Qp1P+b34QbwqTWagx6M5ti\nZqvNbFHKsRvM7E0zm29mz5nZrsnjLczsITNbaGZvm9nY9O8sIpE4/viwifmUKTB5ctTVBCtWwOGH\nw5NPwq23hlU5W7bcetG25cvDL6hDDw3H77sv6qrzRm169FOBQZWOTXT3Hu5+IDALqLiUfyqwnbt3\nB74PnG9mRZkpVUQy5rrr4Jhj4KKLol/W+PXX4eCDw65ZTz8Nl1ySfmP0HXeEZ5+F446DCy6Am29u\n3FrzVI1B7+4vAmsqHfsi5WlroOKqiQOtzaw50Ar4Bkg9V0RyQbNm8Nhj0K5dGK//97+jqeN3v4Mj\njwzXD155Jfy1UZNWrWDmTDj99HD371VXaT2fGtR7jN7MJpjZcqCELT36GcBa4BNgGXCLu69J8xYi\nEqV27eCJJ8KwyQ9/GIZHGot7+KvijDOguDj06vffv/Y/37LllhuqfvnL8JdJY9afZ+od9O4+zt07\nAwmg4qpOL2ATsCvQDbjUzP5fVT9vZqPNrNTMSsvLy+tbhog0RJ8+cNttMGsW3HRT43zm11+HgP/5\nz+FHP4K//jX80qmrZs3g3nvh8svhnnvCL6tvv814uXGQiVk3CeDk5OMfAM+6+7fuvhp4Gahy41p3\nn+Tuxe5e3K4+/5FFJDMuvBB+8AO45poQutn08cdwxBHhL4mbbw4XhLfbrv7vZwa/+lXYPzeRCFMv\n16/PXL0xUa+gN7M9U54OA95JPl4GHJ08pzXQJ+U1EclFZmGWy/e+F9bDWbEiO58zd2646Pr222F2\nzeWXp7/oWhdmYZz+zjvDxdzjj4cvv2z4+8ZIbaZXTgNeBfY2sxVmNgq4ycwWmdmbwADgJ8nT7wJ2\nMLPFwP8CD7r7m1mqXUQypXXrsPjZ+vVhLvs332T2/WfMCNMnmzcPF12HDs3s+0MYp3/4YfjHP+DY\nY2GNLg9WMM+Bq9XFxcVeWloadRkiMmNGCPoxY+C3v234+7mHYZVrrgl72c6cCR06NPx9q/Pkk2FG\nzl57wXPPwS67ZPfzImRmc929yuHxVLozVkS2OOWUsFHJHXc0/O7T9evDUgbXXBO+z56d/ZAHOPFE\n+NOf4KOPwl8RS5dm/zNznIJeRLZ2003Qt29YhmDx4vq9x6pV0K9fmKt/441hSGX77TNaZrX694fn\nnw/r8PftG64LNGEKehHZWosW4Uam73wn3ExV1wubCxZAr16wcGEY9x87NjMXXevqkEPCeP3GjWGm\nz7x5jV9DjlDQi8i2dt01hP0HH8CoUbW/8/TJJ+Gww8L5c+bA8OHZrbMmPXrASy9BYSEcdVR43AQp\n6EWkakceGe46feKJsGJkddzDfPbhw2G//cKdrgcd1Dh11mTPPcMvnV12gYEDw1o5TYyCXkTSu+yy\ncHHz8stDWFZlw4Zwh+uVV4bZLn//e+7NdOncOfTm99knTO184omoK2pUCnoRSc8Mpk6FoiI47TT4\n17+2fn316nDh8+GH4frrw8XXqjYLyQXt2oWZP716hSUYcmWJ5kbQPOoCRCTH7bRTuKjap08Y5167\nNqwN37FjuLFq3Tp4/PEw/z7Xffe7YW798OFhVtEXX4RlkWNOPXoRqVmPHnDWWWGa4rJlYUz+k0/C\n3adjx+ZHyFcoLAxLJVTcMzB+fOyXOVbQi0jt/PnP2x5zz88hkJYtYfp0OOecMOT005/GepljBb2I\n1M6yZXU7nuuaNQt70v70p2G5h379wv60BQXhmkQiEXWFGaMxehGpnS5doKys6uP5qqAg7FG7bBn8\n4Q9bjpeVhU1NIOxPm+fUoxeR2pkwIYxvpyosDMfzmVlYQrmydetg3LjGrycLFPQiUjslJWHd+q5d\nQzh27Rqex6DHm3b4qawsLKOQ5+P3WqZYRKSoqOphKbNwwblz57AL18iRddvbNsu0TLGISG2lG5Z6\n4IFwUbZ7d7jllvD9gANg4sTs7cSVBQp6EZF0w1LnnBN68n/8Y9jv9o47wp2/V1wRLkIffXSYXvr5\n51G3oFoauhERqasPPgg9/UQC3n8/bHA+ZEj4hTF4cMM2PK8DDd2IiGTLHnuEO2rffRdeew3OPz8s\nmjZ8eFgaYvTonLqIq6AXEakvs7BI2m9+AytXhruHhwwJi7v16xcu8l55JSxaFGmZCnoRkUxo3hwG\nDYJHHgmrfCYSYYZOuou4iUT4RdAId+JqjF5EJJtWrw67dSUSYZjHLKyLv2RJWP2zQmFhne9L0Bi9\niEguaN8exoyBf/4T3nsvjO2///7WIQ9ZvRO3xqA3sylmttrMFqUcu8HM3jSz+Wb2nJntmjxekjxW\n8bXZzA7MSuUiIvlmzz1D0G/aVPXrWVogrjY9+qnAoErHJrp7D3c/EJgFXAvg7gl3PzB5/EzgI3ef\nn8mCRUTyXrqF4LK0QFyNQe/uLwJrKh37IuVpa6Cqgf4RwPQGVSciEkeNvEBcvcfozWyCmS0HSkj2\n6Cs5HZhWzc+PNrNSMystLy+vbxkiIvmnkReIq9WsGzMrAma5+zar+ZjZWGB7dx+fcqw38IC7d69N\nEZp1IyJSd4056yYBnFzp2BlU05sXEZHGU6+gN7M9U54OA95Jea0AOA2Nz4uI5IQatxI0s2lAP6Ct\nma0AxgODzWxvYDNQBlyQ8iNHAMvd/cPMlysiInVVY9C7+4gqDqfd9t3d/w70aUBNIiKSQbozVkQk\n5nJirRszKycMAeWDtsCnUReRRXFun9qWv+Lcvoa0rau7t6vppJwI+nxiZqW1mc6Ur+LcPrUtf8W5\nfY3RNg3diIjEnIJeRCTmFPR1NynqArIszu1T2/JXnNuX9bZpjF5EJObUoxcRiTkFfTXMrLOZ/c3M\n3jKzxWb2k+Tx/zKz583s/eT3NlHXWl9m1szM3jCzWcnnsWibmX3XzGaY2Ttm9raZHRKjtl2S/Pe4\nyMymmdn2+dy2NJsbpW2PmY01sw/M7F0zGxhN1bWTpm0Tk/8u3zSzmWb23ZTXstI2BX31NgKXuvu+\nhLt9LzKzfYErgRfcfU/gheTzfPUT4O2U53Fp22+AZ919H+AAQhvzvm1mthvwY6A4uZpsM8Iigvnc\ntqlsu7lRle1J/v93BrBf8mfuNrNmjVdqnU1l27Y9D+zv7j2A94CxkN22Keir4e6fuPu85OMvCWGx\nG2Eht4eSpz0EnBhNhQ1jZp2A44EHUg7nfdvMbCfCmkuTAdz9G3f/nBi0Lak50MrMmgOFwMfkcduq\n2tyI9O0ZBkx39w3u/hHwAdCrUQqthzQbNz3n7huTT/8JdEo+zlrbFPS1lFyT/yDgNaCDu3+SfGkV\n0CGishrqduAKwuJ0FeLQtm5AOfBgcljqATNrTQza5u4rgVuAZcAnwH/c/Tli0LZK0rVnN2B5ynkr\nksfy1TnAn5OPs9Y2BX0tmNkOwO+Bn1baRhEP05bybuqSmQ0BVrv73HTn5GvbCD3ensA97n4QsJZK\nQxn52raH6DxOAAABjUlEQVTkWPUwwi+zXYHWZjYy9Zx8bVs6cWtPBTMbRxgeTmT7sxT0NTCzFoSQ\nT7j7H5KH/2VmuyRf3wVYHVV9DXAYMNTMlhL2DjjazB4lHm1bAaxw99eSz2cQgj8ObTsG+Mjdy939\nW+APwKHEo22p0rVnJdA55bxOyWN5xcx+BAwBSnzLHPestU1BXw0zM8I479vufmvKS08DZyUfnwU8\n1di1NZS7j3X3Tu5eRLgANNvdRxKPtq0Clif3TADoD7xFDNpGGLLpY2aFyX+f/QnXjuLQtlTp2vM0\ncIaZbWdm3YA9gdcjqK/ezGwQYch0qLuvS3kpe21zd32l+QL6Ev5kfBOYn/waDOxMmAnwPvBX4L+i\nrrWB7exH2BOYuLQNOBAoTf63exJoE6O2/Zywq9si4BFgu3xuG2Hb0U+Abwl/jY2qrj3AOGAJ8C5w\nXNT116NtHxDG4isy5d5st013xoqIxJyGbkREYk5BLyIScwp6EZGYU9CLiMScgl5EJOYU9CIiMaeg\nFxGJOQW9iEjM/X/K1H+jH/37WQAAAABJRU5ErkJggg==\n", | |
| "text/plain": [ | |
| "<matplotlib.figure.Figure at 0x24f870031d0>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| } | |
| ], | |
| "source": [ | |
| "plt.plot(pnts_n, pnts_q, 'ro-')\n", | |
| "plt.show()" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "## Metaheuristics" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "............................................................\n", | |
| "\n", | |
| "............................................................\n", | |
| "\n", | |
| "............................................................\n", | |
| "\n", | |
| "............................................................\n", | |
| "\n", | |
| "............................................................\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "# References" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "* Garey, S. and Johnson, D. (1979)\n", | |
| "**Computers and Intractability: A Guide to the Theory of NP-Completeness.**\n", | |
| "Freeman.\n", | |
| "\n", | |
| "* Hoos, H. and Stutzler, T. (2005)\n", | |
| "**Stochastic Local Search: Foundations and Applications.**\n", | |
| "Morgan Kaufmann.\n", | |
| "\n", | |
| "* Sipser, M. (2013).\n", | |
| "**Introduction to the theory of computation**\n", | |
| "(3rd international ed.). Cengage Learning." | |
| ] | |
| } | |
| ], | |
| "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.6.1" | |
| } | |
| }, | |
| "nbformat": 4, | |
| "nbformat_minor": 1 | |
| } |