Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Algorithme

Posté par
Portouti
17-03-15 à 13:00

Bonjour,

je n'arrive pas à coder un algorithme efficace (et surtout juste) pour résoudre le problème suivant :
Soit n entier compris entre 5 et 49. Soit p un entier compris entre 1 et 5. Soit G l'ensemble des parties de [|1,n|] de cardinal 5. Je cherche à construire un ensemble J de cardinal minimal, sous ensemble de G tel que \forall g \in G , \exists j \in J \text{ tel que card} (g \cap j) \geq q.
J'ai essayé de faire un algorithme naïf (en CamL) mais le J qu'il rend n'est pas de cardinal minimal.

Merci de vos suggestions.

Posté par
Portouti
re : Algorithme 17-03-15 à 13:16

Pour ôter toute ambiguité, je prends n un entier entre 5 et 49. De plus, je me suis trompé, c'est q qui est un entier compris entre 1 et 5, il n'y a pas de p.

Posté par
carpediem
re : Algorithme 17-03-15 à 17:58

salut

ben si le sous-ensemble J qu'il te renvoie n'est pas de cardinal minimal essaie d'enlever des éléments de J "qui sons superflus" ...

peut-être une idée ::

à deux éléments a et b de J associe l'ensemble c = a b + 1 élément de a/b et/ou 1 élément de b/a avec card(c) = 5

tu remplaces alors deux éléments de J par un donc tu divises le cardinal par 2 ...

ensuite si c'est trop recompléter par certains éléments de l'ensemble J initial ...

Posté par
Portouti
re : Algorithme 19-03-15 à 18:50

Le problème, c'est qu'il n'y a pas d'éléments que je puisses enlever facilement de l'ensemble qu'il me renvoie. Je parcours les elements de G et si l'élément que je suis en train de considérer a une intersection de cardinal plus grand que q avec l'un des éléments déja dans J, je le laisse tomber et passe au suivant, sinon, je l'ajoute dans J.

Je suis pas sur d'avoir compris comment tu construisais ton ensemble c.

Posté par
vham
Algorithme 25-03-15 à 10:58

Bonjour,

Avez-vous essayé de chercher : "Block design" sur internet
ou encore "LJCR tables" (La Jolla Covering Repository) qui vous donnent les résultats connus, y compris les méthodes par lesquelles ils ont été obtenus.
par exemple si vous demandez v=12,k=5, k>=1 vous aurez 3 résultats, pou k=2,3,ou 4 et vous pourrez afficher les blocks solutions minimales
@+

Posté par
Portouti
re : Algorithme 30-03-15 à 00:21

Les LJCR tables m'ont l'air très intéressantes ! Merci.
Tant pis pour mon algorithme.

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !