Discussion :

[bourgot]

Bonjour,
je suis Programmeur-Analyste et je dois trouver un Algorithme de recherche.

je dois trouver un Algorithme de recherche.

La recherche se fera dans un tableau de maximum 150 colonnes par maximum 5000 lignes.

Le contenu des champs est soit 0 ou 1.

la recherche se fera sur 2 à 25 colonnes.

Le résultats doit être le plus grand nombres d'éléments en commun pour un nombre de colonnes demandé, je doit afficher les 20 meilleurs résultats.

Exemple Simple:

tableau de 80 colonnes par 1 ligne , recherche sur 3 colonnes

Tableau:

1 1 1 0 1 0 1 0 0 1 1 1 0 ............. jusqu'a 80

1 résultat: Col 1, Col 2 , Col 3
2 résultat: Col 1, Col 2 , Col 5
3 résultat: Col 1, Col 2 , Col 7
4 résultat: Col 1, Col 2 , Col 10
...
...
n résultat: Col 1, Col 3 , Col 5
n résultat: Col 1, Col 3 , Col 7
......

Ici l'exemple est sur une ligne,
sur 500 lignes exemple: le résultat "Col 1, Col 2 , Col 10" pourrais être retrouvé sur les lignes 1,5,34,56,67,89, ..... , Comme notre recherche est sur 3 colonnes , le trio qui a plus de rangés sera le meilleur résultat.


l'Algorithme plus haut est de faire toutes les itérations, j'ai calculé que pour 1 ligne par 80 colonne sur une recherche de 3 colonnes ça prend 164 650 itérations, pour le même tableau mais une recherche sur 4 colonnes ça prendrais 4 744 740 itérations, donc je n'ose imaginé une recherche sur 25 colonnes dans un tableau de 150 colonnes par 5000 lignes.



Si quelqu'un aurais des idées, ca serais très apprécier.

Richard
rp@oberon-inf.com

[FrancisSourd]

Ce problème est NP-complet. On ne connaît donc pas d'algorithme efficace pour le résoudre. Il faut donc passer par l'énumération. Vous proposez un algorithme d'énumération explicite, mieux vaux s'orienter vers de l'énumération implicite (branch-and-bound)... mais cela demande du travail....

Sinon, il faudrait vous orienter vers des algorithmes approchés (heuristiques, métaheuristiques)