[PDF] Algorithmique et Programmation Projet : Algorithme de Prim 1 File

View - Download Algorithmique et Programmation Projet : Algorithme de Prim 1 File

Previous PDF

Next PDF

Algorithmique et Programmation

Projet : Algorithme de Prim

Ecole normale superieure, Departement d'informatique td-algo@di.ens.fr

2013-2014

Dans un graphe connexe non-oriente avec ar^etes pondereesG= (V;E;w), unarbre couvrant mini- malest un ensemble d'ar^etes deGqui est un arbre, touche tous les sommets deG, et est de poidsP fu;vg2Aw(u;v) minimal. L'algorithme de Prim (voir [?,x24.2]) construit un arbre couvrant minimal de maniere\gloutonne". Il part d'un sommetrarbitraire et deA=;puis fait grossirAen y adjoignant une ar^ete de poids minimal qui laisse l'ensemble des ar^etes deAconnectees aret sans cycle. On note uvpour dire quefu;vg 2E. Voici l'algorithme de Prim :

1:functionACM-Prim(G)

2:choisirr2V,A ;etS frg.

3:whileS6=Vdo

4:choisirs =2Stel que minx2S;xsw(x;s) soit minimum.

5:A A[ ffx;sggetS S[ fsg

6:end while

7:returnA

8:end function

1 File de priorite

Pour une implementation ecace, l'algorithme de Prim utilise une le de priorite pour les elements deVnSavec cleClef(u)2R[f+1gegale au poids de la plus petite ar^ete deGreliantuaux sommets deS. Voici le pseudo-code :

1:functionACM-Prim(G)

2:A ;

3:choisirr2V

4:for alltrdoInsertion(P;t;w(s;t))

5:for allt6=rett6rdoInsertion(P;t;+1)

6:whileP6=;do

7:s Extraire-Min(P)

8:u choisir un sommet tel queus;u =2P, etw(s;u) =Clef(s)

9:A A[ ffs;ugg

10:for alltsdo

11:ift2Petw(s;t)

12:Diminuer-Clef(P;t;w(s;t))

13:end if

14:end for

15:end while

16:returnA

17:end function

Si la le de priorite est implantee a l'aide destas de Fibonacci(voir [?,x21]), les fonctionsExtraire-

MinetDiminuer-clefse font respectivement en temps amortiO(logjVj) etO(1). On obtient un co^ut totalO(jEj+jVjlogjVj), qui est meilleur que celui de Kruskal.

2 Travail demande

Vous ecrirez et testerez une fonction qui calcule un arbre couvrant minimal par l'algorithme de Prim

avec tas de Fibonacci. La fonction prend en entree un graphe connexe pondere de taille arbitraire donne

Conception : Charles Bouillaguet. Revise par Claire Mathieu 9/2013. 1

sous forme de listes d'adjacence. Les poids sont de type entier. La sortie sur ecran est la liste des ar^etes qui

forment l'arbre (dans un ordre quelconque) suivie du poids de l'arbre. Ainsi, votre travail se decompose

en les etapes suivantes. 1. Imp lementationd 'unef onctionp ourt esters iu ngr apheest c onnexe.La fon ctionpr ende ne ntree un graphe de taille arbitraire donne sous forme de listes d'adjacence, et donne en sortie une valeur binaire, vrai ou faux. 2. Imp lementationd 'unef onctionqu ipr ende nen treed euxe ntiersnetm2[n1;n(n1)=2] et donne en sortie un graphe connexe ansommets etmar^etes donne sous forme de listes d'adjacence. Vous pourrez utiliser lamethode de rejet: faire de maniere repetee une generation aleatoire d'un graphe ansommets etmar^etes, jusqu'a ce que le graphe obtenu soit connexe. 3.

Imp lementationn a

ve de l'algorithme de Prim. Tests sur des graphes connexes aleatoires dont les ar^etes ont des poids aleatoires uniformes entre 1 et 1000. 4. Imp lementationd 'une led epr ioritea vecu nt ableau.Imp lementationd el 'algorithmed eP rima vec une le de priorite. Tests. 5. Imp lementationd' une led ep rioritea vecu nt asd eF ibonacci.Imp lementationde l 'algorithmed e

Prim avec une le de priorite. Tests.

6. Comp araisonen trel ac omplexiteen t empsd esdi versesi mplementationsd el 'algorithmede P rim. Quelles sont, selon les implementations, les plus grandes valeurs de (n;m) pour lesquelles le pro- bleme puisse ^etre resolu en un temps raisonnable (de l'ordre de quelques secondes)?

3 Bonus

Cette partie est optionnelle.

On peut utiliser l'arbre couvrant minimum pour obtenir un tour qui donne une solution approchee au probleme du voyageur de commerce, comme suit. SoitG= (V;E;w) un graphe complet (Eest l'ensemble de toutes les paires de sommets deV),

pondere, non oriente et dont les poids sont positifs ou nuls et verient l'inegalite triangulaire :8s;t;u2

V; w(fs;ug)w(fs;tg)+w(ft;ug). On cherche a trouver un tour, c'est a dire un chemins1;:::;sn2V passant une et une seule fois par chaque sommet, et qui soit de poidsPn1 i=1w(fsi;si+1g) +w(fsn;s1g) minimal. Il est connu (voir [?,x37.2.1]) que le parcours prexe d'un arbre couvrant minimal deGest un tour de poids au plus double du poids minimal.

Vous ecrirez une fonction qui prend en argument un graphe complet de taille arbitraire, dont les poids

sont positifs ou nuls et verient l'inegalite triangulaire, et qui calcule un circuit gr^ace a cette heuristique.

La sortie sur ecran sera la liste, dans l'ordre, des sommets a visiter suivie du poids du circuit. Les poids

seront de type ottantdouble. Vous ecrirez egalement un programme de demonstration qui teste votre fonction sur des graphes aleatoires. Le programme prendra en argument en ligne de commande le nombre de sommets des graphes

a generer. Les graphes seront generes de la maniere suivante (an de s'assurer que l'inegalite triangulaire

est veriee) : pour chaque sommetsi2S, on choisit une position aleatoire uniforme (xi;yi)2[0;1]2 dans le carre unite; chaque ar^ete a alors pour poids la distance euclidienne entre ses extremites : w(fsi;sjg) =q(xixj)2+ (yiyj)2 2quotesdbs_dbs9.pdfusesText_15

[PDF] Score ASIA

[PDF] Un algorithme de simulation pour résoudre un problème de probabilité

[PDF] Algorithme PanaMaths

[PDF] Algorithmique en classe de première avec AlgoBox - Xm1 Math

[PDF] Algorithme U prend la valeur [expression de la suite - Maths en ligne

[PDF] Rappels sur les suites - Algorithme - Lycée d Adultes

[PDF] Les tableaux - Luc Brun

[PDF] Les tableaux 1 Exercice 1 - Lipn

[PDF] Terminale S Exercices sur les suites Exercice 1 On consid`ere la

[PDF] Cours d algorithmique BTS SIO première année - Bienvenue sur le

[PDF] Algorithmique et programmation, un levier pour développer des

[PDF] Algorithmique et Structures de Données

[PDF] ORME 212 : Algorithmique en seconde avec Python

[PDF] Ali baba et les quarante voleurs - Gomme Gribouillages

[PDF] Commentaire de l 'article 26 du code de droit international privé