.. _sphx_glr_api_gallery_optimization_tsp:

The travelling salesman problem
---------------------------------

Nearest-neighbour and 2-opt heuristics against the exact Held-Karp
algorithm.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="A salesman must visit n cities and return home by the shortest route. Trying all (n-1)!/2 tours is hopeless beyond a dozen cities; Held and Karp (1962) found the optimum in 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&#x27;s 2-opt move, which reverses a segment whenever that removes a crossing.">

.. only:: html

  .. image:: /api/gallery/optimization/tsp/images/thumb/sphx_glr_plot_01_held_karp_travelling_salesman_thumb.png
    :alt:

  :doc:`/api/gallery/optimization/tsp/plot_01_held_karp_travelling_salesman`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">The travelling salesman: Held and Karp's exact algorithm</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>


.. toctree::
   :hidden:

   /api/gallery/optimization/tsp/plot_01_held_karp_travelling_salesman