.. _2021tsprst:

=========================================
Algo - Aparté sur le voyageur de commerce
=========================================


.. only:: html

    **Links:** :download:`notebook <2021_tsp.ipynb>`, :downloadlink:`html <2021_tsp2html.html>`, :download:`python <2021_tsp.py>`, :downloadlink:`slides <2021_tsp.slides.html>`, :githublink:`GitHub|_doc/notebooks/td1a_home/2021_tsp.ipynb|*`


Le voyageur de commerce ou Travelling Salesman Problem en anglais est le
problème NP-complet emblématique : il n’existe pas d’algorithme capable
de trouver la solution optimale en temps polynômial. La seule option est
de parcourir toutes les configurations pour trouver la meilleure. Ce
notebook ne fait qu’aborder le problème.

.. code:: ipython3

    from jyquickhelper import add_notebook_menu
    add_notebook_menu()






.. contents::
    :local:





.. code:: ipython3

    %matplotlib inline

Tirer des points aléatoirement et les afficher
----------------------------------------------

.. code:: ipython3

    import numpy
    points = numpy.random.random((6, 2))
    points




.. parsed-literal::
    array([[0.67838254, 0.59016636],
           [0.79780992, 0.59358808],
           [0.15182002, 0.63237946],
           [0.7280486 , 0.79583856],
           [0.18308128, 0.72824711],
           [0.23948217, 0.66792463]])



Distance d’un chemin
--------------------

.. code:: ipython3

    def distance_chemin(points, chemin):
        dist = 0
        for i in range(1, len(points)):
            dx, dy = points[chemin[i], :] - points[chemin[i-1], :]
            dist += (dx ** 2 + dy ** 2) ** 0.5
        dx, dy = points[chemin[0], :] - points[chemin[-1], :]
        dist += (dx ** 2 + dy ** 2) ** 0.5
        return dist
    
    distance_chemin(points, list(range(points.shape[0])))




.. parsed-literal::
    2.4430548937201975



Visualisation
-------------

.. code:: ipython3

    import matplotlib.pyplot as plt
    
    
    def plot_points(points, chemin):
        fig, ax = plt.subplots(1, 2, figsize=(8, 4))
        
        loop = list(chemin) + [chemin[0]]
        p = points[loop]
        
        ax[0].plot(points[:, 0], points[:, 1], 'o')
        ax[1].plot(p[:, 0], p[:, 1], 'o-')
        ax[1].set_title("dist=%1.2f" % distance_chemin(points, chemin))
        return ax
    
    plot_points(points, list(range(points.shape[0])));



.. image:: 2021_tsp_8_0.png


Parcourir toutes les permutations
---------------------------------

.. code:: ipython3

    from itertools import permutations
    
    def optimisation(points, chemin):
        dist = distance_chemin(points, chemin)
        best = chemin
        for perm in permutations(chemin):
            d = distance_chemin(points, perm)
            if d < dist:
                dist = d
                best = perm
        return best
    
    
    res = optimisation(points, list(range(points.shape[0])))
    plot_points(points, res);



.. image:: 2021_tsp_10_0.png


Module tqdm
-----------

Utile seulement dans un notebook, très utile pour les impatients.

.. code:: ipython3

    from tqdm import tqdm
    
    
    def optimisation(points, chemin):
        dist = distance_chemin(points, chemin)
        best = chemin
        loop = tqdm(permutations(chemin))
        for perm in loop:
            loop.set_description(str(perm))
            d = distance_chemin(points, perm)
            if d < dist:
                dist = d
                best = perm
        return best
    
    
    res = optimisation(points, list(range(points.shape[0])))
    plot_points(points, res);


.. parsed-literal::
    (5, 4, 3, 2, 1, 0): : 720it [00:00, 946.03it/s] 



.. image:: 2021_tsp_12_1.png


Retournement
------------

Les permutations ça prend du temps même avec les machines d’aujourd’hui.

.. code:: ipython3

    def optimisation_retournement(points, chemin):
        dist = distance_chemin(points, chemin)
        best = chemin
        for i in range(1, len(chemin)):
            for j in range(i+1, len(chemin)):
                chemin[i: j] = chemin[j-1: i-1: -1]
                d = distance_chemin(points, chemin)
                if d < dist:
                    dist = d
                else:
                    chemin[i: j] = chemin[j-1: i-1: -1]                
        return chemin
    
    
    res = optimisation_retournement(points, list(range(points.shape[0])))
    plot_points(points, res);



.. image:: 2021_tsp_14_0.png