.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "api/gallery/optimization/tsp/plot_01_held_karp_travelling_salesman.py" .. LINE NUMBERS ARE GIVEN BELOW. .. only:: html .. note:: :class: sphx-glr-download-link-note :ref:`Go to the end ` to download the full example code or to run this example in your browser via JupyterLite. .. rst-class:: sphx-glr-example-title .. _sphx_glr_api_gallery_optimization_tsp_plot_01_held_karp_travelling_salesman.py: The travelling salesman: Held and Karp's exact algorithm ======================================================== A salesman must visit :math:`n` cities and return home by the shortest route. Trying all :math:`(n-1)!/2` tours is hopeless beyond a dozen cities; Held and Karp (1962) found the optimum in :math:`O(n^2 2^n)` steps by dynamic programming over the *set* of cities visited so far, still the best worst-case bound known. Heuristics are faster but inexact: the nearest-neighbour tour, and Croes's 2-opt move, which reverses a segment whenever that removes a crossing. .. GENERATED FROM PYTHON SOURCE LINES 15-28 .. code-block:: Python import math import time import matplotlib.pyplot as plt import numpy as np from mathematicskit.optimization import distance_matrix, tsp_held_karp, tsp_nearest_neighbor, tsp_two_opt cities = np.random.default_rng(1962).uniform(size=(14, 2)) dist = distance_matrix(cities) n = len(cities) print(f"{n} cities: {math.factorial(n - 1) // 2:,} distinct tours, Held-Karp table of {n * 2 ** (n - 1):,} entries") .. rst-class:: sphx-glr-script-out .. code-block:: none 14 cities: 3,113,510,400 distinct tours, Held-Karp table of 114,688 entries .. GENERATED FROM PYTHON SOURCE LINES 29-31 Three tours ------------- .. GENERATED FROM PYTHON SOURCE LINES 31-58 .. code-block:: Python start = time.perf_counter() exact = tsp_held_karp(dist) elapsed = time.perf_counter() - start nearest = tsp_nearest_neighbor(dist) improved = tsp_two_opt(dist, nearest.tour) for result in (nearest, improved, exact): print(f"{result.method:16s} length {result.length:.4f} ({100 * (result.length / exact.length - 1):5.2f}% above optimal)") print(f"Held-Karp took {elapsed:.2f} s") fig, axes = plt.subplots(1, 3, figsize=(15, 5)) for ax, result, title in zip( axes, (nearest, improved, exact), ("Nearest neighbour", f"2-opt ({len(improved.history) - 1} improving moves)", "Held-Karp: optimal"), strict=True, ): loop = cities[result.tour + [result.tour[0]]] ax.plot(*loop.T, "-", color="tab:blue", lw=1.5) ax.plot(*cities.T, "o", color="tab:red", ms=6) ax.plot(*cities[result.tour[0]], "ks", ms=8) ax.set_title(f"{title}\nlength {result.length:.3f}") ax.set_aspect("equal") ax.set_xticks([]) ax.set_yticks([]) fig.tight_layout() .. image-sg:: /api/gallery/optimization/tsp/images/sphx_glr_plot_01_held_karp_travelling_salesman_001.png :alt: Nearest neighbour length 4.214, 2-opt (5 improving moves) length 3.607, Held-Karp: optimal length 3.607 :srcset: /api/gallery/optimization/tsp/images/sphx_glr_plot_01_held_karp_travelling_salesman_001.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none nearest_neighbor length 4.2137 (16.82% above optimal) two_opt length 3.6069 ( 0.00% above optimal) held_karp length 3.6069 ( 0.00% above optimal) Held-Karp took 0.05 s .. GENERATED FROM PYTHON SOURCE LINES 59-65 How the exact algorithm scales -------------------------------- Each extra city roughly doubles Held-Karp's work, which is why exact methods are reserved for small instances (or for clever branch-and-cut codes such as Concorde), and 2-opt for everything else. .. GENERATED FROM PYTHON SOURCE LINES 65-87 .. code-block:: Python sizes = list(range(6, 15)) times, gaps = [], [] for k in sizes: d = distance_matrix(np.random.default_rng(k).uniform(size=(k, 2))) t0 = time.perf_counter() best = tsp_held_karp(d).length times.append(time.perf_counter() - t0) gaps.append(100 * (tsp_two_opt(d).length / best - 1)) fig, (ax0, ax1) = plt.subplots(1, 2, figsize=(11, 4)) ax0.semilogy(sizes, times, "o-") ax0.set_xlabel("cities") ax0.set_ylabel("Held-Karp time (s)") ax0.set_title(r"$O(n^2 2^n)$ growth") ax1.bar(sizes, gaps) ax1.set_xlabel("cities") ax1.set_ylabel("2-opt tour above optimal (%)") ax1.set_title("2-opt is usually close, sometimes optimal") fig.tight_layout() plt.show() .. image-sg:: /api/gallery/optimization/tsp/images/sphx_glr_plot_01_held_karp_travelling_salesman_002.png :alt: $O(n^2 2^n)$ growth, 2-opt is usually close, sometimes optimal :srcset: /api/gallery/optimization/tsp/images/sphx_glr_plot_01_held_karp_travelling_salesman_002.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 0.274 seconds) .. _sphx_glr_download_api_gallery_optimization_tsp_plot_01_held_karp_travelling_salesman.py: .. only:: html .. container:: sphx-glr-footer sphx-glr-footer-example .. container:: lite-badge .. image:: images/jupyterlite_badge_logo.svg :target: ../../../../lite/lab/index.html?path=api/gallery/optimization/tsp/plot_01_held_karp_travelling_salesman.ipynb :alt: Launch JupyterLite :width: 150 px .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: plot_01_held_karp_travelling_salesman.ipynb ` .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: plot_01_held_karp_travelling_salesman.py ` .. container:: sphx-glr-download sphx-glr-download-zip :download:`Download zipped: plot_01_held_karp_travelling_salesman.zip ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_