Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
Discussion fermé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
Pages : 1
Discussion fermée