BROADCASTS.com

Published: May 22, 2016, 1:45 p.m.

b'

Retour \\xe0 l\\u2019\\xe9cole et aux \\xe9pisodes \\u201cconcept\\u201d pour parler des graphes !

\\n\\n

En premi\\xe8re ann\\xe9e de pr\\xe9pa en cours d\\u2019algo, j\\u2019ai vu trois structures\\nde donn\\xe9es principales que sont les listes, les arbres et les graphes.

\\n\\n

Encore une fois, mon but n\\u2019est pas que les profs d\\u2019algos s\\u2019\\xe9tranglent\\nscandalis\\xe9s devant ce que je raconte, mais de d\\xe9dramatiser pour les\\nd\\xe9butants et leur mettre le pied \\xe0 l\\u2019\\xe9trier.

\\n\\n

Listes, Arbres, Graphes

\\n\\n

\\xc9videmment il y a \\xe9norm\\xe9ment \\xe0 dire sur chacun, la cl\\xe9 est que chaque\\nfois que vous arrivez \\xe0 repr\\xe9senter le probl\\xe8me que vous avez, sous\\ndes formes connues, vous avez tout un ensemble de connaissances \\xe0\\nvotre disposition.

\\n\\n

Et \\xe0 chaque sp\\xe9cificit\\xe9 de votre probl\\xe8me, vous avez soit la chance\\nd\\u2019avoir des contraintes qui simplifient les algos connus ou vous\\npermettent d\\u2019\\xe9viter des prises de t\\xeate, soit la malchance de ne pas\\nrentrer dans les cases de ce qui est couramment \\xe9tudi\\xe9 et pr\\xe9sent\\xe9,\\net de devoir trouver les astuces vous-m\\xeames.

\\n\\n

On a parl\\xe9 des listes cha\\xeen\\xe9es, et des \\xe9num\\xe9rations en Ruby, et bien\\nqu\\u2019il y ait de nombreuses variantes et astuces \\xe0 ajouter, je pense\\nen rester l\\xe0.

\\n\\n

Je n\\u2019ai pas encore parl\\xe9 des arbres, principalement parce que je\\nn\\u2019ai eu ni d\\u2019inspiration, ni vu de probl\\xe8me majeur et explicable\\nsimplement : soit des \\xe9tudiants se battre sur des points d\\u2019algo\\nassez techniques, soit des gens qui n\\u2019avaient pas vu que leur\\nprobl\\xe8me \\xe9tait en r\\xe9alit\\xe9 \\xe0 repr\\xe9senter sous forme d\\u2019arbre, mais\\nle concept en lui-m\\xeame me semble assez bien compris.

\\n\\n

Graphes

\\n\\n

La mani\\xe8re dont je visualise un graphe, c\\u2019est un GPS ou une carte\\ndes transports, disons le m\\xe9tro parisien.

\\n\\n

Quand vous dessinez un graphe, vous avez des bo\\xeetes ou des points\\nreli\\xe9s par des lignes ou des fl\\xe8ches. Les relations sont des arcs\\n(\\u201car\\xeates\\u201d), les \\xe9l\\xe9ments reli\\xe9s entre eux, des noeuds (\\u201csommets\\u201d).

\\n\\n

La carte du m\\xe9tro vous repr\\xe9sente les lignes et stations, d\\u2019ailleurs\\nde mani\\xe8re simplifi\\xe9e par rapport \\xe0 la r\\xe9alit\\xe9 : vous n\\u2019avez pas les\\nsorties, les couloirs, le temps de trajet repr\\xe9sent\\xe9 fid\\xe8lement.

\\n\\n

Les deux choses les plus simples \\xe0 faire avec un tel graphe sont :

\\n\\n

\\n
• lister les stations (parcours du graphe sans rien oublier)
\\n
• trouver un plus court chemin entre deux stations
\\n

\\n\\n

Les fa\\xe7ons les plus simples de faire sont de choisir un point de\\nd\\xe9part, et de tout lister ensuite \\xe0 partir de l\\xe0. Pour trouver une\\nstrat\\xe9gie adapt\\xe9e, on doit se poser plusieurs questions.

\\n\\n

Graphe orient\\xe9
\\nEst-ce que je peux toujours faire marche arri\\xe8re ?

\\n\\n

Dans la plupart des stations du m\\xe9tro parisien, oui.\\nS\\u2019il y a un tunnel entre deux stations, il les relie dans un sens et\\ndans l\\u2019autre. Mais sur quelques endroits, on a des sens uniques :\\nligne 7bis ou Michel Ange (Auteuil/Molitor) lignes 9 et 10.

\\n\\n

Le graphe du m\\xe9tro parisien est orient\\xe9 (ou dirig\\xe9) : si vous trouvez\\nun chemin pour aller d\\u2019une station \\xe0 une autre, le chemin retour ne\\nsera pas forc\\xe9ment exactement le m\\xeame.

\\n\\n

Graphe connexe
\\nEst-ce que toutes les stations sont reli\\xe9es entre elles ?

\\n\\n

A priori, oui. On peut d\\xe9battre sur le funiculaire de Montmartre,\\nmais c\\u2019est \\xe0 peu pr\\xe8s tout.

\\n\\n

Par contre, imaginez un instant que telle ou telle ligne ou station\\nsoit ferm\\xe9e : travaux, gr\\xe8ves, incidents, ou m\\xeame correspondance\\nferm\\xe9e vous obligent \\xe0 changer de trajet.

\\n\\n

Le m\\xe9tro parisien est si dense qu\\u2019on imagine mal une situation o\\xf9 il\\nrepr\\xe9senterait deux graphes coup\\xe9s qui ne peuvent pas communiquer\\nentre eux. \\xc0 la rigueur, couper le pont de Charenton : le terminus de\\nCr\\xe9teil est assez loin mais la ligne 8 n\\u2019a pas de correspondance apr\\xe8s\\nPorte de Charenton. Bien entendu, dans ces cas-l\\xe0, il n\\u2019y aurait\\nprobablement pas de m\\xe9tro entre les poign\\xe9es de stations qui restent\\nseules.

\\n\\n

Mais si on repr\\xe9sente le graphe de toutes les voies ferr\\xe9es fran\\xe7aises\\net britanniques, quand le Tunnel sous la Manche est ferm\\xe9, on a bien\\ndeux graphes assez grands qui ne sont pas reli\\xe9s entre eux.

\\n\\n

Graphe pond\\xe9r\\xe9
\\nEst-ce que tout chemin d\\u2019une station \\xe0 ses voisines prend le m\\xeame temps ?

\\n\\n

\\xc0 Paris, bien s\\xfbr que non. Certaines stations sont proches et d\\u2019autres\\n\\xe9loign\\xe9es. Si on veut vous proposer un chemin optimal, c\\u2019est une\\ninformation int\\xe9ressante \\xe0 prendre en compte : non seulement il y a\\ndes trajets plus courts, mais il y a aussi des correspondances plus\\nsimples, mais il y a aussi dans la vraie vie le fait de marcher plus\\nou moins longtemps en surface et choisir les bonnes stations de d\\xe9part\\net d\\u2019arriv\\xe9e.

\\n\\n

En voiture, votre GPS va m\\xeame probablement avoir des poids diff\\xe9rents,\\nvoire toute une liste de contraintes : les kilom\\xe8tres \\xe0 parcourir,\\nmais aussi les vitesses maximum autoris\\xe9es voire le trafic en temps\\nr\\xe9el, pour calculer le temps ; l\\u2019argent, les voies limit\\xe9es en hauteur\\nou largeur\\u2026

\\n\\n

Plus court chemin

\\n\\n

\\xc0 partir de l\\xe0, vous pouvez envisager plusieurs algos de cartographie\\npar analogies simples : vous partez d\\u2019une station, et on va simuler\\npresque tous les chemins possibles entre d\\xe9part et arriv\\xe9e.\\nSi vous le faites vous-m\\xeames, vous allez repasser par plein de stations.

\\n\\n

Plus rapide, vous le faites avec une \\xe9quipe, ou disons une infinit\\xe9 de\\nclones de vous-m\\xeames, qui doivent pouvoir se parler pour comparer les\\nchemins emprunt\\xe9s.

\\n\\n

Et l\\xe0, la m\\xe9taphore a atteint ses limites : quand on r\\xe9dige un algorithme,\\non doit se rappeler que l\\u2019ordinateur est tr\\xe8s b\\xeate, il ne se rappellera de\\nrien de particulier sauf si vous lui dites de faire attention.\\nUn algo un peu na\\xeff pourrait l\\u2019oublier et ferait des recherches \\xe0\\nl\\u2019infini, en passant sans cesse par les m\\xeames stations.

\\n\\n

\\xc7a nous m\\xe8ne \\xe0 une propri\\xe9t\\xe9 et une contrainte de plus :

\\n\\n

Graphe cyclique
\\nEst-ce que partant d\\u2019une station, je peux y revenir ?

\\n\\n

\\xc0 Paris, oui, vu le nombre de lignes et le fait que presque tous les\\nchemins sont faisables en sens inverse.

\\n\\n

Comme dans la vraie vie, on sait bien qu\\u2019on est en train d\\u2019\\xe9valuer un\\nchemin qu\\u2019on a d\\xe9j\\xe0 vu, dans la plupart des algorithmes on va\\nconserver quelque part une liste des sommets qu\\u2019on a d\\xe9j\\xe0 visit\\xe9s.

\\n\\n

Cycle absorbant
\\nEst-ce que je peux faire tourner le temps \\xe0 l\\u2019envers ?

\\n\\n

OK ce n\\u2019est pas la meilleure formulation, mais imaginons des\\npoids n\\xe9gatifs dans un graphe pond\\xe9r\\xe9.\\nDans l\\u2019image du m\\xe9tro, on ne peut pas revenir dans le temps,\\naucune ar\\xeate n\\u2019a de poids n\\xe9gatif. A fortiori, il n\\u2019existe\\npas de boucle de transports qui vous ferait revenir dans le temps.

\\n\\n

Mais imaginons que vous avez construit un graphe pour repr\\xe9senter une\\nsuite de choix et d\\u2019\\xe9tapes, certaines o\\xf9 vous payez de l\\u2019argent et\\nd\\u2019autres o\\xf9 on vous en rend.

\\n\\n

Si vous trouviez une combine pour gagner de l\\u2019argent ind\\xe9finiment,\\npourquoi pas : elle n\\u2019est probablement soit pas l\\xe9gale, soit pas\\n\\xe9thique, soit avec des conditions de d\\xe9part particuli\\xe8rement\\nrestrictives, mais pourquoi pas.

\\n\\n

En tout cas, parcourir un tel graphe pour trouver le co\\xfbt le moins\\ncher est une question qui n\\u2019aura pas de sens, puisque le moins\\ncher serait \\u201cmoins l\\u2019infini\\u201d. La plupart des algos de plus court\\nchemin ne savent pas g\\xe9rer ce cas-l\\xe0, le mieux qu\\u2019ils puissent\\nfaire c\\u2019est d\\xe9tecter quand \\xe7a arrive.

\\n\\n

Liste d\\u2019adjacence

\\n\\n

On a raisonn\\xe9 tout l\\u2019\\xe9pisode sur la carte du m\\xe9tro.\\nComment on pourrait stocker de telles informations dans un ordinateur ?

\\n\\n

Deux des m\\xe9thodes les plus utilis\\xe9es sont la liste d\\u2019ajacence et la matrice d\\u2019adjacence.

\\n\\n

La liste d\\u2019adjacence, c\\u2019est quand chaque station conna\\xeet ses \\u201cvoisines\\u201d, celles\\nqu\\u2019on peut atteindre \\xe0 partir de l\\xe0.\\nC\\u2019est ce que vous avez affich\\xe9 ou annonc\\xe9 dans de nombreux syst\\xe8mes de transport :\\nla station suivante et les correspondances.

\\n\\n

On n\\u2019en parle pas dans les transports mais bien \\xe9videmment, dans votre code,\\nil faudrait mentionner la station pr\\xe9c\\xe9dente si on peut y aller (hors cas du\\nsens unique donc).

\\n\\n

Matrice d\\u2019adjacence

\\n\\n

Et la matrice d\\u2019adjacence, c\\u2019est faire un tableau avec tous les\\nsommets en ligne d\\u2019en-t\\xeate, tous les sommets en colonne d\\u2019en-t\\xeate, et\\n\\xe0 chaque case correspondante, ces sommets sont-ils reli\\xe9s par un arc ?\\nOui, non, et le cas \\xe9ch\\xe9ant avec quel poids ?

\\n\\n

\\xc7a ressemble un peu \\xe0 ce que vous avez dans les cartes routi\\xe8res ou\\nsur des tickets de p\\xe9age : \\xe0 titre indicatif, de telle ville \\xe0 telle\\nville, tant de kilom\\xe8tres ou tant d\\u2019euros.

\\n\\n

Et comme on peut faire l\\u2019aller et le retour, c\\u2019est souvent repr\\xe9sent\\xe9\\nsous forme de triangle : je ne peux pas lire \\u201cde Toulouse \\xe0 Bordeaux\\u201d,\\nmais je peux trouver \\u201cde Bordeaux \\xe0 Toulouse\\u201d. Si le graphe \\xe9tait\\norient\\xe9, on aurait besoin du tableau complet.

\\n\\n

Essayez de l\\u2019\\xe9crire sur papier !

\\n\\n

\\xc0 \\xe9crire comme \\xe0 lire, on voit rapidement que la liste d\\u2019adjacence est\\nplus pratique quand il y a peu d\\u2019ar\\xeates, de connexions, et que la matrice\\nd\\u2019adjacence est plus adapt\\xe9e quand il y a beaucoup de connexions entre les\\nsommets.

\\n\\n

Ce n\\u2019est pas toujours le cas qu\\u2019une intuition s\\u2019av\\xe8re vraie, alors autant le noter :)

\\n\\n

Le cours n\\u2019est pas termin\\xe9

\\n\\n

L\\u2019\\xe9pisode va s\\u2019arr\\xeater l\\xe0, mais bien s\\xfbr le cours sur les graphes va\\nplus loin : d\\xe9finitions pr\\xe9cises, algos diff\\xe9rents et calculs de complexit\\xe9,\\net puis plusieurs outils de transformation, par exemple repr\\xe9senter un graphe\\nsous forme d\\u2019arbre etc.

\\n\\n

\\xc7a permet quand on coince sur une repr\\xe9sentation qui ne nous aide pas\\nbeaucoup, de retomber sur des situations qu\\u2019on ma\\xeetrise mieux, ce qui\\nest une excellente m\\xe9thode \\xe0 suivre quand vous bloquez sur un cas\\npr\\xe9cis.

'