.. _td1acenoncesession7rst:

======================================================
1A.algo - Programmation dynamique et plus court chemin
======================================================


.. only:: html

    **Links:** :download:`notebook <td1a_cenonce_session7.ipynb>`, :downloadlink:`html <td1a_cenonce_session72html.html>`, :download:`python <td1a_cenonce_session7.py>`, :downloadlink:`slides <td1a_cenonce_session7.slides.html>`, :githublink:`GitHub|_doc/notebooks/td1a_algo/td1a_cenonce_session7.ipynb|*`


La programmation dynamique est une façon des calculs qui revient dans
beaucoup d’algorithmes. Elle s’applique dès que ceux-ci peuvent s’écrire
de façon récurrente.

.. code:: ipython3

    from jyquickhelper import add_notebook_menu
    add_notebook_menu()






.. contents::
    :local:





La `programmation
dynamique <http://fr.wikipedia.org/wiki/Programmation_dynamique>`__ est
une façon de résoudre de manière similaire une classe de problèmes
d’optimisation qui vérifie la même propriété. On suppose qu’il est
possible de découper le problème :math:`P` en plusieurs parties
:math:`P_1`, :math:`P_2`, … Si :math:`S` est la solution optimale du
problème :math:`P`, alors chaque partie :math:`S_1`, :math:`S_2`, … de
cette solution appliquée aux sous-problèmes est aussi optimale.

Par exemple, on cherche le plus court chemin :math:`c(A,B)` entre les
villes :math:`A` et :math:`B`. Si celui-ci passe par la ville :math:`M`
alors les chemins :math:`c(A,M)+c(M,B) = c(A,B)` sont aussi les plus
courts chemins entre les villes :math:`A,M` et :math:`M,B`. La
démonstration se fait simplement par l’absurde : si la distance
:math:`c(A,M)` n’est pas optimale alors il est possible de constuire un
chemin plus court entre les villes :math:`A` et :math:`B`. Cela
contredit l’hypothèse de départ.

Ces problèmes ont en règle générale une expression simple sous forme de
récurrence : si on sait résoudre le problème pour un échantillon de
taille :math:`n`, on appelle cette solution :math:`S(n)` alors on peut
facilement la solution :math:`S(n+1)` en fonction de :math:`S(n)`.
Parfois cette récurrence va au delà :
:math:`S(n+1) = f(S(n), S(n-1), ..., S(0))`.

Les données
-----------

On récupère le fichier ``matrix_distance_7398.txt`` depuis
`matrix_distance_7398.zip <http://www.xavierdupre.fr/enseignement/complements/matrix_distance_7398.zip>`__
qui contient des distances entre différentes villes (pas toutes).

.. code:: ipython3

    import pyensae.datasource
    pyensae.datasource.download_data("matrix_distance_7398.zip", website  = "xd")




.. parsed-literal::
    ['.\\matrix_distance_7398.txt']



On peut lire ce fichier soit avec le module
`pandas <http://pandas.pydata.org/>`__ introduit lors de la séance 10
`TD 10 : DataFrame et
Matrice <http://www.xavierdupre.fr/app/ensae_teaching_cs/helpsphinx/notebooks/td1a_cenonce_session_10.html#io>`__
:

.. code:: ipython3

    import pandas
    df = pandas.read_csv("matrix_distance_7398.txt", sep="\t", header=None, names=["v1","v2","distance"])
    df.head()






.. raw:: html

    <div>
    <table border="1" class="dataframe">
      <thead>
        <tr style="text-align: right;">
          <th></th>
          <th>v1</th>
          <th>v2</th>
          <th>distance</th>
        </tr>
      </thead>
      <tbody>
        <tr>
          <th>0</th>
          <td>Boulogne-Billancourt</td>
          <td>Beauvais</td>
          <td>85597</td>
        </tr>
        <tr>
          <th>1</th>
          <td>Courbevoie</td>
          <td>Sevran</td>
          <td>26564</td>
        </tr>
        <tr>
          <th>2</th>
          <td>Colombes</td>
          <td>Alfortville</td>
          <td>36843</td>
        </tr>
        <tr>
          <th>3</th>
          <td>Bagneux</td>
          <td>Marcq-En-Baroeul</td>
          <td>233455</td>
        </tr>
        <tr>
          <th>4</th>
          <td>Suresnes</td>
          <td>Gennevilliers</td>
          <td>10443</td>
        </tr>
      </tbody>
    </table>
    </div>



Le membre ``values`` se comporte comme une matrice, une liste de listes
:

.. code:: ipython3

    matrice = df.values
    matrice[:5]




.. parsed-literal::
    array([['Boulogne-Billancourt', 'Beauvais', 85597],
           ['Courbevoie', 'Sevran', 26564],
           ['Colombes', 'Alfortville', 36843],
           ['Bagneux', 'Marcq-En-Baroeul', 233455],
           ['Suresnes', 'Gennevilliers', 10443]], dtype=object)



On peut aussi utiliser le petit exemple qui a été présenté lors de la
séance 4 sur les fichiers `TD 4 : Modules, fichiers, expressions
régulières <http://www.xavierdupre.fr/app/ensae_teaching_cs/helpsphinx/notebooks/td1a_cenonce_session4.html#file>`__.
Les données se présente sous forme de matrice. Les deux premières
colonnes sont des chaînes de caractères, la dernière est une valeur
numérique qu’il faut convertir.

.. code:: ipython3

    with open ("matrix_distance_7398.txt", "r") as f :
        matrice = [ row.strip(' \n').split('\t') for row in f.readlines() ]
    for row in matrice:
        row[2] = float(row[2])
    print(matrice[:5])


.. parsed-literal::
    [['Boulogne-Billancourt', 'Beauvais', 85597.0], ['Courbevoie', 'Sevran', 26564.0], ['Colombes', 'Alfortville', 36843.0], ['Bagneux', 'Marcq-En-Baroeul', 233455.0], ['Suresnes', 'Gennevilliers', 10443.0]]


Chaque ligne définit un voyage entre deux villes effectué d’une traite,
sans étape. Les accents ont été supprimés du fichier.

Exercice 1
----------

Construire la liste des villes sans doublons.


Exercice 2
----------

Constuire un dictionnaire ``{ (a,b) : d, (b,a) : d }`` où ``a,b`` sont
des villes et ``d`` la distance qui les sépare ?

On veut calculer la distance entre la ville de ``Charleville-Mezieres``
et ``Bordeaux`` ? Est-ce que cette distance existe dans la liste des
distances dont on dispose ?


Algorithme du plus court chemin
-------------------------------

On créé un tableau ``d[v]`` qui contient ou contiendra la distance
optimale entre les villes ``v`` et ``Charleville-Mezieres``. La valeur
qu’on cherche est ``d['Bordeaux']``. On initialise le tableau comme suit
:


-  ``d['Charleville-Mezieres'] = 0``
-  ``d[v] = infini`` pour tout :math:`v \neq`
   ``'Charleville-Mezieres'``.

Exercice 3
----------

Quelles sont les premières cases qu’on peut remplir facilement ?


Exercice 4
----------

Soit une ville :math:`v` et une autre :math:`w`, on s’aperçoit que
:math:`d[w] > d[v] + dist[w,v]`. Que proposez-vous de faire ? En déduire
un algorithme qui permet de déterminer la distance la plus courte entre
Charleville-Mezieres et Bordeaux.

Si la solution vous échappe encore, vous pouvez vous inspirer de
l’\ `Algorithme de
Djikstra <http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra>`__.


La répartition des skis
-----------------------

Ce problème est un exemple pour lequel il faut d’abord prouver que la
solution vérifie une certaine propriété avant de pouvoir lui appliquer
une solution issue de la programmation dynamique.

:math:`N=10` skieurs rentrent dans un magasins pour louer 10 paires de
skis (parmi :math:`M>N`). On souhaite leur donner à tous une paire qui
leur convient (on suppose que la taille de la paire de skis doit être au
plus proche de la taille du skieurs. On cherche donc à minimiser :

:math:`\arg \min_\sigma \sum_{i=1}^{N} \left| t_i - s_{\sigma(i)} \right|`

Où :math:`\sigma` est un ensemble de :math:`N` paires de skis parmi
:math:`M` (un `arrangement <http://fr.wikipedia.org/wiki/Arrangement>`__
pour être plus précis).

A première vue, il faut chercher la solution du problème dans l’ensemble
des arrangements de :math:`N` paires parmi :math:`M`. Mais si on ordonne
les paires et les skieurs par taille croissantes :
:math:`t_1 \leqslant t_2 \leqslant ... \leqslant t_N` (tailles de
skieurs) et :math:`s_1 \leqslant s_2 \leqslant ... \leqslant s_M`
(tailles de skis), résoudre le problème revient à prendre les skieurs
dans l’ordre croissant et à les placer en face d’une paire dans l’ordre
où elles viennent. C’est comme si on insérait des espaces dans la
séquence des skieurs sans changer l’ordre :

:math:`\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline t_1 & & t_2 & t_3 & & & t_4 & ... & t_{N-1} & & t_{N} & \\ \hline s_1 & s_2 & s_3 & s_4 & s_5 & s_6 & s_7 & ... & s_{M-3} & s_{M-2} & s_{M-1} & s_M \\ \hline \end{array}`


Exercice facultatif
-------------------

Il faut d’abord prouver que l’algorithme suggéré ci-dessus permet bien
d’obtenir la solution optimale.

Exercice 5
----------

Après avoir avoir trié les skieurs et les paires par tailles
croissantes. On définit :

:math:`p(n,m) = \sum_{i=1}^{n} \left| t_i - s_{\sigma_m^*(i)} \right|`

Où :math:`\sigma_m^*` est le meilleur choix possible de :math:`n` paires
de skis parmi les :math:`m` premières. Exprimer :math:`p(n,m)` par
récurrence (en fonction de :math:`p(n,m-1)` et :math:`p(n-1,m-1)`. On
suppose qu’un skieur sans paire de ski correspond au cas où la paire est
de taille nulle.


Exercice 6
----------

Ecrire une fonction qui calcule l’erreur pour la distribution optimale ?
On pourra choisir des skieurs et des paires de tailles aléatoires par
exemple.

.. code:: ipython3

    import random
    skieurs = [ random.gauss(1.75, 0.1) for i in range(0,10) ]
    paires  = [ random.gauss(1.75, 0.1) for i in range(0,15) ]
    skieurs.sort()
    paires.sort()
    print(skieurs)
    print(paires)

Exercice 7
----------

Quelle est la meilleure distribution des skis aux skieurs ?


Exercice 8
----------

Quels sont les coûts des deux algorithmes (plus court chemin et ski) ?


Prolongements : degré de séparation sur Facebook
------------------------------------------------

Le plus court chemin dans un graphe est un des algorithmes les plus
connus en programmation. Il permet de déterminer la solution en un coût
**polynômial** - chaque itération est en :math:`O(n^2)`. La
programmation dynamique caractèrise le passage d’une vision combinatoire
à une compréhension récursif du même problème. Dans le cas du plus court
chemin, l’approche combinatoire consiste à énumérer tous les chemins du
graphe. L’approche dynamique consiste à démontrer que la première
approche combinatoire aboutit à un calcul très redondant. On note
:math:`e(v,w)` la matrice des longueurs des routes,
:math:`e(v,w) = \infty` s’il n’existe aucune route entre les villes
:math:`v` et :math:`w`. On suppose que :math:`e(v,w)=e(w,v)`. La
construction du tableau ``d`` se définit de manière itérative et
récursive comme suit :

**Etape 0**

:math:`d(v) = \infty, \, \forall v \in V`

**Etape :math:`n`**

:math:`d(v) = \left \{ \begin{array}{ll} 0 & si \; v = v_0 \\ \min \{ d(w) + e(v,w) \, | \, w \in V \} & sinon \end{array} \right.`
où :math:`v_0 =` ``'Charleville-Mezieres'``

Tant que l’étape :math:`n` continue à faire des mises à jour
(:math:`\sum_v d(v)` diminue), on répète l’étape :math:`n`. Ce même
algorithme peut être appliqué pour déterminer le `degré de
séparation <http://www.atlantico.fr/decryptage/theorie-six-degres-separation-relations-entre-individus-facebook-nombre-amis-229803.html>`__
dans un réseau social. L’agorithme s’applique presque tel quel à
condition de définir ce que sont une ville et une distance entre villes
dans ce nouveau graphe. Vous pouvez tester vos idées sur cet exemple de
graphe `Social circles:
Facebook <http://snap.stanford.edu/data/egonets-Facebook.html>`__.
L’algorithme de
`Dikjstra <http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra>`__
calcule le plus court chemin entre deux noeuds d’un graphe, l’algorithme
de
`Bellman-Ford <http://fr.wikipedia.org/wiki/Algorithme_de_Bellman-Ford>`__
est une variante qui calcule toutes les distances des plus courts chemin
entre deux noeuds d’un graphe.

.. code:: ipython3

    import pyensae.datasource
    files = pyensae.datasource.download_data("facebook.tar.gz",website="http://snap.stanford.edu/data/")
    fe = [ f for f in files if "edge" in f ]
    fe

Il faut décompresser ce fichier avec `7zip <http://www.7-zip.org/>`__ si
vous utilisez ``pysense < 0.8``. Sous Linux (et Mac), il faudra utiliser
une commande décrite ici `tar <http://doc.ubuntu-fr.org/tar>`__.

.. code:: ipython3

    import pandas
    df = pandas.read_csv("facebook/1912.edges", sep=" ", names=["v1","v2"])
    print(df.shape)
    df.head()