Discussion :

[LiquidHuk]

Bonjour,

On m'a récemment proposé cet énoncé et comme je ne suis pas parvenu à une solution maline au problème, je suis à la recherche d'un nom à mettre sur celui-ci afin d'en apprendre plus sur les différentes solutions.

A partir d'un tableau de N valeurs (1 < N < 32), découper le tableau en trois groupes vérifiant la condition suivante : Les sommes des valeurs de chaque groupes doivent être égales.
Retourner une chaîne de caractère de taille N qui pour chaque valeur du tableau fait correspondre un groupe donné par les lettres "R", "G" ou "B". Si le tableau ne possède pas de solution, retourner "impossible".

Exemple : [1, 5, 6, 3, 7, 1, 2, 8, 3]
Une solution possible : "RRRGGBGBB"
R : 1+5+6 = 12
G : 3 + 7 + 2 = 12
B : 1 + 8 + 3 = 12

[yahiko]

Je ne sais pas si ce problème a un nom, mais cela ressemble plus à un problème mathématique de de l'algorithmique pure.

Néanmoins, voici une piste de résolution :

Puisque nous avons 3 groupes (R, G et B), la somme S des N valeurs doit être divisible par 3.

Chaque groupe doit donc avoir un total égal à s = S / 3.

Le job consiste donc à trouver l'ensemble des groupes de nombres dont la somme est égale à s.
Si N n'est pas trop grand, un algorithme naïf devrait être acceptable.

[tbc92]

Bonjour,

L'objectif de cet exercice, c'est quoi ?
C'est de parcourir toutes les combinaisons possibles,autrement dit, parcourir toutes les branches d'un arbre.
Dans l'exemple avec [1, 5, 6, 3, 7, 1, 2, 8, 3], on associe 1 avec 5 , puis 1 avec 5 et avec 6,1 avec 5 avec 3 ... etc, jusqu'à trouver une solution au problème.
Parcourir toutes les branches d'un arbre, il y a un algorithme incontournable pour cela, c'est l'algorithme A*.

Après, si on veut optimiser le truc, on va ordonner les nombres du plus grand au plus petit, parce que c'est comme ça qu'on va éliminer au plus vite les combinaisons qui mènent à des impasses.

Et c'est clairement un exercice d'algorithmique, et non de maths.

[yahiko]

En effet, ça peut se résoudre avec du A*, l'auteur du post sera donc content d'avoir la réponse.

[LiquidHuk]

A* se base sur le coût de passage d'un nœud à un autre pour effectuer les calculs jusqu'à l'arrivée (dans le cas de recherche de chemin).
Je ne vois pas bien le rapport entre les deux tbc92 ?

[tbc92]

L'algorithme A* commence par une première chose :
J'ai un point de départ (un noeud).
A partir de n'importe quel noeud, je sais comment trouver ses voisins immédiats. : 2 noeuds voisins sont reliés par un ARC
Je cherche un chemin pour aller de mon noeud de départ au noeud d'arrivée.
Et l'algorithme A* aide à explorer tous les chemins possibles, rebrousser chemin quand on est dans une impasse ... C'est cela l'objectif n°1 de l'algo A*.
Dans sa version plus élaborée, il va optimiser. Il va mettre de coté les chemins qui semblent peu prometteurs, et il va chercher le chemin le plus court.


Ici, c'est quoi notre exercice.
On a 4 boites : Une boite P=Pioche, une boite R=Rouge, une boite G (G=Green = Verte) et une Boite B=Bleue.
Le noeud de départ : tous les pions sont dans la boite P
Le noeud d'arrivée ? En fait, il y a plein de situations d'arrivées possibles, ce sont toutes les situations où la pioche est vide, et les 3 boites ont des montants égaux.

Les mouvements possibles : Un mouvement, c'est déplacer un pion d'une boite à une autre.
On peut même limiter les mouvements en disant que les pions sont ordonnés dans chaque boite ( un peu comme des cartes posées en tas), et les mouvements autorisés, c'est : prendre la carte qui est en haut d'une pile, et la poser en haut d'une autre pile. Ca limite énormément le nombre de doublons dans les hypothèses à explorer.

Ca y est , on a défini nos NOEUDS, nos ARCS ... On peut appliquer le fameux Algo.

[Flodelarab]

Bonjour,

Pas compris ton truc de cartes, de pions et d'A*.

Je trierais les nombres.
J'en ferais la somme divisée par 3 pour fixer l'objectif de chaque groupe qui eux-aussi seront triés.
Puis je passerais tous les nombres en revue pour trouver la somme fatidique.
Si j'en trouve une, je passe au groupe 2 ... puis au groupe 3... toujours en respectant la croissance des nombres.
Quand je bloque, j'arrête cette voie.
Si je ne bloque pas, mes groupes sont constitués.

[tbc92]

Bonjour,

Pas compris ton truc de cartes, de pions et d'A*.

Je trierais les nombres.
J'en ferais la somme divisée par 3 pour fixer l'objectif de chaque groupe qui eux-aussi seront triés.
Puis je passerais tous les nombres en revue pour trouver la somme fatidique.
Si j'en trouve une, je passe au groupe 2 ... puis au groupe 3... toujours en respectant la croissance des nombres.
Quand je bloque, j'arrête cette voie.
Si je ne bloque pas, mes groupes sont constitués.

Oui, c'est exactement ça.
Mais quand tu dis ' je passe en revue tous les nombres..., en fait tu veux dire que tu passes en revue toutes les combinaisons. Et si j'ai 20 ou 30 'pions' dans la pioche, ça fait énormément de combinaisons à explorer.
Et comment je fais pour explorer toutes les combinaisons, jusqu'à trouver une solution, sans en oublier une ?
Tu as un algorithme pour cela ?

Sinon, dans un second temps, une fois que tu auras une solution pour la première question, il y aura une autre question : tu dis que tu classes les nombres par ordre croissant... pourquoi par ordre croissant ? Tu n'as pas envie de les classer plutôt par ordre décroissant ?

[Invité]

juste pour parenthèse, je vois pas à quoi sert A* son but est de trouver un plus court chemin non?
Ici il ne s'agit pas de plus court chemin.

On peut éventuellement parler de parcours de graphe, mais je vois pas la relation avec A*.

Ensuite, faire un graphe c'est qu'une manière de représenter les choses, donc faut pas etre surpris si on parle pas de graphes.

Et enfin, une alternative,
on liste tous les groupes qui valent la moyenne, et une fois faits, on en prend trois parmi la liste et on regarde si les elements sont tous distincts. (un élement étant identique à un autre s'il a le même index dans le tableau d'origine)

[Prof]

Bonjour.

Si on cherche à résoudre ce problème par la force brute, c'est-à-dire en étudiant tous les cas, il n'est pas nécessaire d'utiliser un arbre.
Un simple algorithme itératif convient parfaitement.

Chaque élément du tableau doit figurer dans un et un seul groupe.
Il y a donc 3 cas possibles pour chaque élément, ce qui fait en tout 3^N cas à envisager.

La méthode est donc la suivante :
si i est un nombre compris entre 0 et 3^N-1, on décompose i en base 3 ;
l'écriture de i en base 3 est constituée de N chiffres, chacun de ces chiffres pouvant être 0, 1 ou 2 ;
on a donc le groupe des 0, le groupe des 1, le groupe des 2 ;
on calcule la somme des valeurs pour le groupe 0, pour le groupe 1, pour le groupe 2 ;
si ces 3 sommes sont égales, on a trouvé une solution au problème.

Cela semble long, mais en fait cela se programme simplement.

Voici la fonction qui examine si un entier compris entre 0 et 3^N-1 est une solution :

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
 
FONCTION Solution(indice:ENTIER): BOOLEEN
    m,j,p : ENTIER
    S : TABLEAU[0..2] DE ENTIER
    DEBUT
        S[0] <- 0
        S[1] <- 0
        S[2] <- 0
        m <- indice
        POUR j DE 1 A N FAIRE
             p <- m mod 3
             S[p] <- S[p] + T[j]
             SI (S[p] > tiers) 
                 ALORS RETOURNER(FAUX) 
             FINSI
             m <- m div 3
        FINFAIRE
        RETOURNER(VRAI)
    FIN

Les valeurs auront été au préalable placées dans le tableau T[1],..,T[N].
J'ai appelé tiers le total à obtenir, c'est-à-dire la somme des toutes ces valeurs, divisée par 3.
mod est le modulo, div la division entière.
Le tableau S contient les sommes de chaque groupe.
Dés qu'une de ces sommes dépasse tiers, on sait qu'on n'a pas une solution et on sort de la fonction avec le résultat FAUX.
Si on arrive à parcourir la boucle en entier, c'est qu'aucune somme ne dépasse tiers ; on a donc forcément une solution.

Dans le programme principal, on placera la boucle suivante :

Code :

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

1
2
3
4
5
6
7
 
    POUR i DE 0 A 3^N-1 FAIRE
         SI Solution(i) 
            ALORS Affiche(i)
                  SORTIRBOUCLE
         FINSI
    FINFAIRE

Pour achever l'écriture du programme, il reste à :
- déclarer les variables globales ;
- entrer N et le tableau T[1],..,T[N] ;
- calculer la somme de ces valeurs, vérifier qu'elle est divisible par 3, mettre cette somme divisée par 3 dans la variable globale tiers ;
- écrire la procédure Affiche(indice) qui décompose indice en base 3, remplace 0,1,2 par les lettres R,G,B et affiche le résultat ;
- gérer les messages, en particulier introduire un booleen pour savoir si une solution a été trouvée.

Remarque :
3^9 = 19683, 3^15 = 14348907, 3^20 = 3486784401, 3^31 = 617673396283947.
L'emploi de la force brute pour résoudre ce problème devient problématique dès que N dépasse 20.
Dans ce cas, il faudra envisager une autre méthode.

[Flodelarab]

Et comment je fais pour explorer toutes les combinaisons, jusqu'à trouver une solution, sans en oublier une ?
Tu as un algorithme pour cela ?

Je ne peux pas en oublier une puisque je les passe toutes en revue. Et ce qui m'assure l'efficacité, c'est la croissance stricte. Et la croissance stricte est facile à faire respecter si les éléments de mes tableaux sont triés.

Tu n'as pas envie de les classer plutôt par ordre décroissant ?

Aucune importance puisque je trouverais toutes les solutions possibles. L'exhaustivité me permet de ne pas avoir à choisir entre croissance et décroissance.

Si le but était de trouver vite, alors ton idée de décroissance serait préférable, sûrement.

[LiquidHuk]

Merci à tous pour vos réponses.

tbc92, je connais l'algorithme A* et son fonctionnement pour l'avoir utilisé à plusieurs reprise. Ce que je ne comprends pas dans ton explication, c'est quand tu écris :

Et l'algorithme A* aide à explorer tous les chemins possibles, rebrousser chemin quand on est dans une impasse ... C'est cela l'objectif n°1 de l'algo A*.
Dans sa version plus élaborée, il va optimiser. Il va mettre de coté les chemins qui semblent peu prometteurs, et il va chercher le chemin le plus court.

Comment est-ce que tu vas, dans cette situation, calculer un "coût de déplacement" ou définir un chemin "prometteur". En d'autres termes, que sont les fameux G et H habituellement utilisés dans A* ?


Merci Prof pour cette nouvelle idée. Même si comme tu l'as dis ce n'est pas applicable ici, l'idée de passer en base 3 est intéressante.

Flodelarab, cette méthode est à la fois très simple à comprendre et efficace. Merci

[tbc92]

Je vais reprendre 'ma' vision de l'exercice, sur la base de l'exemple initial.


On a 4 tas de cartes : Un tas intitulé Pioche, et 3 autres tas intitules R G et B

La situation de départ : le tas intitulé Pioche contient 9 cartes marquées : [1, 5, 6, 3, 7, 1, 2, 8, 3], ou plutôt [8, 7, 6, 5, 3, 3, 2, 1, 1]

Les 3 autres tas sont vides.


A tout moment, première approche, les mouvements possibles : Prendre la 1ère carte de la pioche, et la mettre dans l'un ou l'autre des 3 tas R G ou B ; On retrouve donc les 3^9 mouvements possibles recensés par Prof.

Si on utilise cette première approche, on dira :

h() = 0 si aucun des 3 tas R G B ne dépasse 12

h() = 100 si au moins un des 3 tas dépasse 12.



En 2ème approche, les mouvements possibles sont :

Prendre la 1ère carte de la pioche, et la mettre dans l'un ou l'autre des 3 tas R G ou B, à CONDITION que ce tas ne dépasse pas 12.


Pour coller avec les fonctions g et h de l'algo A*, la fonction g est donc : Nombre de cartes prises dans la pioche, et mises dans l'un ou l'autre des 3 tas R G ou B.

g() est donc un nombre entre 0 et 9.


Et pour la fonction h() : h() = 0 quelque soit la position.


C'est une version édulcorée de l'algorithme A*.
Peut être même qu'elle ne mérite pas le nom de A* , c'est possible, je ne suis pas spécialiste.

[LiquidHuk]

Je crois que je comprends mieux ce que tu veux dire avec ce dernier post, merci !

[Trap D]

Je n'ai pas suivi toute la discussion, mais c'est un peu un problème de contraintes qui se résoud bien en Prolog.
j'ai fait l'essai avec 32 valeurs, ca semble assez rapide, il faudrait faire un test avec un cas difficile !
Lle code en SWI-Prolog :

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
:- use_module(library(lambda)).
:- use_module(library(clpfd)).
 
rgb(L) :-
        % L = [1, 5, 6, 3, 7, 1, 2, 8, 3].
	numlist(1,32, L).
 
rgb(L, A) :-
	length(L, N),
	sumlist(L, TT),
	(   TT mod 3 =:= 0
	->  Max is TT//3,
	    A = [A1,A2,A3],
	    maplist(\X^(length(X, N), X ins 0..1), A),
	    maplist(\X^Y^Z^(X+Y+Z #= 1), A1,A2,A3),
	    maplist(L +\X^Y^foldl(\T^U^V^W^(W #= V + T * U), L, X, 0, Y), A, R),
	    maplist(\X^(X #= Max), R),
	    flatten(A, FA),
	    label(FA)
	;   writeln('Impossible'),
	    A = [[],[],[]]).
 
t :-
	rgb(L),
	writeln(L), nl,
	rgb(L, A),
	maplist(writeln, A).