tableau à double entrées et "aide à la décision"

[zyket]

Bonjour,

ceci n'est pas un exercice mais un problème bien réel auquel je suis confronté.

Je suis enseignant en maternelle, et j'ai décidé de mettre en voix un album pour enfants. Pour chaque phrase de l'album j'ai enregistré au moins un de mes élèves. J'ai 26 phrases et 23 élèves. Les élèves choisissaient au hasard la (les) phrase(s) qu'ils voulaient enregistrer. Je me retrouve donc avec des phrases enregistrées par au moins un élève, et avec des élèves ayant enregistré au moins une phrase chacun. J'ai fait un tableau double entrée (cf pièce jointe) avec une ligne par enfant et une colonne par phrase. Chaque case correspondant à une phrase enregistrée par un enfant est marquée du chiffre 1. En début de chaque ligne j'ai le total d'enregistrements par enfant. En haut de chaque colonne j'ai le total d'enregistrements par phrase.

Problème :
Comment à partir de ce tableau trouver une solution, si elle existe, pour que chaque phrase ne soit dite qu'une fois et que tous les enfants parle au moins une fois ?

Existe-t-il dans les tableurs une fonction permettant de savoir si il existe au moins une solution ? Et si oui lesquelles ?

Sinon à part le tâtonnement, auriez-vous une procédure manuelle à me proposer ?

Merci
-----

[Dlzlogic]

Bonjour,
C'est marrant votre problème.
Je résume, il y a 3 phrases de plus que d'enfants, donc, au moins 3 enfants diront 2 phrases.
Vous voulez que chaque phrase ne soit dite qu'une fois, dont il y a aura exactement 20 enfants qui diront une seule phrase et 3 enfants qui en diront 2.
Il y a donc un très grand nombre de solutions.
Si j'étais vous, dans un premier temps, en colonne N+1 je mettrais le total des phrases que cet enfant a choisi, et en ligne M+1 le total des phrases qui ont été choisies.
En fin de manipulation, la dernière colonne ne devra comporter que des 1 sauf 3 nombre 2. La dernière ligne ne devra comporter que des 1.
Je ne vois pas d'autre solution que de supprimer des 1 dans les cellules, au fur et à mesure, sachant qu'il vaut mieux commencer par celles dont le total, vertical et horizontal est le plus grand.
Une cellule dont les totaux sont égaux à 1 ne devra naturellement plus être modifiée.
Ce serait un petit algorithme amusant à faire, mais je crois qu'avec cette méthode des totaux, ça ira très vite.
Naturellement il vaut mieux faire une sauvegarde en cas de fausse manipulation.

[gg0]

A noter : Si une phrase n'est dite que par 1 seul enfant, il n'y a pas le choix. Donc on peut retirer ces phrases et ces enfants du tableau, qui va déjà bien se réduire. Si on n'arrive plus à faire prononcer toutes les autres phrases par les enfants restants, on ira rechercher dans les enfants "supprimés" qui peut prononcer les phrases restantes.

Cordialement.

[leon1789]

Votre problème est un problème classique d'affectation.

Si l'on "marche au petit bonheur la chance", alors il y a un fort risque de se retrouver dans une situation où il n'y a plus de solution. En informatique, on peut utiliser du backtracking pour une recherche brutale de solution.

Il existe d'autres algorithmes plus ou moins sophistiqués pour résoudre (si possible !) ces problèmes, tirés de la théorie des graphes : par exemple, l'algorithme hongrois (qui permet même de considérer des poids... selon la qualité de la prononciation des élèves si on voulait.)

En tout cas, il faut toujours commencer par traiter les enfants ou les chansons qui ont un total le plus petit. Typiquement, les phrases ayant été préparées par un seul enfant sont directement affectées (comme l'a dit gg0).

[A voir en vidéo sur Futura]

[leon1789]

...ah, sauf que l'algorithme hongrois prendrait N élèves et N phrases. Peut-on l'adapter dans le cas où il y a plus de phrases ??

[NicoEnac]

Bonjour,

Première remarque : dans la ligne de Louis, vous avez écrit "2" au lieu de "1" pour la phrase "pas dans mon jardin" faussant ainsi le comptage.

Ensuite, votre problème possède des contraintes qu'il vous faut appliquer avant de lancer n'importe quel algorithme.
1ère contrainte : chaque phrase doit être prononcée. Prenez les phrases qui dont vous n'avez qu'un seul enregistrement (exemple "pouah") et attribuez-la à l'enfant qui l'a prononcée. Vous obtenez ainsi rapidement que "pouah" et "beurk" sont attribuées au collectif et que Marie dira "qu'est ce que c'est que ça ?" et "des bananes". Vous avez, par cette seule contrainte, presque déjà réglé le problème des doublons.

J'ai appliqué cette contrainte à votre tableau et pu attribuer 9 phrases à 7 enfants.

Ensuite, je vous conseille de prendre les phrases qu'il vous restera en commençant par les moins prononcées et en les attribuant aux enfants offrant le moins de possibilités. De telle manière, vous vous garderez le plus de possibilités pour la suite.

[Dlzlogic]

Bon, j'ai commencé par les plus grands nombres, comme j'avais dit, j'ai été coincé à la fin.
J'ai recommence avec les plus petits, et cette fois-ci en essayant d'agir de façon non systématique, je me trouve coincé aussi. Mais je me suis peut-être trompé, de toute façon, j'aime pas Excel.
Pour permettre de revenir en arrière, le plus simple me parait être de mettre 0 au lieu de 1, ce qui fait qu'on peut facilement rétablir une cellule à la fois.
Y'a un truc que j'ai pas compris, vous avez 22 élèves + le collectif, ou 23 élèves dont un s'appelle "collectif", ou alors 22 élèves, les phrases "pouah" et "beurk" sont dits par tout le monde ?

[leon1789]

Je ne vois pas d'autre solution que de supprimer des 1 dans les cellules, au fur et à mesure, sachant qu'il vaut mieux commencer par celles dont le total, vertical et horizontal est le plus grand.
Une cellule dont les totaux sont égaux à 1 ne devra naturellement plus être modifiée.
Ce serait un petit algorithme amusant à faire, mais je crois qu'avec cette méthode des totaux, ça ira très vite.

Bon, j'ai commencé par les plus grands nombres, comme j'avais dit, j'ai été coincé à la fin.

Effectivement, comme tu avais dit.

J'ai recommence avec les plus petits, et cette fois-ci en essayant d'agir de façon non systématique, je me trouve coincé aussi.

Si l'on "marche au petit bonheur la chance", alors il y a un fort risque de se retrouver dans une situation où il n'y a plus de solution.

Le problème n'est pas aussi simple qu'il peut paraître. C'est comme un sudoku.

[Dlzlogic]

Décidément, tu ne peux pas t'empêcher d'intervenir lorsque j'ai répondu à une question.
Bon, en gros, tu proposes quoi ?

[leon1789]

Comme je disais, une méthode brutale est le backtracking (algorithme récursif qui explore toutes les branches possibles, bourrinement)

Voici une première solution :


(en jaune, les affectations obligatoires, signalées par NicoEnac)

[zyket]

Bonjour,

je reviens vers vous avec un peu de retard mais vous remercie tous vivement.

@Dlzlogic

Y'a un truc que j'ai pas compris, vous avez 22 élèves + le collectif, ou 23 élèves dont un s'appelle "collectif", ou alors 22 élèves, les phrases "pouah" et "beurk" sont dits par tout le monde ?

Je précise (mais j'ai l'impression que les trois propositions sont équivalentes ?) : j'ai 22 élèves et les phrases "pouah" et "beurk" sont bien dites par tout le monde que je nomme comme un 23ème élève qui s’appellerait "collectif".


@NicoEnac

Première remarque : dans la ligne de Louis, vous avez écrit "2" au lieu de "1" pour la phrase "pas dans mon jardin" faussant ainsi le comptage.

Louis a enregistré deux fois la même phrase. Ce qui j'en conviens est une donnée inutile du problème.

Un merci particulier à leon1789 qui me propose une solution que je vais de ce pas appliquer.

Encore merci à tous