Permalink
Cannot retrieve contributors at this time
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-Guide/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.
417 lines (417 sloc)
18.9 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-1819JANMAY/TSP-Guide](https://github.coventry.ac.uk/380CT-1819JANMAY/TSP-Guide)" | |
| ] | |
| }, | |
| { | |
| "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 ......\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$ ......: Reduction from the ................. (Hoos and Stutzler, p.25).\n", | |
| "\n", | |
| "* **Search TSP**:\n", | |
| "\n", | |
| " ..........................\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", | |
| " ...............................................\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "## Random instances sampling strategy" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "General TSP instances will be generated by .... uniformly at random.\n", | |
| "\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "# Code" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "First start by importing relevant libraries." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 6, | |
| "metadata": { | |
| "collapsed": true | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "from random import randint\n", | |
| "from pprint import pprint\n", | |
| "from itertools import permutations\n", | |
| "from math import inf as oo\n", | |
| "from time import time\n", | |
| "import matplotlib.pyplot as plt" | |
| ] | |
| }, | |
| { | |
| "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": 7, | |
| "metadata": { | |
| "collapsed": true | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def get_matrix(n):\n", | |
| " # Distance matrix\n", | |
| " dist_matrix = [[0 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,100)\n", | |
| " dist_matrix[i][j] = v\n", | |
| " dist_matrix[j][i] = v\n", | |
| " return dist_matrix\n", | |
| "\n", | |
| "def show_matrix(mx):\n", | |
| " n = len(mx)\n", | |
| " print(\" \", end='')\n", | |
| " for i in range(n):\n", | |
| " print('{:3}'.format(i), end='')\n", | |
| " print('\\n '+\"----\"*n)\n", | |
| " for i in range(n):\n", | |
| " print('{:2} | '.format(i), end='')\n", | |
| " for j in range(n):\n", | |
| " print('{:3}'.format(mx[i][j]), end='')\n", | |
| " print()\n", | |
| " \n", | |
| "def cost(mx, path):\n", | |
| " c = 0\n", | |
| " for a,b in zip([0]+path, path+[0]):\n", | |
| " c += mx[a][b]\n", | |
| " return c" | |
| ] | |
| }, | |
| { | |
| "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. $bestpath\\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$ $bestpath\\gets p$\n", | |
| "3. $\\qquad$ $bestcost\\gets c$\n", | |
| "4. $\\quad$ **end if**\n", | |
| "5. **end for**\n", | |
| "6. **return** $bestpath, bestcost$" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "There are $(n-1)!$ possible cycles, and each computations a cycle's cost costs $O(n)$. So this algorithm costs $$O((n-1)!\\cdot n)=O(n!).$$" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 8, | |
| "metadata": { | |
| "collapsed": true | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "def solve_tsp(mx):\n", | |
| " n = len(mx)\n", | |
| " city_names = list(range(n))\n", | |
| " \n", | |
| " best_cost = oo\n", | |
| " best_path = []\n", | |
| " for path in permutations(city_names[1:]):\n", | |
| " path=list(path)\n", | |
| " c = cost(mx, path)\n", | |
| " if c< best_cost:\n", | |
| " best_cost = c\n", | |
| " best_path = [0]+path+[0]\n", | |
| " return (best_path, best_cost)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "## Testing" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 13, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "n\tExhaustive\n", | |
| "5\t0.0\n", | |
| "6\t0.0\n", | |
| "7\t0.0009970664978027344\n", | |
| "8\t0.008975982666015625\n", | |
| "9\t0.06703472137451172\n", | |
| "10\t0.6558878421783447\n", | |
| "11\t6.896534204483032\n", | |
| "12\t81.38161826133728\n", | |
| "13\t1015.6810438632965\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "pnts_n = []\n", | |
| "pnts_t = []\n", | |
| "def time_Exhaustive():\n", | |
| " # test exhaustive search\n", | |
| " print(\"n\\tExhaustive\" ) # header\n", | |
| " n = 5\n", | |
| " t0 = t1 = 0\n", | |
| " while t1-t0<100: # in seconds; if it takes too long then stop testing\n", | |
| " t0 = time()\n", | |
| " mx = get_matrix(n)\n", | |
| " solve_tsp(mx)\n", | |
| " t1 = time()\n", | |
| " # record time\n", | |
| " print( str(n)+\"\\t\"+str(t1-t0) )\n", | |
| " pnts_n.append( n )\n", | |
| " pnts_t.append( t1-t0 )\n", | |
| " n += 1\n", | |
| "time_Exhaustive()" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "Let us plot this data to see it visually." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 14, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYEAAAD8CAYAAACRkhiPAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAGU1JREFUeJzt3X2QHPWd3/H3hxUILQYsYSFkPYMFsiQDkvYI3CW+JHKC\nfKEsKk6wXOIi2xyqu3A5G6fqCoUqc6nUXjl1d66QVKCswoB86OAUbAeVq+xAlJydVAV6VkiAHhAI\nZD2dHvYQCAoJWQ/f/NE9MKx2pd2dh+6Z/ryqtrrnNz3TX43NfKb72w+KCMzMrJwuyLsAMzPLj0PA\nzKzEHAJmZiXmEDAzKzGHgJlZiTkEzMxKzCFgZlZiDgEzsxJzCJiZldiYvAs4n0996lMxc+bMvMsw\nM2srGzdu/LuImHi+5QofAjNnzqSvry/vMszM2oqk3cNZzruDzMxKzCFgZlZiDgEzsxJzCJiZlZhD\nwMysxBwCZmZFsnYtzJwJF1yQTteuberqCn+IqJlZaaxdCytXwrFj6ePdu9PHAMuXN2WV3hIwMyuK\n++//KACqjh1Lx5vkvCEg6VFJhyVtqRmbIOk5Sa9n0/E1z62StFPSDkm31owvkvRK9tx/lqTG/3PM\nzNrYnj0jG2+A4WwJPA4sGTB2H7AhImYDG7LHSJoLLAPmZa95SFJX9pqHgbuB2dnfwPc0Myu36dNH\nNt4A5w2BiPglcGTA8FJgTTa/Bri9ZvypiDgREbuAncBNkiYDl0XE8xERwA9rXmNmZgC9vdDd/fGx\n7u50vElG2xOYFBEHsvmDwKRsfgqwt2a5fdnYlGx+4PigJK2U1Cepr7+/f5Qlmpm1meXL4Tvf+ejx\njBmwenXTmsLQgKODIiIkRSOKqXnP1cBqgJ6enoa+t5lZoU3KflNv3w5z5jR9daPdEjiU7eIhmx7O\nxvcD02qWm5qN7c/mB46bmVmtJIHLLoNrr23J6kYbAuuBFdn8CuCZmvFlksZKmkXaAE6yXUfvSro5\nOyroX9W8xszMqioV6OlJTxZrgeEcIvok8P+A6yTtk3QX8F3gn0h6HfhC9piI2AqsA7YBPwfuiYjT\n2Vv9a+AR0mbxG8DPGvxvMTNrbx98AC+9BDfd1LJVnrcnEBFfHeKpxUMs3wuc1cqOiD5g/oiqMzMr\nk5degpMnWxoCPmPYzKwoKpV0+hu/0bJVOgTMzIoiSWDyZJgy5BH0DecQMDMrikol3Qpo4VV1HAJm\nZkVw9Ci8+mpL+wHgEDAzK4aNG9NpC/sB4BAwMyuGJEmnPT0tXa1DwMysCJIEZs+GCRNaulqHgJlZ\nEVSbwi3mEDAzy9uBA7BvX8ubwuAQMDPLXw4niVU5BMzM8pYk0NUFCxa0fNUOATOzvFUq8LnPwbhx\nLV+1Q8DMLE8RaQjk0A8Ah4CZWb7eeAPefjuXfgA4BMzM8lU9ScxbAmZmJZQk0N0Nc+fmsnqHgJlZ\nnioVWLgQxpz3Hl9N4RAwM8vLyZPw4ou57QoCh4CZWX62bk3vK5xTUxgcAmZm+cm5KQwOATOz/FQq\ncMUVMGtWbiU4BMzM8pIkLb+d5EAOATOzPLz/PmzZkuuuIHAImJnlY9MmOHMm16YwOATMzPJRbQo7\nBMzMSqhSgenTYdKkXMtwCJiZ5SFJcu8HgEPAzKz13noL3nwz911B4BAwM2u96u0kvSVgZlZCSZKe\nG7BoUd6V1BcCku6VtFXSFklPSrpY0gRJz0l6PZuOr1l+laSdknZIurX+8s3M2lClAp/9LFx6ad6V\njD4EJE0B/gjoiYj5QBewDLgP2BARs4EN2WMkzc2enwcsAR6S1FVf+WZmbSaiME1hqH930BhgnKQx\nQDfwt8BSYE32/Brg9mx+KfBURJyIiF3ATqAYn4KZWavs3QuHDxeiKQx1hEBE7Af+HNgDHACORsSz\nwKSIOJAtdhCoHgQ7Bdhb8xb7srGzSFopqU9SX39//2hLNDMrngJcObRWPbuDxpP+up8FfBq4RNKd\ntctERAAx0veOiNUR0RMRPRMnThxtiWZmxVOpwEUXwfXX510JUN/uoC8AuyKiPyJOAj8GfhM4JGky\nQDY9nC2/H5hW8/qp2ZiZWXkkCdx4YxoEBVBPCOwBbpbULUnAYmA7sB5YkS2zAngmm18PLJM0VtIs\nYDaQ1LF+M7P2cvo0bNxYmH4ApI3dUYmIFyQ9DbwInAI2AauBTwDrJN0F7AbuyJbfKmkdsC1b/p6I\nOF1n/WZm7WPHDnjvvcL0A6COEACIiAeABwYMnyDdKhhs+V6gt551mpm1rYI1hcFnDJuZtU6lApdd\nBtdem3clH3IImJm1SpJATw9cUJyv3uJUYmbWyU6cgJdeKlRTGBwCZmat8dJLcPJkofoB4BAwM2uN\n6uWjvSVgZlZCSQJXXQVTp+Zdycc4BMzMWqF65VAp70o+xiFgZtZsR4+mJ4oVbFcQOATMzJpv48b0\nPgIFawqDQ8DMrPmqTeGennzrGIRDwMys2ZIEPvMZmDAh70rO4hAwM2u2SqWQ/QBwCJiZNdeBA+kt\nJQvYDwCHgJlZcxX0JLEqh4CZWTNVKtDVBQsW5F3JoBwCZmbNlCTwuc9Bd3felQzKIWBm1iwRhW4K\ng0PAzKx53ngD3n67sE1hcAiYmTVPwZvC4BAwM2ueJIFx42DevLwrGZJDwMysWZIEFi6EMWPyrmRI\nDgEzs2Y4eRI2bSp0PwAcAmZmzbF1Kxw/7hAwMyulNmgKg0PAzKw5kiS9aujVV+ddyTk5BMzMmqF6\nkljBbic5kEPAzKzRjh2DLVsK3w8Ah4CZWeNt2gSnTxe+HwAOATOzxkuSdNrpISDpk5KelvSqpO2S\nbpE0QdJzkl7PpuNrll8laaekHZJurb98M7MCShKYNg2uuirvSs6r3i2BB4GfR8Qc4AZgO3AfsCEi\nZgMbssdImgssA+YBS4CHJHXVuX4zs+KpVNqiHwB1hICky4HPAz8AiIhfR8Q7wFJgTbbYGuD2bH4p\n8FREnIiIXcBOoD0+JTOz4XrrrfTqoZ0eAsAsoB94TNImSY9IugSYFBEHsmUOApOy+SnA3prX78vG\nzMw6R19fOm2DfgDUFwJjgIXAwxGxAHifbNdPVUQEECN9Y0krJfVJ6uvv76+jRDOzFkuS9NyARYvy\nrmRY6gmBfcC+iHghe/w0aSgckjQZIJsezp7fD0yref3UbOwsEbE6InoiomfixIl1lGhm1mKVCsyZ\nA5ddlnclwzLqEIiIg8BeSddlQ4uBbcB6YEU2tgJ4JptfDyyTNFbSLGA2kIx2/WZmhRORbgm0ST8A\n0l069fg3wFpJFwFvAl8nDZZ1ku4CdgN3AETEVknrSIPiFHBPRJyuc/1mZsWxdy8cOtQ2/QCoMwQi\nYjPQM8hTi4dYvhforWedZmaFVb1yaBttCfiMYTOzRkkSuOgiuP76vCsZNoeAmVmjVCpwww0wdmze\nlQybQ8DMrBHOnEnPEWijXUHgEDAza4wdO+C999qqKQwOATOzxqheOdRbAmZmJZQkcOmlcN1151+2\nQBwCZmaNUKlATw9c0F5fq+1VrZlZEZ04AZs3t92uIHAImJnV7+WX4eTJtmsKg0PAzKx+bdoUBoeA\nmVn9KhWYNAmmTs27khFzCJiZ1at65VAp70pGzCFgZlaPd9+FV19ty34AOATMzOqzcWN6H4E27AeA\nQ8DMrD7VpnDPYFfVLz6HgJlZPSoVuOYauOKKvCsZFYeAmVk92ux2kgM5BMzMRuvgwfSWkm3aFAaH\ngJnZ6LXh7SQHcgiYmY1WpQJdXbBgQd6VjJpDwMxstJIE5s+H7u68Kxk1h4CZ2WhEpFsCbdwPAIeA\nmdnovPkmHDnS1v0AcAiYmY1OG185tJZDwMxsNCoVGDcO5s3Lu5K6OATMzEYjSWDhQhgzJu9K6uIQ\nMDMbqVOn4MUX274pDA4BM7OR27oVjh9v+34AOATMzEau2hT2loCZWQlVKjB+fHr10DZXdwhI6pK0\nSdJPs8cTJD0n6fVsOr5m2VWSdkraIenWetdtZpaLJEm3AtrwdpIDNWJL4JvA9prH9wEbImI2sCF7\njKS5wDJgHrAEeEhSVwPWb2bWOseOwZYtHdEPgDpDQNJU4J8Bj9QMLwXWZPNrgNtrxp+KiBMRsQvY\nCXTGp2hm5bFpE5w+7RDI/Cfgj4EzNWOTIuJANn8QmJTNTwH21iy3LxszM2sf1ctHd0BTGOoIAUm3\nAYcjYuNQy0READGK914pqU9SX39//2hLNDNrvCSBadPgqqvyrqQh6tkS+C3gS5J+BTwF/GNJTwCH\nJE0GyKaHs+X3A9NqXj81GztLRKyOiJ6I6Jk4cWIdJZqZNVi1KdwhRh0CEbEqIqZGxEzShu//iog7\ngfXAimyxFcAz2fx6YJmksZJmAbOBZNSVm5m12pEj8MYbHdMPAGjGRS++C6yTdBewG7gDICK2SloH\nbANOAfdExOkmrN/MrDk6rB8ADQqBiPgb4G+y+beAxUMs1wv0NmKdZmYtV6mk5wYsWpR3JQ3jM4bN\nzIYrSWDOHLj88rwraRiHgJnZcER0XFMYHAJmZsOzbx8cOtRRTWFwCJiZDU8HNoXBIWBmNjxJAhde\nCDfckHclDeUQMDMbjiRJA2Ds2LwraSiHgJnZ+Zw5A319HdcPAIeAmdn57dgB773nEDAzK6UObQqD\nQ8DM7PySBC69FK67Lu9KGs4hYGZ2PpVKeqmIrs67GaJDwMzsXE6cgM2bO7IfAA4BM7Nze/ll+PWv\nO7IfAA4BM7NzqzaFvSVgZlZCSQJXXpneUrIDOQTMzM6lUkm3AqS8K2kKh4CZ2VDeew+2b+/YXUHg\nEDAzG9rGjel9BDq0KQwOATOzoSVJOnUImJmVUJLA1VfDFVfkXUnTOATMzIZSbQp3MIeAmdlgDh2C\nPXs6elcQOATMzAbX4SeJVTkEzMwGkyTpBeMWLMi7kqZyCJiZDaZSgXnz4JJL8q6kqRwCZmYDRaRb\nAh2+KwgcAmZmZ9u1C44c6fimMDgEzMzOVj1JzFsCZmYllCRw8cVpT6DDOQTMzAaqVGDhQrjwwrwr\nabpRh4CkaZL+t6RtkrZK+mY2PkHSc5Jez6bja16zStJOSTsk3dqIf4CZWUOdOpVeOK4E/QCob0vg\nFPBvI2IucDNwj6S5wH3AhoiYDWzIHpM9twyYBywBHpLUeXdtNrP2tm0bHD9ein4A1BECEXEgIl7M\n5t8DtgNTgKXAmmyxNcDt2fxS4KmIOBERu4CdQDk+ZTNrHyVqCkODegKSZgILgBeASRFxIHvqIDAp\nm58C7K152b5szMysOCoVGD8errkm70paou4QkPQJ4EfAtyLi3drnIiKAGMV7rpTUJ6mvv7+/3hLN\nzIYvSdJ+QIfeTnKgukJA0oWkAbA2In6cDR+SNDl7fjJwOBvfD9TeqXlqNnaWiFgdET0R0TNx4sR6\nSjQzG75jx+CVV0rTFIb6jg4S8ANge0R8r+ap9cCKbH4F8EzN+DJJYyXNAmYDyWjXb2bWcJs3w+nT\npekHAIyp47W/Bfwu8IqkzdnYvwO+C6yTdBewG7gDICK2SloHbCM9suieiDhdx/rNzBqrBLeTHGjU\nIRAR/xcYaqfZ4iFe0wv0jnadZmZNVanA1KkweXLelbSMzxg2M6sqyZVDazkEzMwgvWrozp2l2hUE\nDgEzs1RfXzr1loCZWQlVm8KLFuVbR4s5BMzMIG0Kz5kDl1+edyUt5RAwM6veTrJk/QBwCJiZwf79\ncPBg6foB4BAwMyvdlUNrOQTMzCqV9C5iN9yQdyUt5xAwM0uSNADGjs27kpZzCJhZuZ05k54jUMKm\nMDgEzKzsXnsN3n23lP0AcAiYWdmV8MqhtRwCZlZulQp84hPpiWIl5BAws3JLkvRSEV1deVeSC4eA\nmZXT2rUwY0YaAps2pY9LqJ47i5mZtae1a2HlyvSewpA2hleuTOeXL8+vrhx4S8DMyuf++z8KgKpj\nx9LxkvGWgJmVx8mT8LOfwe7dgz+/Z09r6ykAh4CZdb5t2+Cxx+Av/xIOHYILLkhPEhto+vTW15Yz\nh4CZdaajR+Gv/xoefRReeAHGjIHbboNvfAPefhv+4A8+vkuouxt6e/OrNycOATPrHGfOwC9+kX7x\n/+hHcPw4zJsHf/EXcOedcOWVHy3b1ZX2APbsSbcAentL1xQGh4CZdYLdu2HNmnSXz69+ld4d7Gtf\ng69/HXp6QDr7NcuXl/JLfyCHgJm1p+PH4Sc/Sb/4N2xIxxYvhj/9U7j9dhg3Lt/62oRDwMzaR0R6\nxc9HH4Unn0z3+8+aBX/yJ7BiRXryl42IQ8DMiu/wYXjiifTLf+vW9Ff+l7+cNnl/+7fTo31sVBwC\nZlZM1WP6H3sMfvpTOHUKbr4Zvv99+MpX0v3+VjeHgJkVy/bt6Rf/D3+YHtM/aRLce2/a6J07N+/q\nOo5DwMzyVz2m/7HH4PnnP35M/5Il6f1/rSkcAmaWj5Ec029N0/IQkLQEeBDoAh6JiO+2ugYza6G1\naz9+Uta996a//B9/HHbtSvftr1iR/uof6ph+a5qWttQldQH/FfgiMBf4qqTG7+RbuxZmzkyPGJg5\nszjXCXddI+O6RqYodUXAiRPwzjvw0ENw993pyVwR6fRb34IHHoBrrklrPHAAHn44vb2jA6DlWr0l\ncBOwMyLeBJD0FLAU2NawNQy8Tvju3cW4Trjrcl2truvuu+H999N96x98kO5u+eCDj/8NNtaIZc9n\nyhR47rnmfiY2LIqI1q1M+hfAkoj4vezx7wJ/LyL+cKjX9PT0RF9f3/BXMnPm4JeJHTMGrr12hBU3\n0GuvpYe4DVTkumbPbn09Va+/PnRdn/nMuV87mv9PD/c1b745dF3Tp6fvU/2rvm+jHp9rmWPHRvfv\nHsoFF6TH4l988UfT2r/BxgYb//a3B39/afCreFrDSNoYET3nW66QjWFJK4GVANNHemnXoa4HfupU\nvoeXbRtiY6fIdc2f39paam3fPvj4qVNw/fXnf/1odisM5zWvvTb4+KlTcMst6XvU/lXft1GPh1rm\ne98buubvf3/kX+BjGvTV8OCDg/8oK+ElmwsrIlr2B9wC/I+ax6uAVed6zaJFi2JEZswY+Nsp/Zsx\nY2Tv02iuy3WVsa4nnojo7v54Td3d6bg1FdAXw/hebvW51hVgtqRZki4ClgHrG7qG3t70uuC1inCd\ncNc1Mq5rZIpa1/LlsHp1ek0fKZ2uXu2rdxbJcJKikX/A7wCvAW8A959v+RFvCUSkvzJmzIiQ0mlR\nfnW4rpFxXSNT1LosFwxzS6CljeHRGHFj2MzMht0Y9qX3zMxKzCFgZlZiDgEzsxJzCJiZlZhDwMys\nxAp/dJCkfmCQUw6H5VPA3zWwnEZxXSPjukbGdY1Mp9Y1IyImnm+hwodAPST1DecQqVZzXSPjukbG\ndY1M2evy7iAzsxJzCJiZlVinh8DqvAsYgusaGdc1Mq5rZEpdV0f3BMzM7Nw6fUvAzMzOoWNDQNKv\nJL0iabOkwlyBTtInJT0t6VVJ2yXdUoCarss+p+rfu5K+VYC67pW0VdIWSU9KujjvmqokfTOra2ue\nn5WkRyUdlrSlZmyCpOckvZ5Nxxekrn+ZfV5nJOVyNM4Qdf1Z9t/jy5J+IumTBanrP2Q1bZb0rKRP\nN2PdHRsCmX8UETcW7PCvB4GfR8Qc4AZgiFtotU5E7Mg+pxuBRcAx4Cd51iRpCvBHQE9EzAe6SO8/\nkTtJ84G7Se+ZfQNwm6Tz3POyaR4HlgwYuw/YEBGzgQ3Z41Z7nLPr2gL8c+CXLa/mI49zdl3PAfMj\n4nrSy9yvanVRDF7Xn0XE9dl/lz8FvtOMFXd6CBSKpMuBzwM/AIiIX0fEO/lWdZbFwBsRMdoT9Bpp\nDDBO0higG/jbnOup+izwQkQci4hTwC9Iv9xaLiJ+CRwZMLwUWJPNrwFub2lRDF5XRGyPiB2trmVA\nDYPV9Wz2vyPA88DUgtT1bs3DS4CmNHA7OQQC+J+SNmb3LC6CWUA/8JikTZIekXRJ3kUNsAx4Mu8i\nImI/8OfAHuAAcDQins23qg9tAf6BpCskdZPeKGlazjXVmhQRB7L5g8CkPItpM98AfpZ3EVWSeiXt\nBZbjLYER+/vZZtQXgXskfT7vgkh/2S4EHo6IBcD75LOpPqjslp9fAv5bAWoZT/qLdhbwaeASSXfm\nW1UqIrYD/xF4Fvg5sBk4nWtRQ8juMOVDAIdB0v3AKWBt3rVURcT9ETGNtKY/bMY6OjYEsl+SRMRh\n0v3bN+VbEQD7gH0R8UL2+GnSUCiKLwIvRsShvAsBvgDsioj+iDgJ/Bj4zZxr+lBE/CAiFkXE54G3\nSfclF8UhSZMBsunhnOspPElfA24Dlkcxj5tfC3y5GW/ckSEg6RJJl1bngX9Kugmfq4g4COyVdF02\ntBjYlmNJA32VAuwKyuwBbpbULUmkn1XuTfQqSVdm0+mk/YC/yreij1kPrMjmVwDP5FhL4UlaAvwx\n8KWIOJZ3PVWSZtc8XAq82pT1FDP06iPpaj46umUM8FcR0ZtjSR+SdCPwCHAR8Cbw9Yh4O9+qPgzL\nPcDVEXE073oAJP174Cukm+ibgN+LiBP5VpWS9H+AK4CTwLcjYkNOdTwJ/EPSK04eAh4A/juwDphO\negXeOyJiYPM4j7qOAP8FmAi8A2yOiFsLUNcqYCzwVrbY8xHx+wWo63eA64AzpP87/n51D0dD192J\nIWBmZsPTkbuDzMxseBwCZmYl5hAwMysxh4CZWYk5BMzMSswhYGZWYg4BM7MScwiYmZXY/wdIAL0d\nKJKQiwAAAABJRU5ErkJggg==\n", | |
| "text/plain": [ | |
| "<matplotlib.figure.Figure at 0x1ad18f453c8>" | |
| ] | |
| }, | |
| "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": [ | |
| "................................" | |
| ] | |
| }, | |
| { | |
| "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.7" | |
| } | |
| }, | |
| "nbformat": 4, | |
| "nbformat_minor": 1 | |
| } |