.. _td1acorrectionsession7rst:

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


.. only:: html

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


Correction.

.. code:: ipython3

    from jyquickhelper import add_notebook_menu
    add_notebook_menu()






.. contents::
    :local:





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']



.. code:: ipython3

    import pandas
    df = pandas.read_csv("matrix_distance_7398.txt", sep="\t", header=None, names=["v1","v2","distance"])
    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)



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

.. code:: ipython3

    vil = { }
    for row in matrice :
        vil [row[0]] = 0
        vil [row[1]] = 1
    vil = list(vil.keys())
    print (len(vil))


.. parsed-literal::
    196


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

La distance n’existe pas encore. L’exception du court programme suivant
le montre. Rejoindre Bordeaux depuis Charleville nécessite plusieurs
étapes.

.. code:: ipython3

    dist = { }
    for row in matrice :
        a = row[0]
        b = row[1]
        dist[a,b] = dist[b,a] = row[2]
    print (len(dist))


.. parsed-literal::
    7888


.. code:: ipython3

    print ( dist["Charleville-Mezieres","Bordeaux"] )  # elle n'existe pas encore


::

    ---------------------------------------------------------------------------
    KeyError                                  Traceback (most recent call last)
    <ipython-input-6-0227958f5453> in <module>()
    ----> 1 print ( dist["Charleville-Mezieres","Bordeaux"] )  # elle n'existe pas encore
    
    KeyError: ('Charleville-Mezieres', 'Bordeaux')


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

On peut remplir facilement toutes les cases correspondant aux villes
reliées à Charleville-Mézières, c’est-à-dire toutes les villes
accessibles en une étape.

.. code:: ipython3

    d = { }
    d['Charleville-Mezieres'] = 0
    for v in vil : d[v] = 1e10
    for v,w in dist :
        if v == 'Charleville-Mezieres': 
            d[w] = dist[v,w]
    print(len(d))        


.. parsed-literal::
    196


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

Si on découvre que :math:`d[w] > d[v] + dist[w,v]`, cela veut dire qu’il
faut mettre à jour le tableau :math:`d` car il ne contient pas la
distance optimale. On répète cela pour toutes les paires :math:`(v,w)`.

.. code:: ipython3

    for v,w in dist :
        d2 = d[v] + dist[v,w]
        if d2 < d[w] :
            d[w] = d2
    print ( d["Bordeaux"] )        


.. parsed-literal::
    798824


On trouve 813197 mètres pour la distance (Charleville-Mezieres,
Bordeaux). Ce n’est pas forcément la meilleure. Pour être sûr, il faut
répéter la même itération autant de fois qu’il y a de villes (car le
plus long chemin contient autant d’étapes qu’il y a de villes).

.. code:: ipython3

    for i in range(0,len(d)) :        
        for v,w in dist :
            d2 = d[v] + dist[v,w]
            if d2 < d[w] :
                d[w] = d2
    print ( d["Bordeaux"] )             


.. parsed-literal::
    795670


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

Pour montrer que l’algorithme suggéré permettra d’obtenir la solution
optimale, il faut montrer qu’il n’est pas nécessaire d’envisager aucun
autre ordre que celui des skieurs et des paires triés par taille
croissante. Cela ne veut pas dire qu’un autre ordre ne sera pas optimal,
cela veut dire que pour obtenir l’appariement de coût optimal, il existe
une solution pour laquelle skieurs et skis sont rangés dans l’ordre.

On considère donc un appariement :math:`\sigma` qui associé le skieur
:math:`t_i` à la paire :math:`s_{\sigma(i)}`. Il suffit que montrer que
:

:math:`\forall i,j, \; t_i \leqslant t_j \Longleftrightarrow s_{\sigma(i)} \leqslant s_{\sigma(j)}`

Pour montrer cela, on fait un raisonnement par l’absurde : pour
:math:`i` et :math:`j` quelconques, on suppose qu’il existe un
appariement optimal tel que :math:`t_i \geqslant t_j` et
:math:`s_{\sigma(i)} < s_{\sigma(j)}`. Le coût :math:`C(\sigma)` de cet
appariement est :

:math:`C(\sigma) = \sum_{k=1}^{N} \left| t_k - s_{\sigma(k)} \right| = \alpha + \left| t_i - s_{\sigma(i)} \right| + \left| t_j - s_{\sigma(j)} \right|`

Le coût de l’appariement en permutant les skieurs :math:`i` et :math:`j`
(donc en les rangeant dans l’ordre croissant) est :

:math:`C(\sigma') = \sum_{k=1}^{N} \left| t_k - s_{\sigma(k)} \right| = \alpha + \left| t_j - s_{\sigma(i)} \right| + \left| t_i - s_{\sigma(j)} \right|`

On calcule :

:math:`C(\sigma) - C(\sigma') = \left| t_i - s_{\sigma(i)} \right| + \left| t_j - s_{\sigma(j)} \right| - \left| t_j - s_{\sigma(i)} \right| - \left| t_i - s_{\sigma(j)} \right|`

Premier cas :math:`t_j \geqslant s_{\sigma(i)}` et
:math:`t_i > t_j \geqslant s_{\sigma(i)}` et :

:math:`\begin{array}{rcl} C(\sigma) - C(\sigma') &=& \left| t_i - s_{\sigma(i)} \right| + \left| t_j - s_{\sigma(j)} \right| - \left( t_j - s_{\sigma(j)} + s_{\sigma(j)} - s_{\sigma(i)} \right) - \left| t_i - s_{\sigma(j)} \right| \\ &=& t_i - s_{\sigma(i)} + \left| t_j - s_{\sigma(j)} \right| - \left( t_j - s_{\sigma(j)} \right) - \left( s_{\sigma(j)} - s_{\sigma(i)} \right) - \left| t_i - s_{\sigma(j)} \right| \\ &=& t_i - s_{\sigma(i)}- \left| t_i - s_{\sigma(i)} \right| + \left| t_j - s_{\sigma(j)} \right| - \left( t_j - s_{\sigma(j)} \right) \\ &=& \left| t_j - s_{\sigma(j)} \right| - \left( t_j - s_{\sigma(j)} \right|) \\ &\geqslant& 0 \end{array}`

Second cas :math:`t_j \leqslant s_{\sigma(i)}` et
:math:`t_j \leqslant s_{\sigma(i)} \leqslant s_{\sigma(j)}` et :

:math:`\begin{array}{rcl} C(\sigma) - C(\sigma') &=& \left| t_i - s_{\sigma(i)} \right| + s_{\sigma(j)} -t_j - \left( s_{\sigma(i)} - t_j\right) - \left| t_i - s_{\sigma(j)} \right| \\ &=& \left| t_i - s_{\sigma(i)} \right| + s_{\sigma(j)} - s_{\sigma(i)} - \left| t_i - s_{\sigma(j)} \right| \\ &\geqslant& \left| t_i - s_{\sigma(j)}\right| - \left| s_{\sigma(j)} - s_{\sigma(i)} \right| + s_{\sigma(j)} - s_{\sigma(i)} - \left| t_i - s_{\sigma(j)} \right| \\ &\geqslant& 0 \end{array}`

Dans les deux cas, on montre donc qu’il existe un appariement meilleur
ou équivalent en permutant les deux skieurs :math:`i` et :math:`j`,
c’est-à-dire en les triant par ordre croissant de taille. Nous avons
donc montré que, si les paires de ski sont triées par ordre croissant de
taille, il existe necéssairement un appariement optimal pour lequel les
skieurs sont aussi triés par ordre croissant. Lors de la recherche de
cet appariement optimal, on peut se restreindre à ces cas de figure.

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

:math:`p(n,m) = \min \left\{ p(n-1,m-1) + \left| t_n - s_m \right|, p(n,m-1) \right\}`

Lorsqu’on considère le meilleur appariement des paires :math:`1..m` et
des skieurs :math:`1..n`, il n’y a que deux choix possibles pour la
paire :math:`m` :


-  soit elle n’est associée à aucun skieur et dans ce cas :
   :math:`p(n,m) = p(n,m-1)`,
-  soit elle est associée au skieur :math:`n` (et à aucun autre) :
   :math:`p(n,m) = p(n-1,m-1) + \left| t_n - s_m \right|`.

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

.. 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()
    
    p = { }
    p [-1,-1] = 0
    for n,taille in enumerate(skieurs) : p[n,-1] = p[n-1,-1] + taille
    for m,paire  in enumerate(paires ) : p[-1,m] = 0
    for n,taille in enumerate(skieurs) :
        for m,paire in enumerate(paires) :
            p1 = p.get ( (n  ,m-1), 1e10 ) 
            p2 = p.get ( (n-1,m-1), 1e10 ) + abs(taille - paire)
            p[n,m] = min(p1,p2)
            
    print (p[len(skieurs)-1,len(paires)-1])


.. parsed-literal::
    0.40180280093469833


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

Il faut imaginer que :math:`p` peut être représenté sous forme de
matrice et qu’à chaque fois, on prend le meilleur chemin parmi 2 :


-  Chemin horizontal : on ne choisit pas la paire :math:`m`.
-  Chemin diagonal : on choisit la paire :math:`m` pour le skieur
   :math:`n`

.. code:: ipython3

    from pyquickhelper.helpgen import NbImage
    NbImage('graph_notebook_ski.png') 




.. image:: td1a_correction_session7_23_0.png



``\xymatrix{  & m-1  & m \\      n-1   &  p(n-1,m-1) \ar[dr]^{ + \abs{t_n - s_m}} &  p(n-1,m) \\      n     &  p(n,m-1)   \ar[r] & p(n,m) \\ }``

.. code:: ipython3

    p = { }
    p [-1,-1] = 0
    best = { }
    for n,taille in enumerate(skieurs) : p[n,-1] = p[n-1,-1] + taille
    for m,paire  in enumerate(paires ) : p[-1,m] = 0
    for n,taille in enumerate(skieurs) :
        for m,paire in enumerate(paires) :
            p1 = p.get ( (n  ,m-1), 1e10 ) 
            p2 = p.get ( (n-1,m-1), 1e10 ) + abs(taille - paire)
            p[n,m] = min(p1,p2)
            
            if p[n,m] == p1 : best [n,m] = n,m-1
            else : best [n,m] = n-1,m-1
            
    print (p[len(skieurs)-1,len(paires)-1])
    
    chemin = [ ]
    pos = len(skieurs)-1,len(paires)-1
    while pos in best :
        print (pos)
        chemin.append(pos)
        pos = best[pos]
    chemin.reverse()
    print (chemin)


.. parsed-literal::
    0.40180280093469833
    (9, 14)
    (8, 13)
    (7, 12)
    (6, 11)
    (5, 10)
    (4, 9)
    (3, 8)
    (2, 7)
    (1, 6)
    (0, 5)
    (0, 4)
    [(0, 4), (0, 5), (1, 6), (2, 7), (3, 8), (4, 9), (5, 10), (6, 11), (7, 12), (8, 13), (9, 14)]


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

Les deux algorithmes ont un coût quadratique.

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

.. code:: ipython3

    import pyensae.datasource # utiliser pyensae >= 0.8
    files = pyensae.datasource.download_data("facebook.tar.gz",website="http://snap.stanford.edu/data/")
    import pandas
    df = pandas.read_csv("facebook/1912.edges", sep=" ", names=["v1","v2"])
    print(df.shape)
    df.head()


.. parsed-literal::
    (60050, 2)






.. raw:: html

    <div>
    <table border="1" class="dataframe">
      <thead>
        <tr style="text-align: right;">
          <th></th>
          <th>v1</th>
          <th>v2</th>
        </tr>
      </thead>
      <tbody>
        <tr>
          <th>0</th>
          <td>2290</td>
          <td>2363</td>
        </tr>
        <tr>
          <th>1</th>
          <td>2346</td>
          <td>2025</td>
        </tr>
        <tr>
          <th>2</th>
          <td>2140</td>
          <td>2428</td>
        </tr>
        <tr>
          <th>3</th>
          <td>2201</td>
          <td>2506</td>
        </tr>
        <tr>
          <th>4</th>
          <td>2425</td>
          <td>2557</td>
        </tr>
      </tbody>
    </table>
    </div>