minimisation du nombre de sous-ensembles utilisés pour recouvrement

Bonjour à tous,
J'ai un problème d'optimisation qui peut être formulé de la manière suivante:
J'ai une forêt avec A arbres et plusieurs pots de peinture (avec au total C couleurs différentes). Mon objectif est de marquer chaque arbre avec le minimum de couleurs différentes sachant que chaque arbre de ma forêt doit être marqué au moins une fois (et peut être marqué de plusieurs couleurs différentes) et que chaque arbre peut être marqué uniquement par un sous-ensemble des couleurs.
La modélisation mathématique ressemble à ça (notations LateX like):

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

Données: A : le nombre d'arbres de la forêt C : le nombre de couleurs différentes M_{a,c} = 1 si l'arbre a peut être marqué par la couleur c Variables: x_c = 1 si la couleur c a été utilisée pour marquer les arbres Contraintes: Chaque arbre doit être marqué au moins une fois: \forall a=1..A, \sum_{c=1}^C (x_c \times M_{a,c}) \geq 1 Objectif: minimiser le nombre de couleurs utilisées: \min \sum_{c=1}^C x_c

---

Je n'arrive pas à établir la complexité de ce problème (j'ai essayé de le ramener à un problème de flot mais je n'y suis pas arrivé). Si vous avec des idées... je suis preneur! :ccool:

C'est un problème de dénombrement, il te suffit de calculer combien tu peux marquer d'arbres à l'aide de n couleurs.

Malgré tes efforts je trouve que le problème n'est pas assez bien formulé.

Mes hypothèses:

• il faut pouvoir identifier chaque arbre (unicité du marquage)
• on ne doit pas faire plusieurs marques d'une même couleur sur un même arbre
• les marques ne sont pas ordonnées

Dans ce cas chaque marquage est une combinaison de couleurs, si on dispose de n couleurs on peut marquer C(n,k) arbres à l'aide de k marques.
En faisant varier k de 0 à n on obtient le nombre d'arbres marquables de façon unique à l'aide de n couleurs :
http://upload.wikimedia.org/math/0/8...75b70e7abe.png

Evidemment, si mes hypothèses ne sont pas les tiennes...

Une petite tentative, pas forcément tout à fait exacte.

On peut formuler le problème en termes d'ensembles : on a A éléments, C ensembles, et on recherche le plus petit nombre d'ensembles dont l'union contient les A éléments.

Ceci nous donne de manière directe le dénombrement calculé par SpiceGuid, chacun des C ensembles pouvant être ou ne pas être dans l'union, il y a 2^C unions possibles.

On dispose d'une matrice M(a,c) qui vaut 1 si a peut être marqué par c, 0 sinon. Si on représente une union par un vecteur V de C 0 et 1 (1 si on utilise la couleur, 0 sinon), le produit M(a,c)V est un vecteur de A éléments donnant le nombre de marques sur chaque arbre, si une de ses coordonnées est nulle, l'union ne contient pas cet élément, sinon le recouvrement représenté par V est une solution candidate. Ce produit se calcule en AC produits (de zéro et de un).

Si on énumère tous les cas, on va donc avoir (au pire) quelque chose en
O(AC 2^C). S'il y a peu de couleurs et beaucoup d'arbres, le problème est plus ou moins linéaire (en A).


Maintenant, le problème doit pouvoir aussi s'exprimer comme un programme linéaire. Les solutions possibles sont les vecteurs V {0,1}^C (donc les sommets d'un hypercube de dimension C. On cherche à minimiser le nombre de 1, soit le produit scalaire V.I (où I(1,1....1)) sous la contrainte que toutes les coordonnées du produit MV soient non nulles (je suis certain qu'il doit y avoir une facon rusée de formuler cela comme une contrainte simple).

Dans cette formulation, on pourrait tenter une approche linéaire, soit sur le problème direct (minimiser VI) soit sur son dual.

Voila, c'est un peu fouillis, mais je chercherais par là.

Francois