Théorie des graphes

Invité · 09/05/2011, 19h42

Envoyé par cyberkamikaz

la resolution avec une methode greedy n' est pas si bien accepte(penalite de -50% )

Bonjour,

Je suppose qu'il s'agit d'un exercice scolaire. Il faudrait que tu donnes toutes les informations fournies par l'énoncé (de manière exhaustive). S'il y a une pénalité de 50% (sur la note je suppose) pour l'utilisation d'une méthode gloutonne, cela signifie que tu n'es pas obligé de trouver un algorithme qui te renvoie toujours la solution optimale.

Et il y a plein de méthodes gloutonnes différentes. La pénalité de 50% sur la note s'applique-t-elle à toutes les méthodes gloutonnes, ou seulement à la plus basique qui consiste à sélectionner en premier les lignes les plus longues ?

Envoyé par cyberkamikaz

On m'a dit que sa ce resoud avec les graphes (flux ou chemins ou ...)

ou quoi ? On t'a donné de précieux conseils avec l'énoncé. Si ça parle de "flux" ou de "flots", il y a des dizaines d'algorithmes de flots à consulter.

**cyberkamikaz** · 10/05/2011, 00h17

Envoyé par hellfoust

Bonjour,

Je suppose qu'il s'agit d'un exercice scolaire. Il faudrait que tu donnes toutes les informations fournies par l'énoncé (de manière exhaustive). S'il y a une pénalité de 50% (sur la note je suppose) pour l'utilisation d'une méthode gloutonne, cela signifie que tu n'es pas obligé de trouver un algorithme qui te renvoie toujours la solution optimale.

Et il y a plein de méthodes gloutonnes différentes. La pénalité de 50% sur la note s'applique-t-elle à toutes les méthodes gloutonnes, ou seulement à la plus basique qui consiste à sélectionner en premier les lignes les plus longues ?

ou quoi ? On t'a donné de précieux conseils avec l'énoncé. Si ça parle de "flux" ou de "flots", il y a des dizaines d'algorithmes de flots à consulter.

Oui c'est un exercice scolaire .
Donc l'ennonce veux dire qu'on a des routes les ronds sont des trous (chaussée avec un trou ) et le rectangle est une cahausée praticable en bonne état . On doit recouvrir tous les trou avec de plaques "les lignes".

Le but est de plaquer les trous dans la route
Il est interdit de plauquer un chemin en etat parfaite.
Les plaques peuvent se supraposer dans les trou.
Tous cele en utilisant le minimum de plaques .
Je precise la plaque veux dire une succession de trou reparé comme dans l'image si dessus. 4 plaques (lignes comme je disait avant)
Donc il faut trouver le nombre minime de plaques utilise pour reparer les routes.
D'autres indications on nous a pas donné. Meme pas quoi utiliser.
Il y'a eu quelqu'un qui a poste dans un forum si il peux utiliser une methode gloutonne et ils ont dit que la note maxime va etre 50 si on choisit un algortihme greedy .
Et j'ai entendu que peux etre sa ce resoud avec les flux .
On a que des tests privé pas de test public.
Exemple de in et de out :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
in                           out  
 
3 4                            3
OOOO  
O...
OOOO

Il ont juste dit toute resolution qui utilise greedy seras noté maximum 50 su 100.
Aucune indication juste d'autres etudiants ont mis l' accent sur greedy et flux dans leur debat donc je crois que ca ce resoud aussi avec les flux.
Et le prof a dit que la solution n'est pas si compliqué que la méthode greedy.

**Nemerle** · 10/05/2011, 09h54

Envoyé par Acrim

Un nouvel exemple qui devrait mettre la nouvelle règle en défaut :

??? Mais l'algo marche! En rouge, les 6 noeuds où l'algo s'autorise à commencer, j'ai choisi en bas à gauche (en ajoutant une règle qui cherchent à maximiser i et j lors du choix de Xij par exemple):

**Nemerle** · 10/05/2011, 10h00

Envoyé par cyberkamikaz

Les plaques peuvent se supraposer dans les trou.

Ca change la donne!! La proposition de Pseudocode est alors complêtement suffisante... Un exemple:

**Acrim** · 10/05/2011, 11h24

Effectivement, mon 2eme "contre-exemple" n'en n'était pas un.
Que penses tu de celui là (en commençant par le nœud en bas à gauche) :

Je pense par contre que le premier "contre-exemple" que j'avais envoyé pose problème à l'algo. écrit par Pseudocode (tous les nœuds sont de degré 2).

En espérant que cela t'amuse autant que moi

.

**Nemerle** · 10/05/2011, 11h33

Envoyé par Acrim

En espérant que cela t'amuse autant que moi

.

oui

N'oublie pas que j'ai ajouté la règle permettant de choisir entre horizontal et vertical: on prend le segment issu d'un sommet ayant le moins de voisin, et le plus "au bord" (max ou min sur i,j par ex), et qui induit par 2*2 vérifications le moins de segments ultérieurs.

En commençant en bas à gauche, ça donne des lignes verticales de gauche à droite (à chaque étape, un seul noeud à 1 voisin), et ça marche parfaitement...

Concernant le 1ier cas, idem: 3 belles lignes verticales!!

**pseudocode** · 10/05/2011, 11h38

Envoyé par Acrim

Que penses tu de celui là (en commençant par le nœud en bas à gauche)

Si plusieurs noeuds ont le meme degré, il faut prendre celui qui permet de rayer le plus de noeuds.

 Degré   | Horizontal | Vertical  |
         |   score    |   score	  |
         |            |		  |
    2 2  |      2 2   |      4 2  |
    3 2  |      2 2   |	     4 2  |
  2 3    |    2 2     |	   3 4	  |
2 4 2    |  3 3 3     |	 2 3 4 	  |
2 2      |  2 2       |	 2 3 	  |

Il faut donc prendre l'un des deux sommets colorés en rouge.

**Acrim** · 10/05/2011, 12h53

Nemerle, quelque chose doit m’échapper. Comment cette règle se traduit pour le nœud en bas à gauche ? Je ne comprends pas ce qui lui permet de choisir l'arc vertical plutôt que l'arc horizontal.

Un nouveau cas problématique pour Pseudocode

Des le début on peut fixer les droites obligatoires, c'est à dire les droites qui passent par des nœuds qui n'appartiennent à aucune autre droite (je crois que cela avait déjà été noté par un autre participant).

**Nemerle** · 10/05/2011, 13h25

Voila ce qui permet de choisir:

En rouge le segment testé (Horizontal ou Vertical), et en Violet le nombre de segments nécessaires à recouvrir le reste (4 cas). On voit bien que le vertical n'induit que 3 segements supplémentaire, donc on valide...

Quand à ton dernier exemple, l'algo marche encore: ici, j'ai numéroté les segments construits dans l'ordre de l'algorithem (partant tj en bas à gauche):

**davcha** · 10/05/2011, 13h28

Je vois pas où est le problème dans ton exemple.
Les droites obligatoires sont directement solution du problème.

**Acrim** · 10/05/2011, 14h09

Merci pour les petits dessins

. Je comprends mieux maintenant.

Envoyé par Nemerle

En rouge le segment testé (Horizontal ou Vertical), et en Violet le nombre de segments nécessaires à recouvrir le reste (4 cas). On voit bien que le vertical n'induit que 3 segements supplémentaire, donc on valide...

D'une certaine façon tu appliques un principe de séparation/évaluation ?
Pour le nœud considéré deux droites sont possibles. Donc tu considères les deux cas, en cherchant une évaluation (via une simplification) du nombre de droites nécessaires restantes ? A mon avis, l’évaluation risque de passer a coté pour des graphes plus compliqués. Si tu n'es pas convaincu et que ça t’intéresse, je peux essayer d'en construire un.

Envoyé par Nemerle

Quand à ton dernier exemple, l'algo marche encore: ici, j'ai numéroté les segments construits dans l'ordre de l'algorithem (partant tj en bas à gauche):

Mon dernier exemple venait juste répondre à la remarque de pseudocode :
"Si plusieurs noeuds ont le meme degré, il faut prendre celui qui permet de rayer le plus de noeuds. ". L'exemple prouve que ca ne fonctionne pas a tout les coups.

Envoyé par davcha

Je vois pas où est le problème dans ton exemple.
Les droites obligatoires sont directement solution du problème.

Oui. C'est pour cela qu'il faudrait les exploiter (ce qui ne semble pas être le cas... enfin je peux me tromper).

**pseudocode** · 10/05/2011, 14h28

Envoyé par Acrim

Un nouveau cas problématique pour Pseudocode

C'est très possible que mon heuristique ne fonctionne pas dans tous les cas. Mais dans cet exemple précis, je ne vois pas pourquoi ca pose problème ?

   Degré   | Horizontal  |  Vertical   |
           |   score     |   score     |
           |             |             |
    2 2 2  |      3 3 3  |      4 1 3  |
2 2 3   2  |  3 3 3   1	 |  3 1 4   3  |
2   3 2 2  |  1   3 3 3	 |  3   4 1 3  |
2 2 2      |  3 3 3	 |  3 1 4      |

**Acrim** · 10/05/2011, 14h44

Envoyé par pseudocode

C'est très possible que mon heuristique ne fonctionne pas dans tous les cas. Mais dans cet exemple précis, je ne vois pas pourquoi ca pose problème ?

Si je ne me trompe pas l'heuristique va choisir en premier la droite verticale passant par les 4 nœuds. Or elle n'est pas nécessaire (puisque toutes les droites horizontales passant par 3 nœuds doivent être prises en compte).

**pseudocode** · 10/05/2011, 14h52

Envoyé par Acrim

Si je ne me trompe pas l'heuristique va choisir en premier la droite verticale passant par les 4 nœuds. Or elle n'est pas nécessaire (puisque toutes les droites horizontales passant par 3 nœuds doivent être prises en compte).

Ah, exact. Je n'avais pas vu qu'il y avait une solution avec 6 droites.

En fait, il semble que mon idée de prendre les degrés soit trop approximative, car ce n'est pas un problème de cut/flow classique. Il faudrait calculer le degré "horizontal" et le degré "vertical", et encore je ne sais pas si c'est suffisant.

**Nemerle** · 10/05/2011, 15h13

Envoyé par Acrim

Si tu n'es pas convaincu et que ça t’intéresse, je peux essayer d'en construire un.

non-non, pas la peine, j'ai déjà résolu des problèmes du même style, en plus compliqué... (même un truc qui avant était supposé NP-complet

)

Je rappelle qu'on est pas là pour donner des soluces à des exos (on a aussi des boulots!): ce type d'exercice est assez élémentaire pour peu qu'on prenne un peu de temps pour y réfléchir, et surtout sans prendre la peine de sortir la grosse artillerie de la théorie des graphes (on est sur des matrices!).

Il me semble évident qu'une récursion est une solution possible. Si on la veut, il faut partir de l'algo raffiné présenté en créant un arbre de récursion: dans tous les cas au moins une des feuilles de l'arbre sera optimale.

Mais je pense qu'on peut raffiner nos remarques à moi & pseudo pour obtenir une solution plus élégante que l'arbre force brute...

**cyberkamikaz** · 10/05/2011, 17h42

Couplage maximum et minimum vertex cover sont les mots clef pour resoudre le probleme .

**pseudocode** · 10/05/2011, 18h19

Envoyé par cyberkamikaz

Couplage maximum et minimum vertex cover sont les mots clef pour resoudre le probleme .

?

A moins que le problème soit de seulement utiliser des "plaques" de longueur 2, je ne vois pas le rapport.

Invité · 10/05/2011, 18h43

Raaaa ! J'avais commencé à trouver sans l'indication :

En fait les noeuds du graphe, ce n'est pas les trous sur la route, c'est les plaques de métal.

Voici un exemple dans lequel les plaques sont numérotées de 1 à 7 :

Et maintenant, voici le graphe dont les noeuds sont les plaques. Une plaque est reliée à toutes les autres plaques qu'il faudrait utiliser pour la remplacer :

Par exemple, si on ne veut pas utiliser la plaque 5, alors il faut obligatoirement utiliser les plaques 1, 2 et 3.

**cyberkamikaz** · 10/05/2011, 18h49

C'est ce que j'ai entendu parler : flux, minimum vertex cover et couplage

L.E.: apre avoit vu le post hellfoust :
Apres on doit choisir le minimum cardinal des deux ensembles du graphe biparti ?

Invité · 10/05/2011, 19h49

Sur le graphe biparti, chaque noeud doit être "satisfait". C'est-à-dire qu'il faut :
- soit qu'il soit choisi
- soit que toutes ses dépendances soit satisfaites

Par exemple pour "satisfaire" la 3ème plaque, soit il faut décider d'utiliser la 3ème plaque, soit il faut utiliser les plaques 4, 5, 6 et 7.

Toutes les plaques doivent être satisfaites.

Autrement dit, il faut sélectionner un sous-ensemble de sommets contenant au moins une extrémité de chaque arête. C'est logique car chaque arête correspond à un trou, donc si on veut couvrir tous les trous ...

En gros, c'est un problème de vertex cover sur un graphe biparti. Le vertex cover en général est NP-complet, mais peut-être que ce n'est pas le cas si on se restreint aux graphes bipartis.

Envoyé par cyberkamikaz

Apres on doit choisir le minimum cardinal des deux ensembles du graphe biparti ?

Si tu fais ça, ça veux dire que tu choisis soit toutes les lignes horizontales, soit toutes les lignes verticales

Je ne connais pas les algos de vertex cover sur un graphe biparti. Je pense que quelqu'un en a déjà pondu un (enfin j'espère).