Please upgrade your browser for the best possible experience.

Chrome Firefox Internet Explorer
×

Cassetête de la zone héroïque Traken 4 - Balmorra, République

STAR WARS: The Old Republic > Français (French) > Opérations, zones litigieuses, missions héroïques
Cassetête de la zone héroïque Traken 4 - Balmorra, République

Dici's Avatar


Dici
10.10.2012 , 02:16 PM | #1
Pour tous ceux qui ont eu un perso république, je suppose que vous vous souvenez de cette mission de zone qui a dû vous faire perdre un temps monstre. A l'époque, j'avais un peu cogité là-dessus et trouvé une technique de résolution à la main (facilement programmable) systématique et simple. En faisant un reroll, je suis retombé sur cette mission et ça m'a donné enfin de faire un petit interlude "mathématique" pour les rares clampins que ça pourrait intéresser.

La première question que je me suis posé, c'est : pour une situation initiale donnée dont on suppose qu'elle est résoluble, existe-t-il une solution optimale (la plus courte possible) ?

La réponse est oui, pour deux raisons :

- l'opération consistant à changer l'état d'un pylône est une involution (c'est-à-dire qu'en le faisant deux fois on retrouve l'état initial) ; cela est clair si on représente chaque pylône par la la liste non ordonnée des pylônes qui lui sont reliés, et qu'on définit le fait de cliquer sur un pylône par une multiplication par "-1" (un opérateur unaire involutif) de la liste.

- l'ordre des changements ne compte pas ; en effet si vous concaténez deux listes non ordonnées, que vous choisissiez l'une des listes en tête ou l'autre, on obtient toujours la même liste. Il y a donc commutation.

Ainsi toute composition de changement d'état des pylônes peut se ramener à un produit inclus dans L1 o...o L9 où les Li sont les 9 pylônes. Cela signifie que s'il existe une solution, on peut toujours se ramener à une solution en 9 coups maximum... inutile donc de cliquer sans arrêt.


Avec ce résultat intéressant, on aimerait savoir s'il existe toujours une solution. Cette partie est la plus difficile et il faut un peu d'intuition et de tâtonnements pour y arriver. Au final, mon idée a été de composer un "alphabet" de résolution, c'est-à-dire de décomposer le problème en plusieurs problèmes élémentaires (au sens où ils ne peuvent plus être décomposés). Il suffit alors d'aligner les solutions de chacun de ces problèmes.

Cela revient à se demander comment modifier chaque pylône indépendamment des autres. Comme la disposition est symétrique, au lieu de trouver 9 lettres à notre alphabet, il en suffit de 3. Il suffit donc de trouver 3 solutions à autant de problèmes élémentaires, et de se les noter au papier. Le fait que cet alphabet existe implique qu'à partir de n'importe quelle configuration initiale donnée, on peut atteindre n'importe quelle configuration finale donnée. On peut donc avancer une solution en 9 coups au plus dans n'importe quel cas.

En pratique, il faut se dessiner les 3 schémas correspondant aux 3 problèmes élémentaires, on compte alors pour chaque pylône le nombre de modifications qu'on va lui imposer, si c'est pair, on n'y touche pas, sinon on le modifie une fois (conséquence de l'involution). Et voilà... ça n'intéressera personne à part moi je pense mais pas grave !

dreamskid's Avatar


dreamskid
10.11.2012 , 01:18 AM | #2
Je ne trouve pas cela inintéressant mais j'aimerai que tu me rafraichisses la mémoire sur ces 9 pylônes...
Quel était le but final de l'opération?

Dici's Avatar


Dici
10.11.2012 , 04:40 AM | #3
Chacun des 9 pylônes a 2 états : allumé ou éteint. Si on veut représenter harmonieusement le montage, on choisit la forme d'un octogone dont chaque sommet est un pylône, chaque arête une connexion, et le centre est également un pylône relié à quatre sommets deux à deux non consécutifs.

Le but est, à partir d'une configuration quelconque d'états (allumé/éteint) de l'ensemble des pylônes, d'arriver à tous les allumer. Dans le jeu, quand on les allume tous ça alimente une tourelle qui fait feu sur un vaisseau qui se crash, et on doit récupérer quelque chose dessus.

En fait, avec ce que j'ai expliqué, on peut généraliser le problème en imposant d'accéder à partir d'un état quelconque à un autre état quelconque.

PS : je me rends désormais compte qu'on peut généraliser l'alphabet à tout polygone ayant un nombre pair > 4 de sommets (+ le centre où on garde toujours un pylône). Si on considère que ce problème est de taille 2(n+3), alors la résolution se fait en O(n) affectations. Pour 4 sommets l'alphabet n'a que deux lettres.

Malbsenior's Avatar


Malbsenior
10.11.2012 , 09:39 AM | #4
intéressant je n'avais pas vu cette quêtes sous le format arithmétique. Nous l'avons réalisé à deux avec un ami qui s'est foutu de moi parce qu'un électricien d'EDF n'arrivait pas à allumer 9 pylônes ;p

Ce qu'on à fait c'est de chercher le schéma d'extinction de tout les pylônes pour pouvoir les rallumer à notre guise ce qui permet de s'affranchir de la configuration de base. bien que cela paraisse un peu compliquer une fois partie sur tout éteint c'est réellement plus simple de réaliser le schéma électrique dans son ensemble.
Amicalement Malb

Dici's Avatar


Dici
10.11.2012 , 11:05 AM | #5
Quote: Originally Posted by Malbsenior View Post
intéressant je n'avais pas vu cette quêtes sous le format arithmétique. Nous l'avons réalisé à deux avec un ami qui s'est foutu de moi parce qu'un électricien d'EDF n'arrivait pas à allumer 9 pylônes ;p

Ce qu'on à fait c'est de chercher le schéma d'extinction de tout les pylônes pour pouvoir les rallumer à notre guise ce qui permet de s'affranchir de la configuration de base. bien que cela paraisse un peu compliquer une fois partie sur tout éteint c'est réellement plus simple de réaliser le schéma électrique dans son ensemble.
C'est vrai que passer de tout éteint à tout allumé est très simple ! Cela dit atteindre l'état tout éteint est aussi dur à partir d'une situation quelconque que d'atteindre l'état tout allumé.

Malbsenior's Avatar


Malbsenior
10.11.2012 , 01:24 PM | #6
il est vrai qu'on s'est creuser la tête 20 bonnes minutes pour trouvé le schéma pour éteindre tous les pylônes. Mais n'ayant pas réussit à appliquer les conseils glaner sur le net en partant d'un carré de 3X3, il m'a été plus simple de chercher à tout éteindre.
Amicalement Malb

Dici's Avatar


Dici
10.13.2012 , 04:49 PM | #7
J'ai trouvé que ne faire que parler de l'alphabet sans l'expliciter était un peu léger alors le voici :

Problème élémentaire 1 :

Cette notation signifie qu'on veut changer l'état uniquement du pylône noté 1. Les pylônes rouges sont ceux reliés au centre, sauf le centre lui-même. (Les _ ont été utilisés uniquement pour gruger l'éditeur de texte du forum qui ne comprenait pas quand je mettais seulement des espaces entres les caractères.)

___________________0
_________________0___0
_______________1___0___0
_________________0___0
___________________0

Solution élémentaire 1 :


Cette notation signifie qu'on va modifier uniquement les pylônes notés 1 pour atteindre l'état final.

___________________1
_________________0___1
_______________1___0___0
_________________0___1
___________________1

Problème élémentaire 2 :

___________________0
_________________1___0
_______________0___0___0
_________________0___0
___________________0

Solution élémentaire 2 :

___________________0
_________________0___0
_______________0___1___1
_________________0___1
___________________1

Problème élémentaire 3 :

___________________0
_________________0___0
_______________0___1___0
_________________0___0
___________________0

Solution élémentaire 3 :

___________________0
_________________1___1
_______________0___1___0
_________________1___1
___________________0

Vous pouvez vérifier si ça vous chante, ça marche ! Notez que ces 3 problèmes élémentaires permettent de déduire les 6 autres problèmes élémentaires car il n'y a que 3 types de pylônes :
- les pylônes non reliés au centre
- les pylônes reliés au centre sauf le centre
- le centre

L'algorithme de résolution devient alors trivial :

Pour i de 1 à 9 faire
Si pylône(i) = 0 (*c'est-à-dire s'il est éteint, cela est à rentrer par l'utilisateur pour décrire la situation initiale*) alors résoudre_problème_élémentaire(type(pylône(i)) (*on suppose écrites ces fonctions c'est du scribouillage*)
Sinon rien
FIn pour

La fonction type sert à typer le pylône, c'est-à-dire à savoir s'il est le centre, s'il est relié au centre ou s'il n'y est pas relié.

La fonction résoudre_problème_élémentaire va modifier un tableau T (paramètre global) de telle sorte que si le problème élémentaire rencontré exige d'appuyer sur le pylône k, alors T(k) <- (T(k) + 1) mod 2. Cela signifie qu'on compte les changements modulo 2 effectués sur chaque pylône. Pourquoi modulo 2 ? Parce que changer un pylône 2n fois c'est comme ne pas le changer, le changer 2n+1 fois c'est comme le changer une fois.

Au final, le programme renvoit le tableau T rempli de 0 et de 1 qui indiquent à l'utilisateur sur quels pylônes il doit cliquer ou non. J'ai testé ig, et ça marche parfaitement. S'il y a une erreur ici, ça ne serait que de la recopie.

Le plus beau, c'est que j'ai remarqué que cet alphabet était généralisable à n'importe quel nombre impair de pylônes (dont un centre). Comme je l'ai déjà dit, le problème de taille 2n+1 est résolu en complexité O(n) par cet algorithme, il est clair que c'est optimal. Ca n'est probablement pas le seul aglorithme optimal, mais tout de même !

Harkler's Avatar


Harkler
10.14.2012 , 01:00 PM | #8
Ou sinon t'as plus simple

http://www.ueda.info.waseda.ac.jp/~n...out/index.html

tu mets en 2 color, 3x3.

tu clic sur edit, tu met les lumieres comme elles sont actuellement (rouge c'est éteint)
après tu clic sur play, et puis sur solve

ca te donne les tourelles à activer pour gagner ^^

Moins chiant ;p

Kygona's Avatar


Kygona
10.14.2012 , 02:30 PM | #9
Ahah, ce lien circule toujours !

En cliquant sur ce topic et en lisant les premiers messages, j'ai été étonné de pas le voir circuler et voir les personnes proposer diverses solutions assez difficiles à mettre en place comparé au petit lien cité plus haut.

(Ah les souvenirs ... avec une vingtaine de joueurs j'ai du passer 1H à tenter de faire fonctionner ce satané canon à la sortie du jeu... jusqu'à que je tombe sur ce lien miraculeux, ça a pris 2 minutes le temps de savoir à quel canon correspond telle couleur)

Dici's Avatar


Dici
10.14.2012 , 03:37 PM | #10
Quote: Originally Posted by Harkler View Post
Ou sinon t'as plus simple

http://www.ueda.info.waseda.ac.jp/~n...out/index.html

tu mets en 2 color, 3x3.

tu clic sur edit, tu met les lumieres comme elles sont actuellement (rouge c'est éteint)
après tu clic sur play, et puis sur solve

ca te donne les tourelles à activer pour gagner ^^

Moins chiant ;p
Justement mon but c'était de faire ça moi-même !

Je sais pas exactement quel principe utilisent les carrés 3x3 et je m'en moque ; réfléchir moi-même sur ce problème a pas mal enrichi ma vision de l'algorithmique (moi qui n'ai que peu d'expérience) : le fait de décomposer un problème en sous-problèmes élémentaires est exactement ce qu'on demande à un programmeur.

Et au passage, si je traduisais mon programme en php pour le mettre sur internet, il serait tout aussi simple d'utilisation que ton carré 3x3 (il suffit de remplir un tableau 3x3 de 0 et de 1 correspondant aux états des pylônes).