Discussion :

[yal001]

Bonjour, excusez moi pour le titre un peu ambigü

j'ai une matrice nxm (n pas forcément égal à m) dans lesquels se trouvent des coefficients qui valent soit 0, soit une valeur positive.
Mes études de maths datant d'il y a quelques années déjà, et n'étais pas très poussées, j'aimerais savoir s'il était possible d'avoir la chose suivante, de manière simple
Ce tableau représente mon problème, et une solution est une combinaison d'éléments non nuls, sachant que pour chaque élément sélectionné, je n'ai pas le droit d'en prendre un qui appartient à la même ligne, ni à la même colonne. Comme il y a de bonnes chances que ce ne soit pas clair, voilà un exemple

( 0 0 4 6 8 )
( 1 0 5 0 0 )
( 2 3 0 7 9 )

Une solution serait par exemple 4-1-3, ou 6-5-9 mais pas 4-5-7 car le 4 et le 5 sont sur la même colonne.
En fait ce ne sont pas toutes les solutions qui m'intéressent, mais toutes les solutions qui ont le plus grand nombre d'éléments (en fait c'est la solution parmi celles-ci dont la somme des solutions est la plus grande, mais la liste ferait déjà mon bonheur).
J'ai essayé par un traitement informatique, mais vu la taille énorme de mon tableau et la liste des solutions... Disons que j'ai eu des problèmes

Je ne sais pas si quelqu'un peut m'aider, mais merci d'avance à ceux qui essairont!

N'hésitez pas à demander des précisions si tout cela n'est pas clair

[Nehmé]

Salut,
voici la première idée qui m'est venu en lisant ton problème. les 1ère idées sont souvent pas très bonnes mais mènent tjrs vers les bonnes:

tu parcours ton tableau ligne par ligne ou colonne par colonne comme tu préfères.
Disons ligne par ligne:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
tu cherches le maximum de la première ligne, tu sauvegarde sa position et sa valeur
 
tant que le tableau n'est pas parcouru
{
  tu cherches le maximum de la ligne actuel
  si (ce maximum se trouve dans la même colonne de 1 des maximums précedents ?)
	{
		- deplacerMaximum(ligne1, ligne2);
		- re vérifier si le maximum déplacé se trouve dans la même colonne d'un autre maximum,
		- si c'est la cas il faut re appeler déplacerMaximum et re verifier jusqu'à ce qu'il y ait aucun conflit 
	}
 
  - tu sauvgardes sa position et sa valeur et tu continues
}
 
//ligne1 et ligne2 sont les lignes en conflits
deplacerMaximum(ligne1, ligne2)
{
	max1a = maximum de ligne1
  max1b = 2ème maximum de ligne1
	max2a = maximum de ligne2
	max2b = 2ème maximum de ligne2
 
	si( (max1a + max2b) > (max1b + max2a) )
	{
		tu prend max1a pour ligne1 et max2b pour ligne2
	}
 
	si ( (max1a + max2b) < (max1b + max2a) )
	{
		tu prend max2a pour ligne1 et max2b pour ligne2
	}
 
	si ( (max1a + max2b) == (max1b + max2a) )
	{
		ce cas est ton problème. puisque le choix de une des deux possibilités influencera le choix 
		de maximum des lignes qui suivent et le résultat sera mauvais
		(je n'ai pas de solution en tete pour ca mais ca se fait bien j'imagine)
	}
}

[yal001]

Hum, ça me semble une bonne idée.

Je pense qu'il faut faire quelques adaptations cela dit parce que si j'ai bien compris l'algo

Ceci:
(9 1)
(5 0)

me donnerait comme solution 9, alors que ma solution est 1-5, puisque c'est celle qui a le plus grand nombre d'éléments.

Cela dit, ça me semble une bien meilleure méthode que ce que moi j'avais fait (j'ai fait un arbre des solutions, et même en optimisant le parcours, ça n'était pas performant du tout tant il y a de solutions possibles )

[ToTo13]

Bonjour,

c'est quoi la taille "énorme" de ton tableau ? Quelles sont les dimensions exactes ?
As tu une contrainte de temps pour l'exécution ?

[Nehmé]

Ceci:
(9 1)
(5 0)

me donnerait comme solution 9, alors que ma solution est 1-5, puisque c'est celle qui a le plus grand nombre d'éléments.

c'est plutôt 9-0 au lieu de 1-5. j'ai oublié que tu ne veux pas de zero !

[yal001]

Bonjour Toto13,

la taille du tableau est variable mais (pour le moment) cela tourne autour de 60*60 (ce qui en soit n'est pas si grand, mais quand on considère toutes les solutions que ça peut donner, en fait si )
J'ai en effet des contraintes de temps d'exécution, cela ne doit dépasser quelques secondes.

Nehmé: en effet je ne veux pas de 0, ce qui ne simplie rien!