Discussion :

[cyberkamikaz]

Salut,
(J'ai ajoute encore des explications et des exemples dans un post en dessous)
Dans une chaîne de ballons, on a deux types de ballons : les rouges et les noirs. Les ballons ont une propriété : si il y a trois ballons de la même couleur, l'une à côté de l'autre,les trois exploses . On a une autre chaîne de ballons (qui n'explosent pas ici) d'où l'on prend à chaque fois un ballon de la gauche et on le met dans la première liste n'importe où.

Par exemple, on à la chaîne initiale : « RRNNRRNRNR » et la deuxième chaîne d'où on va prendre un ballon, un à la fois, et le mettre dans la chaîne initiale : RNR.

On prend le premier R et on va le mettre là : RRNNRRRMRNR.
Comme vous le voyez, ces ballons vont exploser (souligné) : « RRNNRRRNRNR »

… et on ne restera qu'avec RNRNR et la liste d'où on prend à chaque fois un ballon : « NR ». On répete la procédure : on va prendre « NR » et le mettre à une position dans la chaîne initiale « RNNRNR ». Rien ne va exploser car on n'a pas trois couleurs identiques côte à côte. Au dernier pas, on va prendre le dernier qui reste R et le mettre dans la chaîne initiale : « RNNRNR ». Et, encore une fois rien ne va exploser.

Dans un fichier, on a les deux chaînes de caractères : la chaîne initiale et la chaîne d'où on prend un ballon. Et on doit calculer le numéro minimum des ballons pris de la deuxième chaîne pour arriver à vider la chaîne initiale.

Comment faire pour calculer ce nombre minimum cite en dessus ?

Je ne sais pas comment faire mais je crois que c'est avec du backtracking ,J'aimerais bien une autre solution si c'est possible plus optimisé (Memoire et Temps) .


Merci d'avance.


Ps:
Meme le backtracking je ne m'y connais pas (j'ai seulement entendu en quoi il conste).

[250rgv]

Donc, tu voudrais que nous fassions tes devoirs ?

[cyberkamikaz]

J'aimerais seulement que vous me metiez sur route.

[250rgv]

Et bien tu peut déjà commencer par :
* faire un algo "naif" sans optimisation, elle viendra en son temps.
* chercher ce qu'est le backtraking par ex. ici.
* rechercher ce que sont les méta-heuristiques comme les fourmis, les algo. génétiques, le recuit simulé, le hill-climbing (me souvient plus du nom "français") et d'autres.
* etc...

[cyberkamikaz]

Merci pour ton aide.
Je vais voir tous ce que tu m'a donne.

[cyberkamikaz]

La seule chose qui me passe par la tete est de utiliser le backtracking + des conditions pour reduire les solutions partielle mais je crois pas que ca marche prenons la conditions de ajouter le ballon a cote de 2 autres ballons de la meme couleure qui existe dans la chaine initiale.
Je crois pas que ca marche parceque on peux poser le ballons dans d'autres lieux et pui il y'auras plusieres reductions (explosions).

[pseudocode]

C'est marrant comme jeu.

si il y a trois ballons de la même couleur, l'une à côté de l'autre, deux explosent et on ne reste qu'avec une seule

RRR -> R
NNN -> N

On prend le premier R et on va le mettre là : RRNNRRRMRNR.
Comme vous le voyez, ces ballons vont exploser (souligné) : « RRNNRRRNRNR »

hum... je ne vois pas trop comment ca marche

RRNN(RRR)NRNR --> RRNN(R)NRNR

[cyberkamikaz]

Je vais ecrire quelques exemples :
Car c'est faux
Je me suis mal exprime il fallait dire que toutes les 3 exploses comme dans l'exemple .
Merci pseudocode pour la remarque


nous avons deux chaines de ballons chaine initiale et chaine d'aprovisionement (d'ou on va prendre a chaque pas un ballon.

1 er exemple :

chaine initiale:
(R)(R)(N)(N)(R)
chaine d'aprovisionement:
(N)(R)

1 er pas
on prend le 1 er (N) de la deuxieme chaine (on commence toujours par la gauche )

et on va le mettre dans n'importe quelle endroit de la chaine 1 (la chaine initiale )
supsons qu'on l'a mis (R)(R)(N)(N)(N)(R) (celui souligne ) comme j'ai dit avant si on trouve 3 ballons de la meme couleure les 3 exploses alors la chaine initiale ressemblerait a ca : (R)(R)(R) qui vont a leur tour exploser et on va rester avec rien
Le probleme c'est qu'il y a beaucoud possibilite de plasser le ballon pris de la chaine d'aprovisionemment alors on n'auras pas le meme numero de pas pour arriver a ce rien (eliminer tous les ballons de la chaine initiale )
si les ballons de la chaine d'aprovisionemment ne suffises pas il faut retourner toutes le combinaisons minime ordone lexicographiquement .

Pour ca voici l'exemple

in :
(R)(B)

(B)(R)

out

(B)(R)(B)(R)

(B)(R)(R)(B)

(R)(B)(B)(R)

(R)(B)(R)(B)

(R)(R)(B)(B)

[TNT89]

on n'auras pas le meme numero de pas pour arriver a ce rien

euh, les méthodes suivantes sont purement identiques :

... (R)(N)(N)(N)(R) ...
... (R)(N)(N)(N)(R) ...
... (R)(N)(N)(N)(R) ...

Car dès qu'il y a trois ballons identiques alors ils explosent... Je pense que déjà il faut te donner une convention : quand je chercherai à faire exploser trois ballons, je poserai toujours mon ballon en tête de la chaîne visée

Ensuite, il faut essayer des cas (une bonne feuille et un bon crayons aident beaucoup dans ces moments là...) : est-il nécessaire d'avoir une stratégie orientée? (ie : si je pose le ballon rouge ici et le noir un peu plus tard là-bas alors je vais réussir à faire pêter plus de ballons qu'en essayant de poser d'abord le noir, puis le rouge) Si oui, il faudrait, à mon goût, opter pour une stratégie en arborescence comme pour les échecs. Et donc, établir tous les coups "à blanc" dans une structure arborescente sur, par exemple, 6 placements successifs et prendre uniquement celui (ou ceux?) qui minimisent le nombre de ballons obtenus à la fin de ce combo.

Personnellement je ferais dans un premier temps comme s'il n'y en avait pas et je me focaliserais sur un algorithme qui localiserait à chaque passe les séries de ballons qu'il puisse faire exploser et qui les classerait en fonction du nombre de combos que chacun entraîne. Un petit exemple :

Code :

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

1
2
3
4
5
6
   Arrivée : (R)

    (R)(R)(N)(R)(N)(N)(R)(R)(N)(N) : la ligne des ballons courante
   ^                  ^            : la ligne des intérêts pour un ballon rouge (si tu places un ballon ici alors, tu es sûr de exploser des ballons)
   0                  4            : le nombre de ballons explosés par combo

On choisit donc la seconde position...

Enfin, ça reste seulement une piste et ce n'est surement pas la meilleure solution...

[cyberkamikaz]

euh, les méthodes suivantes sont purement identiques :

... (R)(N)(N)(N)(R) ...
... (R)(N)(N)(N)(R) ...
... (R)(N)(N)(N)(R) ...

Car dès qu'il y a trois ballons identiques alors ils explosent... Je pense que déjà il faut te donner une convention

Moi ce que je voulais dire c'est qu'il y a plusieurses posibilite de poser non comme tu a dit mais

... (N)(R)(N)(N)(R) ...
ou
... (R)(N)(N)(R)(N) ...

[cyberkamikaz]

euh, les méthodes suivantes sont purement

Ensuite, il faut essayer des cas (une bonne feuille et un bon crayons aident beaucoup dans ces moments là...) : est-il nécessaire d'avoir une stratégie orientée? (ie : si je pose le ballon rouge ici et le noir un peu plus tard là-bas alors je vais réussir à faire pêter plus de ballons qu'en essayant de poser d'abord le noir, puis le rouge) Si oui, il faudrait, à mon goût, opter pour une stratégie en arborescence comme pour les échecs. Et donc, établir tous les coups "à blanc" dans une structure arborescente sur, par exemple, 6 placements successifs et prendre uniquement celui (ou ceux?) qui minimisent le nombre de ballons obtenus à la fin de ce combo.

La reponse est oui
Le probleme c'est que je viens de faire les arbres , et je ne les metrise pas bien.Et j'ai pas biens compris comment faire .
Pour l'autre partie j'ai compris.

[pseudocode]

Je vais ecrire quelques exemples :
Car c'est faux
Je me suis mal exprime il fallait dire que toutes les 3 exploses comme dans l'exemple .

Ah. C'est déjà plus clair.

Première remarque, pour avoir une chaine vide il faut un compte total de N et de R divisible par 3. Ca limite les cas a tester.

Deuxieme remarque, comme l'a dit TNT89, l'emplacement est moins important que la sequence. Donc une chaine peut etre vue comme une séquence alternée de N et de R: RRNNRRNRNR -> {2R,2N,2R,1N,1R,1N,1R}.

[cyberkamikaz]

Le probleme est que ca ne se termine pas obligatoirement par une chaine vide.

Il y a une restriction : la somme maximale des ballons dans les deux chaines de caracteres est de 31 (il peux y en avoir moins).

Le probleme c'est qu'il y a beaucoud possibilite de plasser le ballon pris de la chaine d'aprovisionemment alors on n'auras pas le meme numero de pas pour arriver a ce rien (vide) (eliminer tous les ballons de la chaine initiale )
si les ballons de la chaine d'aprovisionemment ne suffises pas il faut retourner toutes le combinaisons minime ordone lexicographiquement .

Pour ca voici l'exemple

in :
(R)(B)

(B)(R)

out

(B)(R)(B)(R)

(B)(R)(R)(B)

(R)(B)(B)(R)

(R)(B)(R)(B)

(R)(R)(B)(B)

[cyberkamikaz]

Ce que j'ai compris En forme d'arbre :

On a la chaine initiale :
(R)(N)(R)(R)
Et la chaine d'approvsionnement :
(R)(N)

Code :

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

1
2
3
4
                                                                   (R)(N)(R)(R)

(R)(R)(N)(R)(R)               (R)(R)(N)(R)(R)          (R)(N)(R)(R)(R)        (R)(N)(R)(R)(R)     (R)(N)(R)(R)(R)

Et on va faire sa recursivememnt jusqu'a ce que on va arriver a une chaine vide ou si la chaine d'aprovisionnemet est vide


on prend encore chaque noeud est on lui ajoute le ballon

Code :

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

1
2
3
4
                                                                           (R)(R)(N)(R)(R)
    
(N)(R)(R)(N)(R)(R)       (R)(N)(R)(N)(R)(R)         (R)(R)(N)(N)(R)(R)       (R)(R)(N)(N)(R)(R)     (R)(R)(N)(R)(N)(R)       (R)(R)(N)(R)(R)(N)

En peux faire ca sans les arbres ?
Un autre TAD ?

[pseudocode]

Code :

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

1
2
3
4
                                                                   (R)(N)(R)(R)

(R)(R)(N)(R)(R)               (R)(R)(N)(R)(R)          (R)(N)(R)(R)(R)        (R)(N)(R)(R)(R)     (R)(N)(R)(R)(R)

Les 2 premiers et les 3 derniers sont équivalent. Ce dont on s'aperçoit si on stocke la chaine ainsi:

{1R,1N,2R}

ajoute R:
cas #1 : {1R+R,1N,2R} = {2R,1N,2R}
cas #2 : {1R,1N,2R+R} = {1R,1N,3R}

Ensuite, je ne pense pas qu'ajouter un N (ou un R) en dehors d'un groupe de N (ou de R) existant soit utile. Par exemple, ajouter un N entre deux R, ou ajouter un N tout seul au début/fin de la chaine, je ne suis pas sûr que ca conduise vers quelque chose d'intéressant.

Je ne suis pas 100% sûr de cela, il faut voir si ca peut se démontrer.

En peux faire ca sans les arbres ?
Un autre TAD ?

Tu peux construire l'arbre dynamiquement en utilisant la récursion. Le langage se charge de stocker sur la pile les parents du noeud actuel. Donc tu n'as besoins que d'un TAD de type Liste.

[cyberkamikaz]

Ensuite, je ne pense pas qu'ajouter un N (ou un R) en dehors d'un groupe de N (ou de R) existant soit utile. Par exemple, ajouter un N entre deux R, ou ajouter un N tout seul au début/fin de la chaine, je ne suis pas sûr que ca conduise vers quelque chose d'intéressant.

Je ne suis pas 100% sûr de cela, il faut voir si ca peut se démontrer.

Le probleme que je peux me trouve oblige de mettre ce ballons quelque part.

Et j'ai pas compris

Tu peux construire l'arbre dynamiquement en utilisant la récursion. Le langage se charge de stocker sur la pile les parents du noeud actuel. Donc tu n'as besoins que d'un TAD de type Liste.

[pseudocode]

Le probleme que je peux me trouve oblige de mettre ce ballons quelque part.

Bon, c'est pas grave. Dans un premier temps, tu peux mettre le nouveau ballon à toutes les positions possibles. Tu verras plus tard pour les optimisations.

Et j'ai pas compris

Le principe de récursion permet de coder seulement une partie de l'algorithme, puis de réappliquer ce code sur le résultat obtenu.

Dans notre cas, il suffit de coder l'algorithme qui consiste a ajouter UN SEUL ballon dans une chaine existante. Cela nous donne une nouvelle chaine. Et on peut réappliquer ce code sur la nouvelle chaine.

[cyberkamikaz]

Ce que j'ai écrit dans une feuille :

Ce que je dois suivre :

on crée un noeud avec un char* code ( ou on va mettre la chaine initiale)
et un vecteur de noeuds (les fils)

on commence par le noeud racine :

while : il existe des ballons dans la chaine d'approvisionnement et on n'est pas arrivé a une chaine vide
{

for i=0:strlen(code)+1 ( un compteur pour passer sur toutes les positions de code )
{

om met dans la position i
si on peut exploser des ballons c'est bien on les explose ( une fonction qui determine si qq chose explose qui vérifiera a chaque fois (code[i-1] et code[i-2]) ou (code[i-1]et code[i+1]) ou (code [i+1] et code[i+2]) )

si oui on explose ce qu'on peut incrementer i=i+2 et on verifie si on peux encore exploser

si non on ajoute le ballon dans la position i
et on met code dans un noeud

}

}

[pseudocode]

Effectivement c'est l'idée de l'algorithme : construire et explorer l'arbre des solutions.

La récursion permet de ne pas réellement construire un arbre en mémoire, mais juste de créer "dynamiquement" les noeuds lors de l'exploration.

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
28
29
30
31
32
33
34
35
 
TestChaine = "RNRR"
TestAppro = "RN"
 
explorer(TestChaine, TestAppro)
 
explorer( chaine, appro ) {
 
	SI (chaine EST VIDE)  {
		/* on a trouvé une solution qui vide la chaine */
		/* inutile de continuer */
		return
	}
 
	SI (appro EST VIDE)  {
		/* plus rien a faire car l'appro est vide */
		return
	}
 
 
	ballon = DEBUT(appro,1)
	nouvelleappro = FIN(appro,1)
 
	POUR i=0 JUSQU'A longueur(chaine) {
		nouvellechaine = DEBUT(chaine,i) + ballon + FIN(chaine,i)
 
		TANTQUE (nouvellechaine CONTIENT "RRR" ou "NNN") {
			nouvellechaine = REMPLACER(nouvellechaine,"RRR","")
			nouvellechaine = REMPLACER(nouvellechaine,"NNN","")
		}
 
		explorer( nouvellechaine, nouvelleappro) 
	}
 
}

[cyberkamikaz]

Merci Beaucoup.
Je vais essayer d'arranger tous dans mon cerveau et une feuille et essayer de coder