Skip to content

Instantly share code, notes, and snippets.

@cast42

cast42/notebooks_Traveling_Sam_Problem.ipynb

Last active May 24, 2019 20:04
Show Gist options
  • Save cast42/8a65cf377ffd87946359c0abe02d8820 to your computer and use it in GitHub Desktop.
Save cast42/8a65cf377ffd87946359c0abe02d8820 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
notebooks_Traveling_Sam_Problem.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Traveling Sam Problem"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This notebook provides a solution for the [\"traveling Sam Problem\"](https://github.com/Forceflow/Ambiance_TSP). The task is to compute the shortest tour connecting 24 cities in Belgium. The cities are taken from a song [\"Ambiance, Ambiance'](https://www.youtube.com/watch?v=EqdQyoAUQZ0) by Sam Gooris.\n",
"\n",
"This solution took the coordinates of the cities from [this notebook](https://nbviewer.jupyter.org/gist/martinfiers/e8f3efce89e099653d87fb47a8e10b0e) written by [Martin Fiers](https://twitter.com/MartinFiers).\n",
"\n",
"I stand on the shoulder of the giant [Peter Norvig](http://norvig.com/) who [coded a splendid solution](https://github.com/norvig/pytudes/blob/master/ipynb/TSP.ipynb) using the Held Karp algorithm. The solution is optimal but the algorithm is much faster then brute force exhaustive enumeration because it prunes out possible tours that can't be shorter anyway."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"# Imports used in this notebook. This is Python 3 on Jupyter with matplotlib.\n",
"%matplotlib inline\n",
"import matplotlib.pyplot as plt\n",
"import random\n",
"from time import clock \n",
"from itertools import permutations, combinations\n",
"from functools import lru_cache as cache\n",
"from collections import Counter\n",
"from statistics import mean, median"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"cities_list = [\n",
" ('Mal', (50.768450, 5.521440)),\n",
" ('Gent', (51.054340, 3.717424)),\n",
" ('Leest', (51.033699, 4.419630)),\n",
" ('Peer', (51.185883, 5.289227)),\n",
" ('As', (51.000542, 5.572203)),\n",
" ('Tielt', (51.000061, 3.324990)),\n",
" ('Lot', (50.765170, 4.276202)),\n",
" ('Puurs', (51.071998, 4.286193)),\n",
" ('Lint', (51.127670, 4.495450)),\n",
" ('Heist', (51.337436, 3.239979)), # Aan zee.\n",
" ('Reet', (51.104485, 4.405890)),\n",
" ('Bree', (51.141090, 5.597620)),\n",
" ('Schriek', (51.021873, 4.709033)),\n",
" ('Geel', (51.162319, 4.990880)),\n",
" ('Leut', (50.989192, 5.741560)),\n",
" ('Doel', (51.317621, 4.245205)),\n",
" ('Duffel', (51.095718, 4.506199)),\n",
" ('Sinnaai', (50.780688, 4.792712)),\n",
" ('Vorst', (50.809143, 4.317751)),\n",
" ('Niel', (51.109865, 4.330340)),\n",
" ('Bere', (50.949909, 3.288330)), # Meulebeke\n",
" ('Gits', (50.997592, 3.110329)),\n",
" ('Boom', (51.087379, 4.366722)),\n",
" ('Haacht', (50.976929, 4.638682)),\n",
"]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Exhaustive Search Algorithm: exhaustive_tsp"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## The number of tours we must evaluate to find the shortest by exhaustive enumeration"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"12,926,008,369,442,488,320,000\n"
]
}
],
"source": [
"import math\n",
"print(f\"{math.factorial((len(cities_list)-1))//2:,}\")"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"# reduce the number of cities to 9 to keeo the solution tractable\n",
"\n",
"City = complex\n",
"\n",
"cities = frozenset(City(x, y) for _, (x, y) in cities_list[:9])"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"frozenset({(50.76517+4.276202j),\n",
" (50.76845+5.52144j),\n",
" (51.000061+3.32499j),\n",
" (51.000542+5.572203j),\n",
" (51.033699+4.41963j),\n",
" (51.05434+3.717424j),\n",
" (51.071998+4.286193j),\n",
" (51.12767+4.49545j),\n",
" (51.185883+5.289227j)})"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"cities"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## The python code for a brute force solution does not scale to 24 cities"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"alltours = permutations \n",
"\n",
"def tour_length(tour):\n",
" \"\"\"The total of distances between each pair of consecutive cities in the tour.\n",
" This includes the last-to-first, distance(tour[-1], tour[0])\"\"\"\n",
" return sum(distance(tour[i - 1], tour[i]) \n",
" for i in range(len(tour)))\n",
"\n",
"def distance(A, B): return abs(A - B)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"def exhaustive_tsp(cities):\n",
" \"Generate all possible tours of the cities and choose the shortest tour.\"\n",
" return shortest_tour(alltours(cities))\n",
"\n",
"def shortest_tour(tours): return min(tours, key=tour_length)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"frozenset({(50.76517+4.276202j),\n",
" (50.76845+5.52144j),\n",
" (51.000061+3.32499j),\n",
" (51.000542+5.572203j),\n",
" (51.033699+4.41963j),\n",
" (51.05434+3.717424j),\n",
" (51.071998+4.286193j),\n",
" (51.12767+4.49545j),\n",
" (51.185883+5.289227j)})"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"cities"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"CPU times: user 1.15 s, sys: 983 µs, total: 1.16 s\n",
"Wall time: 1.15 s\n"
]
},
{
"data": {
"text/plain": [
"((51.185883+5.289227j),\n",
" (51.12767+4.49545j),\n",
" (51.033699+4.41963j),\n",
" (51.071998+4.286193j),\n",
" (51.05434+3.717424j),\n",
" (51.000061+3.32499j),\n",
" (50.76517+4.276202j),\n",
" (50.76845+5.52144j),\n",
" (51.000542+5.572203j))"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"%time exhaustive_tsp(cities)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [],
"source": [
"def plot_tour(tour, style='bo-'): \n",
" \"Plot every city and link in the tour, and highlight start city.\"\n",
" if len(tour) > 1000: plt.figure(figsize=(15, 10))\n",
" start = tour[0:1]\n",
" plot_segment(tour + start, style)\n",
" plot_segment(start, 'rD') # start city is red Diamond.\n",
" \n",
"def plot_segment(segment, style='bo-'):\n",
" \"Plot every city and link in the segment.\"\n",
" plt.plot([X(c) for c in segment], [Y(c) for c in segment], style, clip_on=False)\n",
" plt.axis('scaled')\n",
" plt.axis('off')\n",
" \n",
"def X(city): \"X coordinate.\"; return city.real\n",
"def Y(city): \"Y coordinate.\"; return city.imag"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAE8AAAD4CAYAAACt+7tLAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvnQurowAAC3FJREFUeJztnV+sFUcdxz9TKH8uSOFeam2sgIU0tbG21j+gtvaiMUETH4w+mKtWEUmaRo2JDzZtovFB+6BpJE2bJjUp+tBEH4SosU00cE9bKlGbajClIoQDqGhTIKVc/nN/PswsbA/ncs7uzJyZ2TPf5GRz9+z+Zs/n/n6/mZ2dnVEiQlY9XRX6AlJWhmehDM9CGZ6FMjwLZXgWyvAslOFZKMOzUIZnoQzPQhmehRoFTykmlKKtFNNmO+G1vKb0qhhQTwAjpd0ngY0iPOWlzAbBOwi8o8tXB0RY4aXMFOEpxVXATcCa0ue2GQ4XET/pabYPo66lFKPAB7kEajWw2Hz9OrATWAFc0+X0g94uTESCfEAmQNog02Y7YfbPBrkd5F6QzSCvgIj5XAD5K8jjIF8BuRnkqpK9qdKxAnKqsOvlNwQE1/lDz4K83LH/fyBbQe4HGQdZWOEfcgFkD8ispsFrd4ArPmdAfgLyeZAVIMqijC8Ym9/y9TuCVBhKMQ2oLl+JOEruSqGA3wAfA24VYZ8Lu2WFaiTPlMSdJXcRBLgXOAf81NTQThUK3gPoBmxZJ81+ZxLhX8C3gXFgo0vbpoDB57xScj9i8tIhX7UiiAL5A8hxkGVObYeCZ37YNwy8Mc/lvNPU4k/bVEKdn9AdA0Wl4bXWEmE/cD+wDviSK7uh4Q1SjwI7gE1Kcb0Lg6HhDcTzAESYBjYA84FHTVPGSkMDD0CEfwDfBT4DfM7WXmh4IfQw8CLa+5baGAoNb6CeByDCeWA9uldmk42toYMHIMIu4AfAhFJ8uq6d0PBC6iFgF/C4Uhf7BispNLwgngcgwlngq8DbgB/XsTG08ABE+AvwI2CDUnyi6vmxwAup7wN7gCeUYmGVE0PDKxTsKZQIp9Dhuwx4CKXWolQbpdb2Ojc0vKBhW0iEHcAj42z/+hQj24DlU4xs+7L62ZYeJwbtVfmO6VUZCXkdIsIX+fmvTzAi5WcCJxiRe9i8ZcbrjwTe/KDwYG0nuDJAgbXdzsthq/Xkgss6trXM/ie7fRcLvNBaP/WmIS6XZPav7/ZdaHiFwnqeyPb7eGxrJ8ApRriPx7Yisn2G84LmvAdMapkTNOeZzz1s3lLkvl6VhUj4CuPBmOCBzBlnmxxl8bGZKonyJ4ftmzU6yVpGOfYgM4VqSaHhxVLbFho12yP9HBwLvFg0ZrZH+zk4NLxCsXheAS8pz8vwaii2sE0q5xWKyfPOAlP9HBwanoKLw8Fi0BhwtN/riQJeRBqjz5CF8PBi0ygJwVPEk+8gMc+LMWz7aiBDeHgQieeZUVPJeV4U8IAFwBwSgxeLKjWQITw8iMfzKnUKQHh4MYVtpftaiANeLEoOHsTjecnlvBjDNqmcF4vGgBOix+31pdDwIC7P6ztkITy8mMK2UqcAxAEvFiXneRCP51XqFIDw8GIK2+Q8L4qwNW+BLyFBeDF43mL0tSQFD+KAV/nWDMLDi8XzKt9dQBzwYlDl+1oIDw/i8ryk4MUWtsnBi0FjwDR6RrS+FRoexON5x0TPQ9C3QsOLJWwrdwpAHPBiUOVbMwgPD+LwvCThxRK2lXtUIA54MSjJnAeBPU8p5gALSRBeDGFbq4EMccALrVqdAhAeHoT3vFqdAhAeXg5bC8UUtsnBg+x5tRVD2I4CZ4BTVU+MAV5ojQFH6rxIExoehPe8Wve1EB5eDGGbNLzQqtUpAOHhQXjPq9UpAOHhBQ3bOi+ulBUDvJBaCFxNovAgbNjWbiBDeHiha9uiUyDJCiN02CbteZDDtrZCh23y8EKqyHnH6pwcGh6E97zjIpyrc3JoeMHC1qxK+jVgUd3lXGOAN/hCLy3nusDsWo6eZLoSwBjghfC8H8Jlk4SOmP19KzQ8CANvWcX9XRUa3sDDVinWMvM/rNKKfzHAG4jnKYVSim8CvwcOc/kzi8or/oWGBwOApxTz0BNFbwJ+C9yCrmkPmPIPUGft78Czw/4SZLcn2+W1bs+YWXG/h1lM2MUn9LLUXsK2y8ryc9CPF/9ZddzxldTUsO3WFJlLxaZIL4WG56u2ddIU6aUY4PnwPO+LD0N4eOAH3kAWHw4Nz0vYmibHRi552hvUaYr0UAzwvLTzRHhKhOXAM8Bh1+AgPDzw30h+GrhJKVa6Nhwa3iDubX9ntp90bTgGeL6XpN4L7AU+5dp2aHgwmI6BvcA6pZiu22vcVQHvaydATpp7zjbIhMdyTnesyDXloryQ4KZ8/KAuZbW7LGcmIG1b20oXMFgpRRv93KBTB0RY4bisabpXTCKWy/iEynkDufc08narFgreQO49jfzdqjU955XKKzpE267KCQKv9IPa5ged8AWuVN4rIL9waTNYO0/0vecK4FfAa+Lh3rND84DTLg3G0EhuAcuV6lr7utRcGgoP4G7P5TTS83ahh3hleFUl+mnWs8C4rzLMKwPNg2fUAm5Uihs82Z9jto2FB/5Cd57ZNhLe39AziGV4VSXCBeB5/MM749JoFPCMJtHPGq73YLu5nmfkM+81Ht5L6OerGV5ViXAe2EGGV1uTwLuU4jrHdocCXpH3PurY7lDAexG9MK/r0G0+PNGvMb1AhldbLeDdSrHUoc2hgTdpti7z3lyzbTy8P6PfkXAZusPheaLXHfsjfuA19t62rBbwHqVY4sjePOCc6YBwpljhTaKHSNzlyJ7zXmSIF96f0CE27sje8MAT4TSwE3d5bx6O8x1ECs+oBdyuFNc4sDU8nmfUQl/fnQ5sDR28ncBZ3ITucMET4SS64hh3YG644Bm1gDuU4i2WdoYW3izgI5Z2hhLeC8B57PPe8METYQrdUTBuaWr44Bm1gPcrdXH2nToaanizgQ9b2BhaeDuAC9jlPeejQiEBeCK8gX4wVAuer7F5kAA8oxawWqnLZqzoR7PRv3Oo4V0NrKlxrpcueEgH3vPoVUDrhO5wwxPhdfRAIBt4Q9Wf16kWsMZMqlVFw+15Ri10k2N1vyeYN7qL8S8PO3vD2ygleM+hX6nvK3RLk3EVI02vpca8oFcsQ7/UloaU4iXgqAgf7+PYNp5fiE7J80CH4IeUujh84kry/kJ0ivDmAx/o41jvL0SnBu85s+0n73mfjCspeCK8BvydPuDJpcm4iolV680LegUlVWEAKMUjwHpgifQxp7tS7AZeFuGzrq8lKc8zaqGnJX9frwOVYhZwI7DPx4WkCO9Zsx3v49i3o9943OvjQpKDJ8KrwG76qzRWmW32vJImgTuV6jlVcTFnXoZXUgu9Ztl7exy3EjgHHPJxESnDg96huwrY73pEaKEk4YnwX2APvSuNlXiqLCBReEYt4C7THLlM5sHPKjzlO0gb3iSwCLhthu+vRefFDK+LeuW9oqbNYdspEf6N9qrxGQ7x2saDhOEZFXmv2+9Yie553u+r8NThTQJLgFu7fLcKOCTi/qlZodThXSnvrcRjyELi8EQ4CLTpDm8VHisLSByeUQu4u5z3lGIRsJTseT3VQi94eUtpn/dmCjQD3qTZlkPXezMFmgGvje41KcPz2hVVKHl4IgiX8l4xE/cq4FUzMNKbkodn1ALeCtxs/vbeTIHmwJs02yJ0vXZFFWoKvH3Af9ChOw+4gex5/amc99CPGhUZXiW10MPJ1pm/c9hWUHGfu8FsvXtecsMtZpJpphwGrgOOA4tNOHtTYzzPgCr67hYB+10Po+1UY+AZUHeUdi3H8TDay8psUNi2GdC6QhfLbBA8bwslzaTGhC2DXVcIaBa8gaxpW1Zj4JWG0R5APzVzPoy2U43JeSHUGM8LoQzPQhmehTI8C2V4FsrwLJThWSjDs1CGZ6EMz0IZnoUyPAtleBbK8CyU4Vkow7NQhmehDM9CGZ6FMjwLZXgWyvAslOFZKMOzUIZnoQzPQhmehTI8C2V4Fvo/reOtq7IO0f4AAAAASUVORK5CYII=\n",
"text/plain": [
"<Figure size 432x288 with 1 Axes>"
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"plot_tour(exhaustive_tsp(cities))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Held karp algorithm"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [],
"source": [
"def first(collection): return next(iter(collection))"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [],
"source": [
"def held_karp_tsp(cities):\n",
" \"\"\"The Held-Karp shortest tour of this set of cities.\n",
" For each end city C, find the shortest segment from A (the start) to C.\n",
" Out of all these shortest segments, pick the one that is the shortest tour.\"\"\"\n",
" A = first(cities)\n",
" shortest_segment.cache_clear() # Start a new problem\n",
" return shortest_tour(shortest_segment(A, cities - {A, C}, C)\n",
" for C in cities - {A})\n",
"\n",
"# TO DO: function: shortest_segment(A, Bs, C)"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [],
"source": [
"@cache(None)\n",
"def shortest_segment(A, Bs, C):\n",
" \"The shortest segment starting at A, going through all Bs, and ending at C.\"\n",
" if not Bs:\n",
" return [A, C]\n",
" else:\n",
" return min((shortest_segment(A, Bs - {B}, B) + [C] for B in Bs),\n",
" key=segment_length)\n",
" \n",
"def segment_length(segment):\n",
" \"The total of distances between each pair of consecutive cities in the segment.\"\n",
" # Same as tour_length, but without distance(tour[0], tour[-1])\n",
" return sum(distance(segment[i], segment[i-1]) \n",
" for i in range(1, len(segment)))"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [],
"source": [
"def do(algorithm, cities):\n",
" \"Apply a TSP algorithm to cities, plot the result, and print info.\"\n",
" tour = algorithm(cities)\n",
" assert Counter(tour) == Counter(cities) # Every city appears exactly once in tour\n",
" plot_tour(tour)\n",
" print(\"{}: {} cities ⇒ tour length {:.0f}\".format(\n",
" name(algorithm), len(tour), tour_length(tour)))\n",
" return tour\n",
" \n",
"def name(algorithm): return algorithm.__name__.replace('_tsp', '')"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [],
"source": [
"# Take all 24 cities\n",
"cities = frozenset(City(x, y) for _, (x, y) in cities_list)"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"held_karp: 24 cities ⇒ tour length 6\n",
"CPU times: user 1h 47min 17s, sys: 5min 21s, total: 1h 52min 39s\n",
"Wall time: 1h 52min 39s\n"
]
},
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAFoAAAD4CAYAAABsfPHnAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvnQurowAADb9JREFUeJztnXuMXFUdxz+/lkooj9IKAXmVdCuBoonPQAwhrtYEUYgkEHVTwYK8aoQ/RCXQABUoUaOiEHyglDfYhNAQEVCEIokgkiAaEkNLmW4jjVBgF1so3XZ//nHO3V5m7+zOzL3ncWfON5nczp2dc8799De/87i/+zuiqiS514zQDegXJdCelEB7UgLtSQm0JyXQnpRAe1IC7UkJtCcl0J6UQHtSAu1JtQYtwpAIDRHG7XEodJtaSeq6emeh3gzMzp1+GzhXlbvDtKq16gy6Acwv+GijKkf6bc30qjPocUAKPlLV+FxidA3qQMMdng+qOoO+DOOTm7VJhD18N2Y61Ra07fDOBbbYU68Aq4ETgNUi7BmqbYVS1Vq/QE8GVdDj7PuL7PtHQPcO3b7sVVuLzulNe5wLoMrPgXOAxcDDIswJ1bC8eg40gCq3AF8Fjgf+LMIBIRqWVy+Bnpc/qcpq4EvAscATInzAd8Py6iXQc5s/UOVB4PPAEcCTIlwUbMoeupOoqEPcCvrjKT4/zv7NuO0os9c20CEvbQwNqQLIQ6A7LbhGK3CgrzRBzl4NH+2s7RQcOltYCj1lry1oEfYB1gMHFXw8aWEp9CJU+M5QZBCRBiKDrf+EGSIcLcLXRfilCP8ARimGDKbza1bRlP1te969QvrXM7n1/q3MVgXdymw9k1vvt/50HuhJoFeBPgz6Zs6njthZ3wrQ/3bid60/3zadP3fSl8QAOXttZbYu5o9v5U7tAn0e9FegS0GPAZ3RAlxbIwnQlaBjoHv4vN4woGGwGXIe9jJuvBl0EHTfaS/AwG7Yodu0Vmr/wxR0wOc1h+kMRRoUd0yZNqJ6pJuqOQF4EjhZlYdc1FGkUJ3h0m3vGZHtlj2/1GHd6+zxgw7rmKQwoFUfX8ZNa5phb2M2y7hpDaqPO6z9VeAtPIMO46Pta4g7/1A06nDeMaHPgj7s81qDggY94NM8piPs97rCoMd67wF9yee1hp6w7FzLIPszeg1u3UWz1gFHivA+XxUGB22Pvm+mrsNc+wJfFYYGPWaPIUCDxw4xNOhQFv2iPfYN6HF7nOWzUlXeAN6gX0Crohj3ESLgZR1wlK/KQls0GPcRCnR/WLTVTjy7Dqt1wOEi7OWjshhAh3IdWYc44KOyGECHch3ZGPqfPkIPYgHt1XVYqMuzt5gl25tdwo4BdAjXsRIm+ebZ9rwTxQA6hOsounk71fnSigW071GH96cFYgHt26K9hx7EANq7j1YTxfSt3KmNOH5sLoZnPUJNWJ6wx7NUud11ZTFYdKhxdBacvmXKv6pIMYAONTPsO9DJoj0plI8+0B77BnRI17ED+J+PymIAHdJ1bLE3H5wrFtAhXMcBeHIbEA/oEBZ9IH0GOqSP7ivQIV3Ha74qiwW0V4u2aSbm0mcWHcJ1zMPcWekr0CFch9dZIcQD2rdFZ6D7ykeHcB3Jol0r91gzwO99ZTiIZuFfBHE9HS54dvwwTJgBLu+uQBwWncVI+2jLSpj0OJjTMINMMYD2GSPtPcwgU0ygfQzxgiUljAm0D4v+UcE5LxkOYgDt8zmWY4BdwH8AxUOYQaZYRh3g2HWIcBgm8+NvVTnfZV1FisGifbmOSzHXe53jegoVA2jnrkOEQzHWvEqVhqt6plIMoH24jsyanY+XWykm0E4sOmfNt4ayZogDtGvX8T1gJgGtGeIA7cyiRTgEOA+4TZWXqy6/E8UE2oWPjsKaIQ7QJ9jjU1U+HWWt+XzgdlU2VFFmKQVOjDIEut1FYlbQ623O0gUhrzF7BU2Z6SqNpc0VvQG4R5Wzuy2nSoV2Ha6WLb+L8fnXliynMoUGXfmypbXmC4A7VHmp23KqVmjQlwHvNJ0ru2z5HSKzZiB8om7bIU4kb+22I7TlbJrIvOkxwWtb7QvdAAtpFPRnJf+zOkoG6/sV2nVkGoVS+6UEu+narmIBPUI50MFuurarWECPAvuX+P7rLc5HsxNcTKA7suj8NqjA+2FS8I2/tPJtKBbQHbmOXMTRfEz4rWAWp7bg+aZru4rh5ix07jqKOr9ZwDbViecHo1IsFj0KzBEp3CelSNF3fs2KBfQIZt24OE36ZNVqG1SIB/SoPbbrPlptg+ozNXJHig10Wx2i7t4GdSOm8xsGngXOEuF0Jy0sqVhAj9hj2yMPVe5W5UhVZqgyHzgReAq4U4QTXTSyjGIB3anrmCRV3gFOwSz4PyDCh6toWFWKDXSp/WHVpCs+CdgGPCQSzygkFtAdu45WUmUYA3sf4K8iDAfZkbNJsYAu7TryUuVfwA3AocDh7E6LeWco6LGAfhsTt1zl1tJfKziXTded5yJtVhSgVVHKL5U2azr/7HW9OgrQVmWXSpvVzizRW2cZG+gqLbrV7DEvb1P2mEBX7Tr+AmzOvQ+6Xh0T6NKuo+lmQAMz6jhNFQGWsHvK7n29Opb1aCjpOgoeP56Jib1eLML1GH88DCwJcUMgmu2qLYylqt3BniKOr1mF+4a7VmyuYz8RZnb5/XZHEEHCEGIDDbBvl9/vZAThfQ0kJtBl1zvaGc5l8n4nJibQpdY7Cm4G7Jriz72HIcQE+uP2+Fy3iz75mwHEdW3RBDkOgb5TZZCijUwt2uNdQRu+rzGK4Z2LRyzsL+KuFh97D/AM9vNqmsW1Gv92NTqwkKcawnnvDIPMDAtmca3UMZA2yg4SkxfKootCuprVLZCpyh4FfgM873OraiBMZwg6PkVHNV7yEYvpys7+PQb6Auhq0KtAzwBdBDqroKNulG1XkM7Q1fOF05WNSfVzNHCsfS2yxwUwEfe3E7Op5AuYhakvAHvmyulurSSQRRc9c7K9oidmO36eBXQ26EdBl4BeB/oA6Poqh4dBQBf8JMdAh0FnOii74cANjXdaVizj6C8D9wJDqtwTuj2ZqnRxsYCeATyH2TVzkepEaomgajFUrI+PbvEzPdX+LM8O3ZYCN7Qj8821GnUUyUb7Pw0cDBylyruBmzQhEZ4DNqlyardlRLPCpYpidjY+AvhG4OY0awzKTXCiAW31KCZMYLlI249Z+NAYJVMRRQU6Z9UHA8sCNyev3gINoMqTwCPApSLsF7o9VjvoNdBWyzFPw14cuiFWvWfRAKo8C6wBLhFhXuj20Kugra7AhB5cEroh9DJoNVH79wIXi3BQ4Ob0LmirqzBLlJcGbkdvg1blReA24EKb0TyUehu01fcx7VwesA29D1qVjcCvgXNEWBCoGb0P2upazC2mKwPV3x+gVdkM3AgsEeGYAE3oD9BWP8Asuq8IUHf/gFZlC/BT4AwRPuK5+jFASgTJ1we01U8wcdRXe64324ega6uuFWhVRoAfAl8U4XiPVfcXaKsbgFeBazzW2X+gVdmK2YbpsyIMeqq2/0Bb/RKzg9s1HaRwK6P+BK3KdkyH+ClMEhTX2mGP/QXaahXwMn6sOrPoru+E1xa0Kjswy6gfA05zXF1/uo6c7gL+DVxdZjLRhvobtCq7MLe8FgFfcVhVf4O2ug94Hlgh4mxPxARalXHMTYEB4CxH1STQVg8CfwOuEHnPYxBVKYGGiVCyyzE57s5zUEUCndNjwFrgchH2rrjsBDpTLkDyIGBTxRkbE+gmzcekj5hLtRkbE+gmrYRJE5cqUvsk0E1ytclCAt0kV5ssJNBNKsqrVEU2gwQ6L/vsXx5qVRkbS4OOKZNjVXrBHgdVWVtRmcmiC7TQHqvcb7av77C00gDwLuaeYlXKUrsl0DktBDbYVb1KZGedpcLCehH0ALDeQbkJdCZ7k3aAav1zpgQ6p4MxU25XoPvvLngLDdhjch2O5WJolymBzmkAMxTb6KDsBDqnAWDYBtdUrQQ6p4W48c+QQL9HroZ2kEAbiTAXmEcC7Vwuh3aQQE8oA50s2rGyMfQGR+Un0FYDwGZVtjkqP4G2Wog7twEJ9IRcLY9mKpUprCdA22SEh5As2rmyPB4uLTqBxv3QDvodtA1gXGXf3udwC+pSoGsd11GQSPtwTPQoFQTNNKuvLbpozxVXG0P2F2iXWz9No/5xHS63fmpDY8AsEcTGeXSkulm0y62fplMWf9eVcdYN9FQuwdl+3/aX9G37dn1XI5vQu0J0uINEw/dGkN3sVFRYTmh4IS46xH9ucHhdws5f/HkO61o0xX5ZHW3jVDcfjdoNfDHZZwDerLJ8EeaIcL4IT7M7qL1IHY1sagc6p78DbwGfK1uQCDNE+IwIdwCbMTmb9sF0gBdSxXMxoV1ByZ/2GtANJb4/H/RK0JetOxgB/QXoJ0GlwF11vZtccFglQX/TAhro4Dt7WXB/ym2j96g9t5erttZqZligR+1xMVMskdq46U8AS4EhYA5mzL0CuE2VhttmRrLNXreyADcCz6hyesHnBwJLgLOBDwHbMRlrbgHWaoWPX0ynWlu0KirCBuA0u8g0jMlwMIKBewrmGp8BLgB+pya/qXfV3aKzRf98JL5iMhu8BtwOrFKdcpjmRXUH3aB4qfQ14FDViYWg4Ko76HEozOKoGtlkLKrGdCFX2QwqV91Bu8pmULlqDVrNuvO5mCGes/XoKlRrH10n1dqi66QE2pMSaE9KoD0pgfakBNqTEmhPSqA9KYH2pATakxJoT0qgPSmB9qQE2pMSaE9KoD0pgfakBNqTEmhPSqA9KYH2pATakxJoT0qgPSmB9qQE2pMSaE9KoD0pgfak/wMQu/VU9nPufwAAAABJRU5ErkJggg==\n",
"text/plain": [
"<Figure size 432x288 with 1 Axes>"
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"# Search for the shortest tour\n",
"%time sam_tour = do(held_karp_tsp, cities)"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Mal -> Sinnaai -> Vorst -> Lot -> Gent -> Tielt -> Bere -> Gits -> Heist -> Doel -> Puurs -> Niel -> Boom -> Reet -> Leest -> Lint -> Duffel -> Haacht -> Schriek -> Geel -> Peer -> Bree -> Leut -> As -> "
]
}
],
"source": [
"# Print the list and order of cities in the shortest tour\n",
"for city in sam_tour:\n",
" for city_name, location in cities_list:\n",
" #print (location, city)\n",
" if City(location[0], location[1]) == city:\n",
" print (city_name , '-> ', end='')"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"24"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(cities)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Draw the shortest Traveling Sam Tour"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[('Mal', (50.76845, 5.52144)),\n",
" ('Sinnaai', (50.780688, 4.792712)),\n",
" ('Vorst', (50.809143, 4.317751)),\n",
" ('Lot', (50.76517, 4.276202)),\n",
" ('Gent', (51.05434, 3.717424)),\n",
" ('Tielt', (51.000061, 3.32499)),\n",
" ('Bere', (50.949909, 3.28833)),\n",
" ('Gits', (50.997592, 3.110329)),\n",
" ('Heist', (51.337436, 3.239979)),\n",
" ('Doel', (51.317621, 4.245205)),\n",
" ('Puurs', (51.071998, 4.286193)),\n",
" ('Niel', (51.109865, 4.33034)),\n",
" ('Boom', (51.087379, 4.366722)),\n",
" ('Reet', (51.104485, 4.40589)),\n",
" ('Leest', (51.033699, 4.41963)),\n",
" ('Lint', (51.12767, 4.49545)),\n",
" ('Duffel', (51.095718, 4.506199)),\n",
" ('Haacht', (50.976929, 4.638682)),\n",
" ('Schriek', (51.021873, 4.709033)),\n",
" ('Geel', (51.162319, 4.99088)),\n",
" ('Peer', (51.185883, 5.289227)),\n",
" ('Bree', (51.14109, 5.59762)),\n",
" ('Leut', (50.989192, 5.74156)),\n",
" ('As', (51.000542, 5.572203))]"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sam_tour_cities_list = []\n",
"for city in sam_tour:\n",
" for city_name, location in cities_list:\n",
" #print (location, city)\n",
" if City(location[0], location[1]) == city:\n",
" sam_tour_cities_list.append((city_name, (location[0], location[1])))\n",
"sam_tour_cities_list"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np\n",
"city_list = np.array([(x, y) for _, (x, y) in sam_tour_cities_list])"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"data": {
"application/vnd.jupyter.widget-view+json": {
"model_id": "f7ec348b6fa04deab17b621ceda02667",
"version_major": 2,
"version_minor": 0
},
"text/plain": [
"Map(basemap={'url': 'https://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png', 'max_zoom': 19, 'attribution': 'Map …"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# Draw the solution to the Traveling Sam Problem\n",
"\n",
"from ipyleaflet import Marker, Map, Polyline\n",
"\n",
"center = list(np.mean(city_list, axis=0))\n",
"\n",
"m = Map(center=center, zoom=9)\n",
"\n",
"for city, center in sam_tour_cities_list:\n",
" marker = Marker(location=center, title=city, draggable=False)\n",
" m.add_layer(marker)\n",
" \n",
"line = Polyline(locations=[[\n",
" [[x, y]\n",
" for _, (x, y) in sam_tour_cities_list]\\\n",
" \n",
"]])\n",
"\n",
"m.add_layer(line)\n",
"\n",
"m"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.3"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment