En joue... Feu !

[danyvio]

Je n’ai jamais terminé la démarche infernale du problème suivant, que j’avais relevé il y a … longtemps… :

Le peloton d’exécution est composé de N soldats alignés face au mur, et d’un capitaine.
Le capitaine est placé à gauche du soldat le plus à gauche de la ligne.
A un certain moment, le capitaine donne l’ordre de feu. Alors l’information se transmet de proche en proche jusqu’au moment où l’ordre de feu est exécuté.

Pour cela, chaque soldat est affecté d’un code d’état. Ce code état va de « REPOS » (l’état initial, à « FEU », en passant par un certain nombre d’états intermédiaires.

Le capitaine a deux états : « REPOS » et « FEU ». La différence avec les soldats est que c’est lui-même qui prend l’initiative de passer de REPOS à FEU.

L’état de tous les soldats est évalué simultanément à chaque cycle de calcul.

Le changement d’état d’un soldat ne dépend que de trois paramètres :
• son propre état,
• l’état de son voisin de gauche (qui est un autre soldat ou le capitaine pour le soldat le plus à gauche)
• l’état de son voisin de droite(ou l’absence de soldat pour le soldat le plus à droite).

Autres contraintes rigolotes :

Les soldats ne savent pas compter, et chaque soldat ignore d’ailleurs la composition du peloton.

Les soldats sont identiques et parfaitement interchangeables avant la mise en place du peloton.
Le passage à l’état « FEU » doit être simultané pour tous les soldats.

La question infernale : combien faut-il prévoir, au minimum, d’états en fonction de N ?

Avec un, deux ou trois soldats on arrive facilement à écrire les tables de changement d’états. Au-delà ça se complique…. A vous de jouer !!

[CoucouHibou]

Salut,

Je vois un algorithme avec N+1 états, où les N soldats font feu tous en même temps au bout de N étapes après que le capitaine est passé à l'état feu, mais je suppose qu'on peut faire mieux :

 Cliquez pour afficher

1=REPOS
N+1=FEU

- pour tout 1<p<N+1, chaque soldat à l'état 1 passe à l'état p+1 quand son voisin de droite est à l'état p
- chaque soldat à l'état 1 passe à l'état 2 quand son voisin de droite est à l'état N+1 (le capitaine peut être ledit voisin)
- pour tout 1<k<N+1, chaque soldat passe à l'état k+1 quand il est à l'état k, indépendamment de l'état des voisins
- et pour éviter une erreur de la machine « soldat », tout soldat à l'état N+1 passe à l'état 1

C'est du vite fait, je me trompe probablement, mais c'est tout ce que je vois et je trouve dommage que ce joli problème reste sans réponse... C'est chouette les problèmes d'informatique fondamentale . Merci et à bientôt, cordialement,

Hibou

[ambrosio]

 Cliquez pour afficher

je dirais 2 états, en plus de repos=0 et feu=3
quand le le capitaine décide decommander le feu, il passe
de 0 à 1.
un soldat qui a un 1 à sa gauche et un 0 à sa droite, passe à 1. Le soldat le plus à droite, s'il a un 1 à sa gauche et s'il est dans l'état 0, passe à 2.
un soldat qui a un 2 à sa droite passe à 2, y compris le capitaine.
un soldat qui a un 2 à sa gauche et à sa droite, ou personne à sa droite passe à 3=feu.

[Médiat]

Envoyé par ambrosio

 Cliquez pour afficher

je dirais 2 états, en plus de repos=0 et feu=3
quand le le capitaine décide decommander le feu, il passe
de 0 à 1.
un soldat qui a un 1 à sa gauche et un 0 à sa droite, passe à 1. Le soldat le plus à droite, s'il a un 1 à sa gauche et s'il est dans l'état 0, passe à 2.
un soldat qui a un 2 à sa droite passe à 2, y compris le capitaine.
un soldat qui a un 2 à sa gauche et à sa droite, ou personne à sa droite passe à 3=feu.

Marche pas
Si j'ai bien compris ta solution, une fois les 1 propagés sur la droite on obtient : 1111111....1112 puis 1111111....1122 puis 1111111....1223, et le soldat le plus à droite est le seul à faire feu

[Médiat]

Solution qui nécessite des soldats sachant compter ce qui est contraire à l'énoncé, mais cela peut, peut-être, débroussailler le problème (de plus cette solution utilise un maximum d'états)

 Cliquez pour afficher

Les états du capitaine sont 0 = Repos et -1 (Feu)
Pour les n soldats 0 = Repos, -1 = Feu, et on utilise 2n+1 états

Si un soldat à -1 à sa gauche et 0 à sa droite, il passe à 1
Si un soldat à 0 à sa droite et un nombre positif p à sa gauche, il passe à p+1
Si un soldat n'a rien à sa droite et un nombre positif p à sa gauche, il passe à -(p+1)
Si un soldat n'a rien à sa droite et est égal à p < 0, il passe à (p+1)
Si un soldat a un nombre négatif p à sa droite, il passe à (p+1)

Exemple avec 4 soldats

 0 :  0  0  0  0
-1 :  0  0  0  0
-1 :  1  0  0  0
-1 :  1  2  0  0
-1 :  1  2  3  0
-1 :  1  2  3 -4
-1 :  1  2 -3 -3
-1 :  1 -2 -2 -2
-1 : -1 -1 -1 -1

Et là ils font feu tous ensemble (berk !)

[danyvio]

Envoyé par Médiat

Solution qui nécessite des soldats sachant compter ce qui est contraire à l'énoncé, mais cela peut, peut-être, débroussailler le problème (de plus cette solution utilise un maximum d'états)

 Cliquez pour afficher

Les états du capitaine sont 0 = Repos et -1 (Feu)
Pour les n soldats 0 = Repos, -1 = Feu, et on utilise 2n+1 états

Si un soldat à -1 à sa gauche et 0 à sa droite, il passe à 1
Si un soldat à 0 à sa droite et un nombre positif p à sa gauche, il passe à p+1
Si un soldat n'a rien à sa droite et un nombre positif p à sa gauche, il passe à -(p+1)
Si un soldat n'a rien à sa droite et est égal à p < 0, il passe à (p+1)
Si un soldat a un nombre négatif p à sa droite, il passe à (p+1)

Exemple avec 4 soldats

 0 :  0  0  0  0
-1 :  0  0  0  0
-1 :  1  0  0  0
-1 :  1  2  0  0
-1 :  1  2  3  0
-1 :  1  2  3 -4
-1 :  1  2 -3 -3
-1 :  1 -2 -2 -2
-1 : -1 -1 -1 -1

Et là ils font feu tous ensemble (berk !)

Apparemment, ça ne marche pas avec 2 soldats ni même avec un seul

[Médiat]

Envoyé par danyvio

Apparemment, ça ne marche pas avec 2 soldats ni même avec un seul

Il est vrai qu'avec un seul soldat il y a conflit entre deux règles, il faudrait donc préciser ce cas.
Mais pour deux soldats, voilà ce que cela donne

 Cliquez pour afficher

 0 :  0  0
-1 :  0  0
-1 :  1  0
-1 :  1 -2
-1 : -1 -1

[danyvio]

Envoyé par Médiat

Il est vrai qu'avec un seul soldat il y a conflit entre deux règles, il faudrait donc préciser ce cas.
Mais pour deux soldats, voilà ce que cela donne

 Cliquez pour afficher

 0 :  0  0
-1 :  0  0
-1 :  1  0
-1 :  1 -2
-1 : -1 -1

Pour 2 soldats : OK.
Maintenant, le problème initial était : quel est le nombre minimal d'états, autrement dit, existe t-il des solutions plus complexes en termes de diagrammes, mais avec moins de variables ? Je précise que je n'ai pas la solution.... Mais ton approche est très sympa !

[ambrosio]

en y repensant avant de m'endormir j'ai compris que ma solution était fausse (il y a plus intéresant à faire au lit que penser aux énigmes de fs, mais bon, au moins je n'ai pas rêvé qu'on me fusillait). J'ai trouvé une autre solution, que je ne détaille pas, mais il faut beaucoup d'états puisque quelqu'un (le capitaine) doit compter les soldats. Comme le nombre de soldats est indéterminé, il doit avoir une mémoire de taille infinie et ça n'est pas très réaliste.

[yat]

Envoyé par danyvio

Pour 2 soldats : OK.
Maintenant, le problème initial était : quel est le nombre minimal d'états, autrement dit, existe t-il des solutions plus complexes en termes de diagrammes, mais avec moins de variables ? Je précise que je n'ai pas la solution.... Mais ton approche est très sympa !

Si le but est d'avoir moins de variables (donc d'états différents, je suppose), alors j'ai une meilleure solution, en N+2 états :

 Cliquez pour afficher

Les états sont -2 (repos), -1 (feu), et 0 à N-1.

Un soldat à l'état -2 y reste tant que son voisin de gauche passe dans un état différent de -2. Quand son voisin de gauche passe à l'état X, il se met dans l'état X+1. Dans ce dernier cas, si le soldat n'a pas de voisin de droite, il passe directement à l'état X.

Un soldat dans un état positif X y reste tant que son voisin de droite est dans l'état -2 ou X+1. Si l'état de son voisin de droite devient X ou qu'il n'a pas de voisin de droite, il passe à l'état X-1.

Exemples :

-2 -2
-1 -2
-1 -1

-2 -2 -2
-1 -2 -2
-1  0 -2
-1  0  0
-1 -1 -1

-2 -2 -2 -2 -2 -2 -2 -2
-1 -2 -2 -2 -2 -2 -2 -2
-1  0 -2 -2 -2 -2 -2 -2
-1  0  1 -2 -2 -2 -2 -2
-1  0  1  2 -2 -2 -2 -2
-1  0  1  2  3 -2 -2 -2
-1  0  1  2  3  4 -2 -2
-1  0  1  2  3  4  5 -2
-1  0  1  2  3  4  5  5
-1  0  1  2  3  4  4  4
-1  0  1  2  3  3  3  3
-1  0  1  2  2  2  2  2
-1  0  1  1  1  1  1  1
-1  0  0  0  0  0  0  0
-1 -1 -1 -1 -1 -1 -1 -1

[CoucouHibou]

Bonjour,

après avoir regardé à tête plus reposée, je crois que ma solution n'est pas si mauvaise, mais par contre je me pose la question : qu'entends-tu par la contrainte « les soldats ne savent pas compter » ?

Parce que là, on numérote ce que l'on définit comme états, mais on pourrait très bien imaginer que ces états sont des postures ou des paroles dites, des gestes etc... et alors plus besoin pour le soldat de savoir compter, mais de savoir faire ce qu'il faut quand il faut (normal pour un soldat non ?).

Cordialement,

Hibou

[yat]

L'énoncé dit "Les soldats ne savent pas compter, et chaque soldat ignore d’ailleurs la composition du peloton.".

Pour moi ça veut dire que les soldats ne savent pas combien ils sont dans le peloton. Si c'est le cas, ta solution ne convient pas, et quoi qu'il arrive, il faut que l'information fasse un aller-retour, ce qui élimine toute solution de l'ordre de N étapes.

[CoucouHibou]

Pour moi ça veut dire que les soldats ne savent pas combien ils sont dans le peloton. Si c'est le cas, ta solution ne convient pas, et quoi qu'il arrive, il faut que l'information fasse un aller-retour, ce qui élimine toute solution de l'ordre de N étapes.

Dans la solution que je propose, chaque soldat ne fait attention qu'à lui même, et éventuellement ses voisins. Donc il n'a pas besoin de savoir la composition du peloton. J'ai compris l'énoncé comme étant : « comment un opérateur extérieur peut-il configurer, par p états et une série de règles de passages d'un état à l'autre, un soldat d'un peloton de N soldats identiques à lui (i.e. qui ont les mêmes ordres) pour que tout le peloton arrive dans le même état à un moment donné ». Je ne compte pas le capitaine dans le peloton, alors c'est peut-être là que je me trompe, mais bon... Prenons un exemple avec 5 soldats.

 Cliquez pour afficher

Chaque soldat reçoit la série d'ordre suivant :

début des ordres

Tu as le droit d'être dans 6 états : REPOS, GA, BU, ZO, MEU et FEU.

Si tu es a REPOS

Si ton voisin de droite est à FEU, passe à GA

Si ton voisin de droite est à GA, passe à BU

Si ton voisin de droite est à BU, passe à ZO

Si ton voisin de droite est à ZO, passe à MEU

Si ton voisin de droite est à MEU, passe à FEU

Sinon,

Si tu es à GA, passe à BU

Si tu es à BU, passe à ZO

Si tu es à ZO, passe à MEU

Si tu es à MEU, passe à FEU

Si tu es à FEU, passe à REPOS.

Fin des ordres

Ainsi on a la série d'étapes suivantes :

initiale :
cap. : FEU
sol. 1 à 5 : REPOS

étape 1
cap. : FEU
sol. 1 : GA
sol. 2 à 5 : REPOS

étape 2
cap. : FEU
sol. 1 et 2 : BU
sol. 3 à 5 : REPOS

étape 3
cap. : FEU
sol. 1 à 3 : ZO
sol. 4 et 5 : REPOS

etc...

On arrive bien à tout le monde à FEU pour l'étape 5, de tels soldats ne savent pas forcément compter, ne connaissent pas forcément la composition du peloton, et sont interchangeables non ?

Cordialement,

Hibou

[Médiat]

CoucouHibou >> si j'applique ta règle avec 6 soldats et non 5, les 5 premiers sont à FEU alors que le dernier est à R.

La difficulté vient de ce qu'il faut une règle qui marche quel que soit le nombre de soldats (d'où l'aller-retour évoqué par yat).
Sinon, pour 5 soldats il existe une solution avec 2 états supplémentaires et non 4.

[yat]

Envoyé par CoucouHibou

Dans la solution que je propose, chaque soldat ne fait attention qu'à lui même, et éventuellement ses voisins. Donc il n'a pas besoin de savoir la composition du peloton.

Si : il a besoin de savoir le nombre de shadoks du peloton. Ou plus précisément, l'automate qu'il doit suivre est construit en fonction du nombre de soldats. On ne peut donc pas prendre les soldats d'un peloton de 5 et les mettre dans un peloton de 10 et leur faire appliquer le même algorithme. Ca ne marchera pas : les 5 premiers vont tirer à la cinquième étape, alors que les deux autres seront encore au repos.

Edit : croisement avec Médiat

[CoucouHibou]

Envoyé par Médiat

La difficulté vient de ce qu'il faut une règle qui marche quel que soit le nombre de soldats.

Ce n'est pas clairement spécifié dans l'énoncé donné par danyvio ! Enfin, après recherche, j'ai en effet vu qu'il faut prendre cela en compte dans le problème du firing squad.

Mais bon, je crois que la réponse n'est pas triviale, jugez plutôt :

http://mathworld.wolfram.com/FiringSquadProblem.html

Résultat : 2n+1 étapes et 6 états... Un programme en COQ ici : http://coq.inria.fr/contribs/firing-squad.html

Bonne fin de soirée, cordialement,

Hibou

[yat]

Envoyé par CoucouHibou

Ce n'est pas clairement spécifié dans l'énoncé donné par danyvio

Mais si ! "Les soldats ne savent pas compter, et chaque soldat ignore d’ailleurs la composition du peloton."...

Si les soldats ne savent pas combien ils sont dans le peloton, l'automate doit pouvoir se passer de cette information...

Envoyé par CoucouHibou

Mais bon, je crois que la réponse n'est pas triviale, jugez plutôt :

http://mathworld.wolfram.com/FiringSquadProblem.html

Résultat : 2n+1 étapes et 6 états... Un programme en COQ ici : http://coq.inria.fr/contribs/firing-squad.html

Voilà qui donne une toute autre dimension au problème Et de quoi cogiter encore pendant un petit moment.

[CoucouHibou]

Bonjour,

Une autre solution, assez jolie graphiquement mais moins performante :

http://www.cs.hmc.edu/~hadas/firing_squad/continue.html

23 états, 3n étapes.

La solution de Mazoyer est peut-être la solution optimale puisqu'elle est en 2n étapes (aller-retour du signal) et qu'il a aussi démontré que c'était impossible de trouver une solution avec 4 états.

Allez, qui trouve une solution intermédiaire entre les 23 états et les 6 états ? Voire en 5 ? (Mais là je suppose qu'il y a un papier à la clef, et que dans ce cas, la solution ne sera pas exposée ici avant sa parution )

Cordialement,

Hibou