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
NP dur?
Modérateur : Modérateurs
Encore Non déterministe polynomial?
bonjour à tous,
Est ce qu'il y a quelqu'un qui peut m'aider?
Merci
Est ce qu'il y a quelqu'un qui peut m'aider?
Merci
NP dur ou difficile?
Bonjour
Merci pour votre réponse.
(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 implique
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 génère un autre vecteur au lieu de 0 0 1 3 je peux trouvais 0 0 2 2, je vois de nouveau avec 2 3 1 0, 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
Merci pour votre réponse.
(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 implique
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 génère un autre vecteur au lieu de 0 0 1 3 je peux trouvais 0 0 2 2, je vois de nouveau avec 2 3 1 0, 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
-
Oswald_le_fort
- Messages : 1073
- Inscription : 24/05/2007 - 7:52:01
- Activité : Enseignant ou Chercheur
- Localisation : Meyrin / CERN
Désolé, de mon coté, je ne vois pas le problème.
Tu ne veux pas ce que tu appelles des "collisions": répétition d'un nombre dans une ligne (si je comprend bien?).
Alors, au lieu d'utiliser une fonction aléatoire par colonne (vecteur), pourquoi ne pas utiliser pas une fonction speudo aléatoire (qui interdirait, par exemple, à un nombre de sortir 2 fois) par ligne ?
Tu ne veux pas ce que tu appelles des "collisions": répétition d'un nombre dans une ligne (si je comprend bien?).
Alors, au lieu d'utiliser une fonction aléatoire par colonne (vecteur), pourquoi ne pas utiliser pas une fonction speudo aléatoire (qui interdirait, par exemple, à un nombre de sortir 2 fois) par ligne ?
"Ce qui compte ne peut pas toujours être compté, et ce qui peut être compté ne compte pas forcément" Albert Einstein
Bonjour Pollux,
la collision produit s'il y a deux nombres identiques dans la même colonne, par exemple: j'ai un vecteur v1=[1 3 2 1] et v2=[1 2 1 0] il y a une collision dans la première colonne, donc collision s'il y a répétition dans la même colonne.
Pour la fonction utilisé, n'importe laquelle va généré des collisions car les valeur de v1 et v2 doit être dans l'intervalle {0,1,2 et 3} obligatoirement.
Merci l'ami A vous
la collision produit s'il y a deux nombres identiques dans la même colonne, par exemple: j'ai un vecteur v1=[1 3 2 1] et v2=[1 2 1 0] il y a une collision dans la première colonne, donc collision s'il y a répétition dans la même colonne.
Pour la fonction utilisé, n'importe laquelle va généré des collisions car les valeur de v1 et v2 doit être dans l'intervalle {0,1,2 et 3} obligatoirement.
Merci l'ami A vous