Arbre de poids minimal-ro et théorie des graphes

Soyez le premier à donner votre avis sur cette source.

Vue 7 508 fois - Téléchargée 935 fois

Description

Pour être clair dés le départ, je présente la source pour ceux qui connaissent un peu de recherche opérationnelle et de la théorie des graphes, puis pour ceux qui n'en connaissent rien du tout:
PCQCUP: Il s'agit de trouver l'arbre de poids minimal dans un graphe dont les sommets sont des points du plan. Chaque sommet est relié avec tout autre sommet par une arrête qui a un coût égal à la distance entre ces 2 point. L'algorithme utilisé est celui de Kruskal.

PCQNCRDT: On a n points dans le plan, il faut les relier avec (n-1) segments (chaque segment relie 2 points), de sorte qu'on ait un réseau, c'est à dire que chaque point doit communiquer avec tout autre. Le probléme est de minimiser la somme des longueurs des segments (Imaginez qu'on doit connecter des postes avec du cablage, il faudrait minimiser le cout des cables donc utiliser le minimum possible)

Conclusion :


Ce qu'on peut remarquer, c'est qu'en placant ALEATOIREMENT n point, on aura un cout de l'arbre qui n'est pas du tout aléatoire.
J'attends vos commentaires.

Codes Sources

A voir également

Ajouter un commentaire Commentaires
dupuisj
Messages postés
22
Date d'inscription
mercredi 16 juin 2004
Statut
Membre
Dernière intervention
17 août 2009

14 févr. 2005 à 14:25
Oser appliquer le theoreme de Kruskal à Flash, il fallait le faire... çà marche hyper bien...
Reste plus qu'à trouver une application concrète dans flash..
cs_Mafassure
Messages postés
1058
Date d'inscription
jeudi 24 juillet 2003
Statut
Modérateur
Dernière intervention
14 février 2009

12 févr. 2005 à 12:25
capilotracté mais ça marche bien ;-)
@+
cs_hamdouss
Messages postés
23
Date d'inscription
jeudi 6 novembre 2003
Statut
Membre
Dernière intervention
12 février 2005

12 févr. 2005 à 11:57
non mafassure,
pour lancer l'algorithme, il faut aller à l'image 2 de la séquence que j'ai appelé "main", puisque la séquence "intro" contient 2 image , celle-ci devient la 4éme image de toute l'animation, c'est ce que j'ai essayé d'expliquer.
cs_Mafassure
Messages postés
1058
Date d'inscription
jeudi 24 juillet 2003
Statut
Modérateur
Dernière intervention
14 février 2009

12 févr. 2005 à 11:16
oups désolé pour la coquille...
je parlé du "coût", fallais la trouver cette relation ;-)

tu peut virer le goto(4) t'as que 3 images sur root...

stown (si tu passe par ici) faut faire gaffe à la frappe et l'orthographe :-) !! (nb : Coup / coût)
cs_hamdouss
Messages postés
23
Date d'inscription
jeudi 6 novembre 2003
Statut
Membre
Dernière intervention
12 février 2005

12 févr. 2005 à 10:32
pegase:
J'ai mis le swf.

tout le monde:
J'attends vos notes
Afficher les 9 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.