Arbre de poids minimal-ro et théorie des graphes
Soyez le premier à donner votre avis sur cette source.
Vue 7 669 fois - Téléchargée 939 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)
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.
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
- Arbre de poids minimal-ro et théorie des graphes
- Arbre de java ✓ - Forum Java
- Arbre de tournoi - Forum PHP
- Dessin arbre généalogique - Forum PHP
- Comment dessiner un arbre généalogique - Forum PHP
- Hauteur d'un arbre ✓ - Forum C / C++ / C++.NET
14 févr. 2005 à 14:25
Reste plus qu'à trouver une application concrète dans flash..
12 févr. 2005 à 12:25
@+
12 févr. 2005 à 11:57
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.
12 févr. 2005 à 11:16
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)
12 févr. 2005 à 10:32
J'ai mis le swf.
tout le monde:
J'attends vos notes
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.