{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 1A.algo - Programmation dynamique et plus court chemin\n", "\n", "La programmation dynamique est une fa\u00e7on des calculs qui revient dans beaucoup d'algorithmes. Elle s'applique d\u00e8s que ceux-ci peuvent s'\u00e9crire de fa\u00e7on r\u00e9currente."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["
run previous cell, wait for 2 seconds
\n", ""], "text/plain": [""]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["La [programmation dynamique](http://fr.wikipedia.org/wiki/Programmation\\_dynamique) est une fa\u00e7on de r\u00e9soudre de mani\u00e8re similaire une classe de probl\u00e8mes d'optimisation qui v\u00e9rifie la m\u00eame propri\u00e9t\u00e9. On suppose qu'il est possible de d\u00e9couper le probl\u00e8me $P$ en plusieurs parties $P_1$, $P_2$, ... Si $S$ est la solution optimale du probl\u00e8me $P$, alors chaque partie $S_1$, $S_2$, ... de cette solution appliqu\u00e9e aux sous-probl\u00e8mes est aussi optimale.\n", "\n", "Par exemple, on cherche le plus court chemin $c(A,B)$ entre les villes $A$ et $B$. Si celui-ci passe par la ville $M$ alors les chemins $c(A,M)+c(M,B) = c(A,B)$ sont aussi les plus courts chemins entre les villes $A,M$ et $M,B$. La d\u00e9monstration se fait simplement par l'absurde : si la distance $c(A,M)$ n'est pas optimale alors il est possible de constuire un chemin plus court entre les villes $A$ et $B$. Cela contredit l'hypoth\u00e8se de d\u00e9part.\n", "\n", "Ces probl\u00e8mes ont en r\u00e8gle g\u00e9n\u00e9rale une expression simple sous forme de r\u00e9currence : si on sait r\u00e9soudre le probl\u00e8me pour un \u00e9chantillon de taille $n$, on appelle cette solution $S(n)$ alors on peut facilement la solution $S(n+1)$ en fonction de $S(n)$. Parfois cette r\u00e9currence va au del\u00e0 : $S(n+1) = f(S(n), S(n-1), ..., S(0))$."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Les donn\u00e9es\n", "\n", "On r\u00e9cup\u00e8re 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\u00e9rentes villes (pas toutes)."]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [{"data": {"text/plain": ["['.\\\\matrix_distance_7398.txt']"]}, "execution_count": 3, "metadata": {}, "output_type": "execute_result"}], "source": ["import pyensae.datasource\n", "pyensae.datasource.download_data(\"matrix_distance_7398.zip\", website = \"xd\")"]}, {"cell_type": "markdown", "metadata": {}, "source": ["On peut lire ce fichier soit avec le module [pandas](http://pandas.pydata.org/) introduit lors de la s\u00e9ance 10 [TD 10 : DataFrame et Matrice](http://www.xavierdupre.fr/app/ensae_teaching_cs/helpsphinx/notebooks/td1a_cenonce_session_10.html#io) :"]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [{"data": {"text/html": ["
\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
v1v2distance
0Boulogne-BillancourtBeauvais85597
1CourbevoieSevran26564
2ColombesAlfortville36843
3BagneuxMarcq-En-Baroeul233455
4SuresnesGennevilliers10443
\n", "
"], "text/plain": [" v1 v2 distance\n", "0 Boulogne-Billancourt Beauvais 85597\n", "1 Courbevoie Sevran 26564\n", "2 Colombes Alfortville 36843\n", "3 Bagneux Marcq-En-Baroeul 233455\n", "4 Suresnes Gennevilliers 10443"]}, "execution_count": 4, "metadata": {}, "output_type": "execute_result"}], "source": ["import pandas\n", "df = pandas.read_csv(\"matrix_distance_7398.txt\", sep=\"\\t\", header=None, names=[\"v1\",\"v2\",\"distance\"])\n", "df.head()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Le membre ``values`` se comporte comme une matrice, une liste de listes :"]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [{"data": {"text/plain": ["array([['Boulogne-Billancourt', 'Beauvais', 85597],\n", " ['Courbevoie', 'Sevran', 26564],\n", " ['Colombes', 'Alfortville', 36843],\n", " ['Bagneux', 'Marcq-En-Baroeul', 233455],\n", " ['Suresnes', 'Gennevilliers', 10443]], dtype=object)"]}, "execution_count": 5, "metadata": {}, "output_type": "execute_result"}], "source": ["matrice = df.values\n", "matrice[:5]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["On peut aussi utiliser le petit exemple qui a \u00e9t\u00e9 pr\u00e9sent\u00e9 lors de la s\u00e9ance 4 sur les fichiers [TD 4 : Modules, fichiers, expressions r\u00e9guli\u00e8res](http://www.xavierdupre.fr/app/ensae_teaching_cs/helpsphinx/notebooks/td1a_cenonce_session4.html#file). Les donn\u00e9es se pr\u00e9sente sous forme de matrice. Les deux premi\u00e8res colonnes sont des cha\u00eenes de caract\u00e8res, la derni\u00e8re est une valeur num\u00e9rique qu'il faut convertir."]}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["[['Boulogne-Billancourt', 'Beauvais', 85597.0], ['Courbevoie', 'Sevran', 26564.0], ['Colombes', 'Alfortville', 36843.0], ['Bagneux', 'Marcq-En-Baroeul', 233455.0], ['Suresnes', 'Gennevilliers', 10443.0]]\n"]}], "source": ["with open (\"matrix_distance_7398.txt\", \"r\") as f :\n", " matrice = [ row.strip(' \\n').split('\\t') for row in f.readlines() ]\n", "for row in matrice:\n", " row[2] = float(row[2])\n", "print(matrice[:5])"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Chaque ligne d\u00e9finit un voyage entre deux villes effectu\u00e9 d'une traite, sans \u00e9tape. Les accents ont \u00e9t\u00e9 supprim\u00e9s du fichier."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 1\n", "\n", "Construire la liste des villes sans doublons."]}, {"cell_type": "code", "execution_count": 6, "metadata": {"collapsed": true}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 2\n", "\n", "Constuire un dictionnaire ``{ (a,b) : d, (b,a) : d }`` o\u00f9 ``a,b`` sont des villes et ``d`` la distance qui les s\u00e9pare ?\n", "\n", "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 ?"]}, {"cell_type": "code", "execution_count": 7, "metadata": {"collapsed": true}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## Algorithme du plus court chemin\n", "\n", "On cr\u00e9\u00e9 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 :\n", "\n", "- ``d['Charleville-Mezieres'] = 0``\n", "- ``d[v] = infini`` pour tout $v \\neq$ ``'Charleville-Mezieres'``."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 3\n", "\n", "Quelles sont les premi\u00e8res cases qu'on peut remplir facilement ?"]}, {"cell_type": "code", "execution_count": 8, "metadata": {"collapsed": true}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 4\n", "\n", "Soit une ville $v$ et une autre $w$, on s'aper\u00e7oit que $d[w] > d[v] + dist[w,v]$. Que proposez-vous de faire ? En d\u00e9duire un algorithme qui permet de d\u00e9terminer la distance la plus courte entre Charleville-Mezieres et Bordeaux. \n", "\n", "Si la solution vous \u00e9chappe encore, vous pouvez vous inspirer de l'[Algorithme de Djikstra](http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra)."]}, {"cell_type": "code", "execution_count": 9, "metadata": {"collapsed": true}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## La r\u00e9partition des skis\n", "\n", "Ce probl\u00e8me est un exemple pour lequel il faut d'abord prouver que la solution v\u00e9rifie une certaine propri\u00e9t\u00e9 avant de pouvoir lui appliquer une solution issue de la programmation dynamique.\n", "\n", "$N=10$ skieurs rentrent dans un magasins pour louer 10 paires de skis (parmi $M>N$). On souhaite leur donner \u00e0 tous une paire qui leur convient (on suppose que la taille de la paire de skis doit \u00eatre au plus proche de la taille du skieurs. On cherche donc \u00e0 minimiser :\n", "\n", "$\\arg \\min_\\sigma \\sum_{i=1}^{N} \\left| t_i - s_{\\sigma(i)} \\right|$\n", "\n", "O\u00f9 $\\sigma$ est un ensemble de $N$ paires de skis parmi $M$ (un [arrangement](http://fr.wikipedia.org/wiki/Arrangement) pour \u00eatre plus pr\u00e9cis).\n", "\n", "A premi\u00e8re vue, il faut chercher la solution du probl\u00e8me dans l'ensemble des arrangements de $N$ paires parmi $M$. Mais si on ordonne les paires et les skieurs par taille croissantes : $t_1 \\leqslant t_2 \\leqslant ... \\leqslant t_N$ (tailles de skieurs) et $s_1 \\leqslant s_2 \\leqslant ... \\leqslant s_M$ (tailles de skis), r\u00e9soudre le probl\u00e8me revient \u00e0 prendre les skieurs dans l'ordre croissant et \u00e0 les placer en face d'une paire dans l'ordre o\u00f9 elles viennent. C'est comme si on ins\u00e9rait des espaces dans la s\u00e9quence des skieurs sans changer l'ordre :\n", "\n", "$\\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}$"]}, {"cell_type": "code", "execution_count": 10, "metadata": {"collapsed": true}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice facultatif\n", "\n", "Il faut d'abord prouver que l'algorithme sugg\u00e9r\u00e9 ci-dessus permet bien d'obtenir la solution optimale."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 5\n", "\n", "Apr\u00e8s avoir avoir tri\u00e9 les skieurs et les paires par tailles croissantes. On d\u00e9finit :\n", "\n", "$p(n,m) = \\sum_{i=1}^{n} \\left| t_i - s_{\\sigma_m^*(i)} \\right|$ \n", "\n", "O\u00f9 $\\sigma_m^*$ est le meilleur choix possible de $n$ paires de skis parmi les $m$ premi\u00e8res. Exprimer $p(n,m)$ par r\u00e9currence (en fonction de $p(n,m-1)$ et $p(n-1,m-1)$. On suppose qu'un skieur sans paire de ski correspond au cas o\u00f9 la paire est de taille nulle."]}, {"cell_type": "code", "execution_count": 11, "metadata": {"collapsed": true}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 6\n", "\n", "Ecrire une fonction qui calcule l'erreur pour la distribution optimale ? On pourra choisir des skieurs et des paires de tailles al\u00e9atoires par exemple."]}, {"cell_type": "code", "execution_count": 12, "metadata": {"collapsed": true}, "outputs": [], "source": ["import random\n", "skieurs = [ random.gauss(1.75, 0.1) for i in range(0,10) ]\n", "paires = [ random.gauss(1.75, 0.1) for i in range(0,15) ]\n", "skieurs.sort()\n", "paires.sort()\n", "print(skieurs)\n", "print(paires)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 7\n", "\n", "Quelle est la meilleure distribution des skis aux skieurs ?"]}, {"cell_type": "code", "execution_count": 13, "metadata": {"collapsed": true}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 8\n", "\n", "Quels sont les co\u00fbts des deux algorithmes (plus court chemin et ski) ?"]}, {"cell_type": "code", "execution_count": 14, "metadata": {"collapsed": true}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## Prolongements : degr\u00e9 de s\u00e9paration sur Facebook\n", "\n", "Le plus court chemin dans un graphe est un des algorithmes les plus connus en programmation. Il permet de d\u00e9terminer la solution en un co\u00fbt **polyn\u00f4mial** - chaque it\u00e9ration est en $O(n^2)$. La programmation dynamique caract\u00e8rise le passage d'une vision combinatoire \u00e0 une compr\u00e9hension r\u00e9cursif du m\u00eame probl\u00e8me. Dans le cas du plus court chemin, l'approche combinatoire consiste \u00e0 \u00e9num\u00e9rer tous les chemins du graphe. L'approche dynamique consiste \u00e0 d\u00e9montrer que la premi\u00e8re approche combinatoire aboutit \u00e0 un calcul tr\u00e8s redondant. On note $e(v,w)$ la matrice des longueurs des routes, $e(v,w) = \\infty$ s'il n'existe aucune route entre les villes $v$ et $w$. On suppose que $e(v,w)=e(w,v)$. La construction du tableau ``d`` se d\u00e9finit de mani\u00e8re it\u00e9rative et r\u00e9cursive comme suit :\n", "\n", "**Etape 0**\n", "\n", "$d(v) = \\infty, \\, \\forall v \\in V$\n", "\n", "**Etape $n$**\n", "\n", "$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\u00f9 $v_0 =$ ``'Charleville-Mezieres'``\n", "\n", "\n", "Tant que l'\u00e9tape $n$ continue \u00e0 faire des mises \u00e0 jour ($\\sum_v d(v)$ diminue), on r\u00e9p\u00e8te l'\u00e9tape $n$. Ce m\u00eame algorithme peut \u00eatre appliqu\u00e9 pour d\u00e9terminer le [degr\u00e9 de s\u00e9paration](http://www.atlantico.fr/decryptage/theorie-six-degres-separation-relations-entre-individus-facebook-nombre-amis-229803.html) dans un r\u00e9seau social. L'agorithme s'applique presque tel quel \u00e0 condition de d\u00e9finir ce que sont une ville et une distance entre villes dans ce nouveau graphe. Vous pouvez tester vos id\u00e9es 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."]}, {"cell_type": "code", "execution_count": 15, "metadata": {"collapsed": true}, "outputs": [], "source": ["import pyensae.datasource\n", "files = pyensae.datasource.download_data(\"facebook.tar.gz\",website=\"http://snap.stanford.edu/data/\")\n", "fe = [ f for f in files if \"edge\" in f ]\n", "fe"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Il faut d\u00e9compresser 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\u00e9crite ici [tar](http://doc.ubuntu-fr.org/tar)."]}, {"cell_type": "code", "execution_count": 16, "metadata": {"collapsed": true}, "outputs": [], "source": ["import pandas\n", "df = pandas.read_csv(\"facebook/1912.edges\", sep=\" \", names=[\"v1\",\"v2\"])\n", "print(df.shape)\n", "df.head()"]}, {"cell_type": "code", "execution_count": 17, "metadata": {"collapsed": true}, "outputs": [], "source": []}], "metadata": {"kernelspec": {"display_name": "Python 3", "language": "python", "name": "python3"}, "language_info": {"codemirror_mode": {"name": "ipython", "version": 3}, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.4"}}, "nbformat": 4, "nbformat_minor": 2}