Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 22-11-2008 20:42:08

nilz2008
Membre
Inscription : 22-11-2008
Messages : 5

NP-dur

Bonjour à tous,

J'ai une matrice de la forme v=[0 2 1 2; 2 2 0 3; 0 0 1 1;...]=[v1;v2;v3], je  veux minimiser les collisions (les valeurs identiques) entre les vecteurs v1,v2,.... Par exemples entre v1 et v2 il y a un seul valeur qui coïncide (deuxième position, valeur 2), donc   le cas ou il y a coïncidence je génère un autre vecteur et je répète pour tous les vecteurs jusqu'à trouver la combinaison qui donne la matrice optimale.
Ma question est ce que mon problème est NP-dur (les polynômes non déterministes)?.
Merci

Hors ligne

#2 22-11-2008 23:51:14

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : NP-dur

Bonjour,

  Comment génères-tu tes vecteurs?
Si tu prends des coefficients successifs v=[0 1 2 3; 4 5 6 7;...],
c'est tout sauf NP-dur!

Fred.

Hors ligne

#3 23-11-2008 10:51:55

nilz2008
Membre
Inscription : 22-11-2008
Messages : 5

Re : NP-dur

Bonjour,
les vecteurs sont génères aléatoirement dans l'ensemble {0,1,2,3} Exemple:
v=[1 3 0 2;3 1 3 0;2 2 2 2;3 0 2 1;0 1 3 0;1 3 0 0;2 2 2 2; 0 1 3 0; 1 3 0 2; 0 1 3 0]. donc il faut optimiser les vecteurs entre eux pour avoir moins de collision en moyenne.
Merci à vous.

Cordialement

Hors ligne

#4 23-11-2008 18:15:53

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : NP-dur

Salut,

  Je n'ai plus fait de complexité depuis longtemps,
mais je dirai que oui, ce doit être NP-dur.
Tu as essayé de réduire à un pb NP-dur classique.
Si Barbichu passe par ici, il a dû faire de la complexité plus récemment que moi, non?
(j'ai qqs copains au LSV d'ailleurs).

Fred.

Hors ligne

#5 23-11-2008 20:19:35

nilz2008
Membre
Inscription : 22-11-2008
Messages : 5

Re : NP-dur

Bonjour Fred
Merci beaucoup pour le temps que vous m'avez consacré.
Sincèrement je connaît pas les problèmes de complexité! pour moi juste je veux savoir si c'est vraiment un problème NP-dur ou difficile???
Est ce que vous pouvez m'aider davantage et merci d'avance.
Cordialement

Hors ligne

#6 23-11-2008 23:46:03

Barbichu
Membre actif
Inscription : 15-12-2007
Messages : 405

Re : NP-dur

Salut,
pour nilz2008 : Je n'ai pas compris le problème considéré. Les vecteurs sont-ils la donnée du problème ? Sinon : quelle est elle ? Qu'appelles tu "optimiser les vecteurs entre eux" ? Quelle genre d'optimisation, pour quel invariant ? et quelles variables ?
pour Fred : en effet, j'en ai fait il n'y a pas très longtemps ;). Et qui connais-tu au LSV ?
++


Barbichu

Hors ligne

#7 24-11-2008 18:58:03

nilz2008
Membre
Inscription : 22-11-2008
Messages : 5

Re : NP-dur

Bonjour
Merci beaucoup
(les vecteurs sont les données du problème).
J'ai une fonction aléatoire (rand) avec laquelle je vais génère n vecteur chaque vecteur est de longueur k-1 (de 0 à k-1) Exemple k=4.
v=[0 0 1 3;2 3 1 0;3 2 1 1]. Si en prend les vecteurs  0 0 1 3 et 2 3 1 0 il y a une collision (troisième position) alors avec la même fonction rand je vais génère un autre vecteur au lieu de 0 0 1 3  je peux trouvais 0 0 2 2 et je voir de nouveau avec 2 3 1 0 et puis avec  3 2 1 1 et puis je passe vers le deuxième vecteur et je le compare avec les deux autres jusqu'à trouve soit la solution optimal global c'est à dire qu'il n'est y pas de collision ou bien la solution optimal  (c'est à dire qui posséde le moins de collision).

Merci beaucoup
Cordialement
A vous les amis

Hors ligne

#8 27-11-2008 11:32:22

Barbichu
Membre actif
Inscription : 15-12-2007
Messages : 405

Re : NP-dur

Hello,
1/ Soit les vecteurs sont la donnée, soit ils sont aléatoires mais pas les deux.
2/ S'ils sont aléatoire, tu ne peux pas imposer la façon dont l'algorithme va les utiliser.

Je rappelle qu'un problème est un couple (données, question).
Quel est le couple (donnée, question) qui défini ton problème ?
++

Dernière modification par Barbichu (27-11-2008 11:32:38)


Barbichu

Hors ligne

Pied de page des forums