La ROADEF
La R.O.A.D
Evénements
Prix
Publications
Plus
Forums
Connexion
Livre blanc

Complexit

Forum 'Discussions' - Sujet créé le 2012-01-25

Bonjour,
Dans mes travaux de recherche, je suis confronté à la résolution d'un problème que j'ai traduit sous la forme d'un CSP (constraint satisfaction problem).

Mon CSP contient donc des variables et mes contraintes sont exclusivement des contraintes d'égalité et d'appartenance .

Chaque variable possède un domaine, une valeur possible dans ce domaine est de la forme {entier, ensemble d'entiers}.

Une contrainte d'appartenance entre deux variable X et Y est de la forme suivante : X appartient à Y signifie que l'entier de la valeur affectée à X appartient à l'ensemble d'entiers de la valeur affectée à Y

Une contrainte d'égalité entre X et Y : X est égale à Y signifie que l'entier de la valeur affectée à X est égale à l'entier de la valeur affectée à Y

La résolution du problème consiste à trouver une solution qui respecte toutes les contraintes et qui minimise une fonction de coût.

Ma question : Est ce qu'il s'agit d'un problème NP-complet ? la preuve ?


Merci d'avance de vos réponses, j'ai vraiment besoin de vos aides.