Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
#1 Re : Entraide (supérieur) » NP-dur » 24-11-2008 18:58:03
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
#2 Re : Entraide (supérieur) » NP-dur » 23-11-2008 20:19:35
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
#3 Re : Entraide (supérieur) » NP-dur » 23-11-2008 10:51:55
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
#4 Entraide (supérieur) » NP-dur » 22-11-2008 20:42:08
- nilz2008
- Réponses : 7
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
Pages : 1







