Génération uniforme de solutions d'un problème NP-difficile

La question :

Bonjour,

Je veux générer une solution d'un problème NP-difficile avec une
probabilité uniforme.
Le problème NP-difficile se présente sous la forme d'un vecteur
booléen de longueur n vérifiant des contraintes de cardinalité de la
forme (x_1 + x_3 + x_6 <= 2, respectivement ==, >=)

Comme je ne vois pas trop de solution non triviale, je considère un
cas très simplifié (tirer uniformément un vecteur de 5 booléens
dont 3 valent 1) que j'essaie ensuite de généraliser. Un des
problèmes est que j'ai du mal a évaluer si l'algorithme fournit in
fine une distribution uniforme sur l'ensemble des solutions du
problème.

Noter que pour les problèmes vraiment difficiles, je me contenterai
d'une distribution "à peu près" uniforme.

Methode 1 (triviale) :
Génerer tous les vecteurs booléens contenant 3 bits à 1
Leur associer un nombre dans un intervalle [0..M]
Tirer uniformément un nombre sur cet intervalle
-> La probabilité est bien uniforme mais cette approche est
irréalisable en pratique

Methode 2 (arbre de recherche sans propagation de contraintes) :
Pour chaque bit x_k
- tirer uniformément une valeur dans {0, 1}, par exemple x_3 = 1
- fixer la valeur (x_3 = 1) et vérifier que les contraintes ne sont
pas violées
- si les contraintes sont violées, revenir au dernier choix et prendre
l'option inverse (x_3 = 0)
-> C'est équivalent à developper un arbre de recherche avec un
branchement probabiliste sur les variables booléenes. Mais j'ignore si
la probabilité uniforme sur les variables individuelles (x_k = 0 ||
x_k = 1) induit une probabilité uniforme sur l'ensemble des solutions.

Methode 3 (arbre de recherche avec propagation de contraintes) :
Idem que la précédente mais dès que l'on remarque que certaines
valeurs sont nécessaires, on les fixe.
Par exemple pour le vecteur de longeur 5 avec 3 bits à 1, si on a
généré 00... on sait immédiatement qu'il faut completer avec des 1
: 00111.

Methode 4 (décomposition en sous-contraintes)

J'explique d'abord sur l'exemple. L'idée est de tirer uniformément la
position des '1' dans le vecteur :
- on tire uniformément un nombre entre 1 et 3 (car le premier 1 est
nécessairement parmi ces valeurs)
on obtient par exemple 2, alors on construit 01...
- on tire uniformément un nombre entre 3 et 4 (car conditionnellement
au fait que le premier 1 est en 2, le second 1 est nécessairement
entre 3 et 4)
on obtient par exemple 4, on construit alors le vecteur 0101.
- on tire uniformément un nombre entre 5 et 5, on obtient 01011

D'un point de vue plus global, on triture l'ensemble des contraintes
afin d'en déduire des variables "libres" puis on tire uniformément
leur position. C'est probablement la façon la plus efficace d'un point
de vue calculatoire, mais je n'ai pas la moindre idée de comment les
transformations biaisent la distribution de probabilités sur les
solutions.

Commentaires ? Suggestions ? Liens ?

Diego Olivier

Poser votre question sur le forum Programmation

La réponse :

a écrit :


Commentaires ? Suggestions ? Liens ?


Tu parles de quel problème exactement ?

--
Tom

Poser votre question sur le forum Programmation

Questions similaires :

Idees pour resoudre un probleme

Bonjour, Je recherche une ligne directrice pour trouver un algo efficace pour resoudre le probleme suivant: "Etant donne une liste de rectangles (decrit par leur longueur et leur largeur), trouver un rectangle dont l'aire est la plus petite possible et recouvrant tous les rectangles donnes en...

Petit problème de géographie.

Bonjour. "dvanhee" a écrit dans le message de news J'avais ébauché un truc de ce genre il y a longtemps, à base de géométrie constructive... De mémoire: on parcours les points du contour (polygone) en considérant pour chaque nouveau point: - le triangle qu'il forme avec les...

Autre problème graphisme

Bonjour à tous Me revoilà avec un nouveau petit problème : J'ai une image couleur codée sur 24 bits (8 bits pour le Rouge, 8 bits pour le Vert et 8 bits pour le Bleu) Je dois arriver à réduire le nombre de couleurs dans l'image finale car chaque pixel est codé sur un nombre de bits variable de 1 bit...

problème de 3 couleurs

Bonjour messieurs, Voici un algorithme pour 3 couleurs : Soit G un graphe planaire qui a 3-clique comme clique maximum, on note chaque 3-clique par triangle. G contient plusieurs triangles, placer les un à coter des autres, ou séparer par des arrêts. 1) Zone de colorisation obligatoire simple : Si...

probleme d'emploi du temps.

Bonjour, Je m'intéresse à l'aspect théorique des algorithmes permettant d'obtenir un emploi du temps en fonction de contraintes. J'ai bien trouvé quelques références éparses sur google, le problème semble NP-complet, peut se résoudre par le coloriage d'un graphe (cela n'est pas clair pour...