@White Crow: Est-tu vraiment en train de dire qu'il n'existe effectivement aucune solution pour N=36 et k=6 ou si c'est parce que tu n'en as pas trouvé? Comme tu l'as vu, j'ai commencé à regarder ta solution avec les graphes, mais je n'ai pas eu le temps de la compléter. Je pense avoir bien montré ci-haut que le nombre d'itérations (si la solution existe) est (N-1) / (k-1) @sylpro: Un algorithme de flot maximum? Je connais, mais je ne comprend pas comment s'en servir dans ce contexte. En passant, lequel utiliserais-tu? Le Push Relabel?
Le Tout est souvent plus grand que la somme de ses parties.
@sylpro: Un algorithme de flot maximum? Je connais, mais je ne comprend pas comment s'en servir dans ce contexte. En passant, lequel utiliserais-tu? Le Push Relabel?
Comme l'as remarqué WhiteCrow, je me suis trompé dans la contrainte, la mienne est moins forte; donc je ne résouds pas le problème de flolem. Après, effectivement, on peut peut-être s'inspirer de l'algo décrit stackoverflow. Pour le flot maximum, dans l'algo proposé, on part de "partitions" vides et pour i de 1 à N on place le nombre i dans exactement un sous-ensemble de chaque partition. L'algo du flot max sert alors à faire le choix du sous-ensemble pour chaque partition dans lequel on place le nombre i.
Voilà comment il fait le choix :
on part du réseau suivant :
Sommets : un sommet pour la source s, un sommet pour chaque pseudo-partition de l'étape i-1, un sommet pour chaque sous-ensembles contenant i et DES nombres inférieurs (du style, si i=4 : {1,4},{2,3,4} ou {4}) et un sommet pour le puit t
Arcs et capacités : un arc de capacité 1 entre la source et chaque partition; un arc de capacité 1 entre chaque partition et chaque sous-ensemble contenant i qui peut potentiellement prendre place dans la partition (par ex, si la partition contient déjà {1,2}, il y aura un arc vers {1,2,4} et {4} mais il n'y aura pas d'arc vers {1,4}) et pour finir, un arc de capacité binome(n-i,k-#e) entre chaque sous-ensemble e et le puit (cette capacité correspond au nombre de fois qu’apparaît le sous-ensemble e les partitions)
Une fois l'algo du flot max effectué sur ce réseau, on récupère le flot max restreint aux arcs entre partitions et sous-ensembles : le sous-ensemble est dans la partition si le flot est égal à 1 sur l'arc correspondant !
Pour ma part, j'ai implémenté le flot max avec l'algo de Dinic et pas le push relabel mais comme leur complexité est la mêmedonc pourquoi pas ! - comme le nombre d'arêtes est bien supérieur au nombre de sommets mieux vaut minimiser la complexité en terme de nombre d'arêtes.
@White Crow: Est-tu vraiment en train de dire qu'il n'existe effectivement aucune solution pour N=36 et k=6 ou si c'est parce que tu n'en as pas trouvé? Comme tu l'as vu, j'ai commencé à regarder ta solution avec les graphes, mais je n'ai pas eu le temps de la compléter. Je pense avoir bien montré ci-haut que le nombre d'itérations (si la solution existe) est (N-1) / (k-1)
Comme je le disais à Flolem, l'existence d'une solution à son problème nécessite l'existence d\un BIBD de même paramètres. En l'occurrence le problème du tournoi avec 36 participants et des partitions de taille 6 nécessite l'existence du BIBD(36,6,1). Or Mills a prouvé en 1984 qu'un BIBD de paramètre (n,6,1) n'existe que pour n=1 ou 6 modulo 15 avec n différent de 16,21 et 36. Du coup il n'y pas de solutions possibles à ce problème.
→ W.H. Mills, Balanced incomplete block designs with k = 6 and A = 1, Enumeration and design, D. M. Jackson and S. A. Vanstone (Editors) Academic, Canada, 1984, pp. 239-244.
Cela fait partie des documents que j'ai cité dans un message à flolem. Si tu veux, je peux te fournir les mêmes docs, pas ici mais en mp …
Par contre, je me demande le nombre d'itérations maximum que l'on peut découvrir avec n=36 et k=6
Ou avec N=42 et k=6 (mon problème initial)
En vrai, mon intêret est de connaitre une possible répartition pour X itérations en utilisant la contrainte du 1 le plus possible.
Genre: avoir 6 itérations de 7 groupes de 6 pour 42 personnes (BIBD(42,6,1)) et si ce n'est pas possible passer à A=2 (BIBD(42,6,2)) à partir de l'itération suivante.
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.