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.
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.