Graphe de coût minimum Fermé

Question

Bonjour

Je fais des études sur les graphes et je viens solliciter votre aide pour un problème qui bloque mon avancement.

En faite j'utilise un des algorithmes de recouvrement minimal comme Kruskal. Mon problème c'est le graphe de départ que je n'ai pas.
J'ai des sommets avec des poids mais pas des arrêtes. J'ai résolu mon problème en premier temps en prenant un graphe complet comme graphe de départ et je reconstruit mes arrêtes ainsi leur poids, mais cette solution est très coûteuse en terme de temps d'exécution pour un nombre de point qui dépasse 31587.

Merci de m'aider à retrouver une solution.

Idéophage · Answer

Bonjour,

Je ne comprends pas très bien le problème. Pourrais-tu préciser ce qui est donné en entrée ?

Voilà comment j'interprète le problème pour le moment :
On a un graphe complet dont les noeuds sont pondérés. Le poids de chaque arc est donné comme la somme des poids des deux extrémités. Trouver un arbre couvrant minimal de ce graphe.

Comme ce problème est un peu trivial, je doute fort que ce soit cela...

mainou1 · Answer

Bonjour,


Merci pour votre aide,

J'ai en entrée des sommets, chaque sommet a une valeur. Je cherche à faire un recouvrement minimal de ces sommets (je peux créer un poids pour les arrêtes à partir de ces valeur). je n'ai pas un graphe en entrée c'est pour cela j'ai supposé  que j'ai un graphe complet et j'ai travaillé sous cette hypothèse,  mais cette solution est très coûteuse en terme de temps d'exécution pour un nombre de sommets en entrée  qui dépasse 31587. 

merci

Idéophage · Answer

Et selon quelle règle le poids de ces arrêtes est-il créé ?

mainou1 · Answer

J'ai plusieurs règles, Prenant par exemple la différence entre deux sommets puisque chaque sommet à une valeur.

Idéophage · Answer

J'ai bien peur que si tu ne donne pas les règles exactes, on ne puisse pas te faire chercher un algorithme meilleur que des algos standards de recherche d'arbre couvrant minimal.

[edit] Si les arcs sont pondérés simplement par la différence des poids de leurs extrémités, alors c'est encore un peu trivial.

mainou1 · Answer

Pour l'instant je travaille sur :

( Valeur pointX - Valeur point Y)/ (max de tousles points -min de tous les points)

Idéophage · Answer

Maintenant que j'ai le problème en entier, je peux essayer (/= réussir) de te faire trouver une solution optimale (oui, je ne vais bien sûr pas la donner toute cuite).

Est-ce que tu connais l'algorithme de Prim ? Si non, alors c'est très bien, ne cherche surtout pas sur Internet, tu vas pouvoir le trouver en cherchant dans ta tête, elle est pleine de trucs géniaux du genre qui ne demandent qu'à être découverts !
Pour commencer, essaie de prendre un exemple de graphe au hasard et de chercher à trouver l'arbre couvrant minimal à la main (oublie l'implémentation, tu analysera ta stratégie plus tard). Comme tu es flemmard (heureusement !), tu vas peut-être trouver une stratégie performante qui va pouvoir servir de base pour un algorithme.

Comment peut-on définir précisément un arbre couvrant minimal (fais une liste des conditions que le sous-graphe doit respecter, j'en vois deux importantes) ?

mainou1 · Answer

Merci de me guider.

Pour un arbre couvrant, il existe nécessairement une arête qui relie l'un des sommets .Pour construire un arbre couvrant de poids minimum, il suffit de choisir parmi ces arêtes sortantes d'un sommet choisie  celle de poids le plus faible.

Mon problème je n'ai pas les arrêtes. Est ce que je tri selon les valeurs des sommets? mais comme ça, j 'ai perdu l'importance de ma formule qui va relier deux sommets et  leur donner un poids et d'autre part  tout les algorithmes se base sur des graphes (des sommets ainsi que des arrêtes)

mainou1 · Answer

Considère un sommet quelconque. À quel autre sommet est-ce que l'on doit le relier pour que le cout de sa liaison au reste du graphe soit minimale (dans le cas spécifique des graphes de ton problème) ?

C'est ici mon problème est ce que je parcours tout les sommets et je détermine quel qui permet d'avoir un coût minimum? dans ce cas là comme j'ai un graphe complet et j'applique l'algorithme de Prim

Graphe de coût minimum

9 réponses

Discussions similaires