[graphe] Partitionnement d'une chaîne

[Lalawou]

Bonjour à tous,

J'ai un problème que j'ai modélisé en un graphe orienté et dont je n'arrive pas à trouver un algorithme satisfaisant. Voici un exemple de ce type de graphe:


Chaque sommet possède un poids de même que chaque arc. Le graphe est systématiquement une chaîne. Une partition ne peut pas dépasser un poids M. Le poids d'une partition étant la somme des poids des sommets et des arcs qui la compose. Une partition peut contenir un seul sommet.

Mon problème consiste à partitionner ce graphe en suivant les contraintes suivantes (par ordre de priorité):
[*] Obtenir un nombre minimal de partition (c'est le critère principal)
[*] Si plusieurs solution existent en sortie de la contrainte précédente, en sélectionner une qui minimise la taille globale des partitions. (somme des poids des partitions)

J'ai tenté de me renseigner sur les algorithmes de partitionnement de graphe, mais je n'ai pas trouvé exactement ce que je cherchais. Je ne suis d'ailleurs pas certain que les graphes soient le meilleur moyen de modéliser et résoudre ce problème.

Auriez-vous des pistes à me proposer s'il vous plait pour pouvoir me débloquer? Il me manque probablement un vision plus globale en mathématiques..

En vous remerciant par avance!

[pascal16]

s'il n'y a aucune boucle, où est la difficulté ?

[Lalawou]

La difficulté est que le graphe peut être très grand, et que générer l'ensemble des solutions à la première contrainte peut être très long.
Je voulais simplement savoir s'il existait des algorithmes plus efficace que de générer toutes les combinaisons possibles du problème.

[Ben314]

Salut,
Je ne comprend pas bien la question vu que tu emploie des termes mathématiques (par exemple celui de "partition"), mais avec un sens qui n'est pas exactement celui qu'on leur donne en math. (par exemple "le nombre minimal de partition", en math. , ça a pas trop de sens ou alors un sens extrêmement compliqué qui n'a rien à voir avec ton problème).

- Pour commencer, tu parle de partition de ton Graphe : est ce que ça signifie que tu regroupe les sommets en différents ensembles disjoints et d'intersection vide sans autre conditions.
i.e les sommets du même regroupement ne sont pas forcément successifs sur ton graphe ?
- Est ce que tu partitione aussi les Arrêtes de ton graphe, i.e. est ce que tu les regroupes toutes en différents ensembles disjoints ?
Ou bien est-ce que tu partitionne dés le départ en ensembles contenant des sommets ET des Arrêtes ?

[Lalawou]

Salut Ben,

Effectivement, je dois employer des termes qui ont un sens non-approprié en mathématiques, mais ce n'est pas volontaire, je vais donc essayer de reformuler mon problème en termes courants.

Je cherche à couper le graphe que j'ai présenté en plusieurs graphes, la coupe étant faite sur les arcs. La somme des poids des sommets et des arcs des ces sous-graphes constitue le "poids" du sous-graphe. Le poids de ces sous-graphes est limité à l'avance par un paramètre de l'algorithme, c'est à dire qu'on ne peut pas avoir un sous-graphe qui dépasse une taille donnée.

On cherche à minimiser le nombre de sous-graphe (c'est à dire le nombre de coupe).

Il peut donc y avoir plusieurs solution de découpage du graphe. Un second critère est donc de chercher dans les solutions qui ont les sous-graphes les moins lourds (critère basé sur la somme des poids des sous-graphe).

Pour répondre à ta question:
- est ce que ça signifie que tu regroupe les sommets en différents ensembles disjoints et d'intersection vide sans autre conditions.
i.e les sommets du même regroupement ne sont pas forcément successifs sur ton graphe
=> Non. On cherche bien à grouper des sommets adjacents, et il n'y a aucun intersection entre les sommets de chaque "partitions" (un sommet n'apparait que dans une "partition")

J'espère que c'est plus clair... mais n'hésitez pas à me refaire éclaircir le problème.

Merci encore pour votre aide.

[Ben314]

Je pense que c'est bon : sous la forme "en Français dans le texte", c'est on ne peut plus compréhensible (mais au niveau mathématique, c'est pas vraiment une "partition", déjà tu ne prend pas toutes les arrêtes et en plus, les sous-ensembles formant la partition doivent être composés de sommets consécutifs de ta liste)

Dans ce cas, il me semble qu'en ce qui concerne le premier point, c'est simple : tu prend le premier sommet, puis tu regarde si en ajoutant l'arc et le sommet suivant, ça dépasse ou pas M. Si oui tu les prend, si non tu coupe au niveau de cet arc. Puis tu recommence avec la même logique : si je peut prendre l'arc et le sommet suivant dans le même sous-ensemble, je prend, sinon je coupe.
Arrivé à la fin, assez clairement, en terme de "nombre de coupes", tu pourra pas faire mieux.
Par contre, il est fort possible que ça ne minimise pas la "taille globale" (c'est à dire qui ça ne maximise pas la somme des valeurs des arcs qu'on a coupé) vu qu'il risque d'y avoir pas mal d'endroit (principalement le dernier bloc) où on pourrait décaler la coupe vers la gauche : on peut éventuellement regarder quels sont les coupes "déplaçable à gauche" (i.e. qui ne font pas trop augmenter le bloc à droite de la coupe) et qui font augmenter la somme des valeurs des coupes. Sauf que je suis pas certain qu'on obtienne forcément l'optimum en procédant de la sorte.

[Lalawou]

Effectivement, c'est bien l'algorithme que j'ai utilisé jusqu'à présent (sans le déplacement des coupes). J'aurais juste aimé savoir si je pouvais en utiliser un autre qui trouve l'optimum pour les 2 critères.

Je n'avais pas pensé au déplacement des coupes: aucune idée si cela permet d'avoir un optimum ou pas..