Graphe de coût minimum
Fermé
mainou1
Messages postés
6
Date d'inscription
lundi 18 novembre 2013
Statut
Membre
Dernière intervention
21 novembre 2013
-
Modifié par irongege le 18/11/2013 à 14:24
Idéophage Messages postés 43 Date d'inscription mardi 21 août 2012 Statut Membre Dernière intervention 23 novembre 2013 - 21 nov. 2013 à 18:28
Idéophage Messages postés 43 Date d'inscription mardi 21 août 2012 Statut Membre Dernière intervention 23 novembre 2013 - 21 nov. 2013 à 18:28
A voir également:
- Graphe de coût minimum
- Son trop fort au minimum casque bluetooth - Forum Casque et écouteurs
- Age minimum salle de sport ✓ - Forum Loisirs / Divertissements
- Vampire diaries âge minimum ✓ - Forum Cinéma / Télé
- Fitness park age minimum ✓ - Forum Loisirs / Divertissements
- La taille de l'étendue est inférieure au minimum - Forum logiciel systeme
9 réponses
Idéophage
Messages postés
43
Date d'inscription
mardi 21 août 2012
Statut
Membre
Dernière intervention
23 novembre 2013
5
20 nov. 2013 à 18:45
20 nov. 2013 à 18:45
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...
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
Messages postés
6
Date d'inscription
lundi 18 novembre 2013
Statut
Membre
Dernière intervention
21 novembre 2013
20 nov. 2013 à 19:15
20 nov. 2013 à 19:15
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
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
Messages postés
43
Date d'inscription
mardi 21 août 2012
Statut
Membre
Dernière intervention
23 novembre 2013
5
20 nov. 2013 à 19:50
20 nov. 2013 à 19:50
Et selon quelle règle le poids de ces arrêtes est-il créé ?
mainou1
Messages postés
6
Date d'inscription
lundi 18 novembre 2013
Statut
Membre
Dernière intervention
21 novembre 2013
20 nov. 2013 à 20:01
20 nov. 2013 à 20:01
J'ai plusieurs règles, Prenant par exemple la différence entre deux sommets puisque chaque sommet à une valeur.
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Idéophage
Messages postés
43
Date d'inscription
mardi 21 août 2012
Statut
Membre
Dernière intervention
23 novembre 2013
5
Modifié par Idéophage le 20/11/2013 à 20:08
Modifié par Idéophage le 20/11/2013 à 20:08
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.
[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
Messages postés
6
Date d'inscription
lundi 18 novembre 2013
Statut
Membre
Dernière intervention
21 novembre 2013
20 nov. 2013 à 20:10
20 nov. 2013 à 20:10
Pour l'instant je travaille sur :
( Valeur pointX - Valeur point Y)/ (max de tousles points -min de tous les points)
( Valeur pointX - Valeur point Y)/ (max de tousles points -min de tous les points)
Idéophage
Messages postés
43
Date d'inscription
mardi 21 août 2012
Statut
Membre
Dernière intervention
23 novembre 2013
5
Modifié par Idéophage le 20/11/2013 à 20:27
Modifié par Idéophage le 20/11/2013 à 20:27
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) ?
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
Messages postés
6
Date d'inscription
lundi 18 novembre 2013
Statut
Membre
Dernière intervention
21 novembre 2013
20 nov. 2013 à 20:44
20 nov. 2013 à 20:44
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)
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)
Idéophage
Messages postés
43
Date d'inscription
mardi 21 août 2012
Statut
Membre
Dernière intervention
23 novembre 2013
5
20 nov. 2013 à 21:18
20 nov. 2013 à 21:18
Quand tu dis que tu n'as pas les arrêtes, c'est qu'elles sont implicites, tu peux les calculer au besoin, donc ce n'est pas un problème. Ce problème est même plus simple que le cas général d'un arbre couvrant minimum sur un graphe quelconque (et pourrait servir d'introduction, je crois).
Je pense que tu as au moins le début de l'idée. Considérer que les données sont triées ne peut que simplifier le problème, le tri est une bonne idée. Je suis désolé, mais je n'ai pas compris grand chose à ta dernière phrase : comment ça la formule perd son importance ? Tous les algorithmes se basent sur des graphes ? Je ne connais pas Matlab, il n'est possible que d'exécuter des algorithmes standards du genre Kruskal ou Prim ? On ne peut pas programmer ce que l'on veut avec Matlab ?
> il suffit de choisir parmi ces arêtes sortantes d'un sommet choisie celle de poids le plus faible.
C'est en gros l'idée simplifiée de l'algorithme de Prim. 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) ?
Je pense que tu as au moins le début de l'idée. Considérer que les données sont triées ne peut que simplifier le problème, le tri est une bonne idée. Je suis désolé, mais je n'ai pas compris grand chose à ta dernière phrase : comment ça la formule perd son importance ? Tous les algorithmes se basent sur des graphes ? Je ne connais pas Matlab, il n'est possible que d'exécuter des algorithmes standards du genre Kruskal ou Prim ? On ne peut pas programmer ce que l'on veut avec Matlab ?
> il suffit de choisir parmi ces arêtes sortantes d'un sommet choisie celle de poids le plus faible.
C'est en gros l'idée simplifiée de l'algorithme de Prim. 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) ?
mainou1
Messages postés
6
Date d'inscription
lundi 18 novembre 2013
Statut
Membre
Dernière intervention
21 novembre 2013
21 nov. 2013 à 13:27
21 nov. 2013 à 13:27
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
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
Idéophage
Messages postés
43
Date d'inscription
mardi 21 août 2012
Statut
Membre
Dernière intervention
23 novembre 2013
5
Modifié par Idéophage le 21/11/2013 à 18:28
Modifié par Idéophage le 21/11/2013 à 18:28
Oui, c'est beaucoup trop couteux. Fais un exemple à la main (5 ou 6 noeuds). Est-ce que tu as besoin de regarder tous les sommets pour savoir auquel relier ton noeud (oublie complètement l'implémentation, fais le de façon à aller le plus vite possible, sans te préoccuper de savoir comment un ordinateur pourrait faire).
