<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Algo - Aparté sur le voyageur de commerce
Le voyageur de commerce ou Travelling Salesman Problem en anglais est le problème NP-complet emblématique 
Step1:  Tirer des points aléatoirement et les afficher
Step2:  Distance d'un chemin
Step3:  Visualisation
Step4:  Parcourir toutes les permutations
Step5:  Module tqdm
Utile seulement dans un notebook, très utile pour les impatients.
Step6:  Retournement
Les permutations ça prend du temps même avec les machines d'aujourd'hui.
<ASSISTANT_TASK:>
Python Code:
from jyquickhelper import add_notebook_menu
add_notebook_menu()
%matplotlib inline
Explanation: Algo - Aparté sur le voyageur de commerce
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.
End of explanation
import numpy
points = numpy.random.random((6, 2))
points
Explanation: Tirer des points aléatoirement et les afficher
End of explanation
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])))
Explanation: Distance d'un chemin
End of explanation
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])));
Explanation: Visualisation
End of explanation
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);
Explanation: Parcourir toutes les permutations
End of explanation
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);
Explanation: Module tqdm
Utile seulement dans un notebook, très utile pour les impatients.
End of explanation
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);
Explanation: Retournement
Les permutations ça prend du temps même avec les machines d'aujourd'hui.
End of explanation
<END_TASK>