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.14.2012 , 03:43 PM | #11
Quote: Originally Posted by Kygona View Post
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)
Le lien qui circule n'est pas une solution, c'est un solveur c'est différent ! C'est comme de dire qu'un mathématicien est une preuve, non, le mathématicien ne fait que trouver et fournir la preuve tout comme le solveur fournit la solution et quels raisonnements avaient permis d'y aboutir.

Ce topic, en revanche, propose un principe de résolution qui peut mener à la réalisation d'un solveur (je l'ai fait c'est la partie la plus simple). Ca s'adressait aux gens qui auraient pu se demander comment un tel solveur pouvait éventuellement fonctionner.

Xhylette's Avatar


Xhylette
10.15.2012 , 02:49 AM | #12
Quote: Originally Posted by Dici View Post
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.
Bonjour Dici !

S'il existe au moins une solution, il existe au moins une solution optimale, oui. Cependant ton argumentation ne démontre pas l'existence de la solution ; elle existe certainement, sinon Bioware ne proposerait pas l'énigme, mais autre chose est de le démontrer sans l'avoir trouvée.

Le fait qu'on puisse exécuter des actions inutiles (changer l'état d'un pylône puis de suite le remettre en l'état) démontre que certaines solutions sont plus longues que d'autres ; il y en a donc une (ou plusieurs ...) qui sont les plus courtes, donc optimales, oui.


Par contre, ton deuxième raisonnement m'échappe complètement. Tu dis "concaténer deux listes" ; veux tu dire par là ajouter deux solutions à la suite de l'autre ? La queue de la première liste d'actions soudée à la tête de la deuxième liste d'actions ? Cela reviendrait à dire qu'une seule action (laquelle ?) permettrait de passer de l'état de solution (l'état final) à l'état de problème (l'état initial). Cela me laisse vraiment perplexe. J'aimerais que tu développes davantage.

Il faut aussi garder présent à l'esprit que s'il n'existe qu'un seul état final, lorsque la solution est trouvée, il existe de nombreux états initiaux, lorsque le problème est posé.

Comme je te l'ai dit, je compte me replonger sur ce casse-tête, mais pas nécessairement tout de suite.

Bon jeu à toi.

NB. Il existe bien des problèmes mathématiques de ce genre, dont certains sont devenus particulièrement célèbres. Toute la beauté du casse-tête réside dans le contraste entre la simplicité enfantine de l'exposé du problème, et l'indescriptible complexité de sa solution.

Parfois certains ont mis des années ou des siècles à être découverts comme

- le théorème de Fermat (3² + 4² = 5², mais il n'existe pas d'autre cas semblable quelque soit l'exposant s'il est différent de 2) ; tout le monde a pu se convaincre que jamais on ne trouvera trois nombres a, b c tels que a³ + b³ = c³, mais il faudra 350 ans pour qu'enfin quelqu'un arrive à l'expliquer :
--> http://fr.wikipedia.org/wiki/Dernier...A8me_de_Fermat

- le théorème des quatre couleurs (quatre couleurs suffisent à colorer une carte de géographie plane sans que deux pays de même couleur ne se touchent à leur frontière) ; ce théorème est compréhensible pour un enfant de cinq ans à qui vous donnez quatre crayons de couleurs et une carte à colorier ; offrez lui une récompense s'il parvient à la colorer correctement ; ce n'est pas bien difficile. Mais quand il s'agit de comprendre pourquoi c'est toujours quatre et pas trois ou cinq couleurs, là, croyez moi, c'est vraiment, mais vraiment tout autre chose :
--> http://fr.wikipedia.org/wiki/Th%C3%A...uatre_couleurs

Le problème de Traken est peut-être de ce type ; il faut peut-être de nombreux calculs pour le résoudre. Mais il est tout aussi possible qu'il existe une solution subtile, toute simple, visible comme le nez au milieu de la figure ; la difficulté est de cacher le reste de la figure pour faire apparaitre clairement le nez ...
"Qu'importe la destination, seul compte le voyage."

Dici's Avatar


Dici
10.15.2012 , 04:46 AM | #13
Je suis désolé pour la longueur j'ai édité 15 fois pour raccourcir mais j'aimerais être compris ! Dans le pire des cas je peux fournir le programme en Pascal et tu pourras tester en jeu (oui je sais c'est vieux mais on m'a appris que ça en prépa !).

Tout d'abord merci d'être passé Xhylette, les politesses étant rendues je vais éclaircir quelques points !

Premièrement la partie que tu as citée avait pour seul but de prouver que si la solution existe (et je me demande si la solution existe car rien ne dit que le jeu, lorsqu'il réinitialise l'énigme, ne choisit pas exprès une configuration soluble parmi d'autres non solubles) alors on peut la raccourcir à moins de 9 coups.

Pour cela je définis en quelques sortes 9 fonctions : F1 ... F9. Utiliser F1 consiste à appuyer sur le pylône numéroté 1 etc, et cela modifie tous les pylônes reliés. Mon argumentation réside en deux points :

- pour tout i, Fi o Fi = id où "o" est le signe de la composition et id est la fonction identité
- pour tout i et tout j, Fi o Fj = Fj o Fi (c'est là que je parle de concaténation de deux listes non ordonnées, j'avais choisi comme structure des listes non ordonnées de pylônes pour représenter un pylône, oublie ça même si je trouvais ce choix astucieux, car si ce résultat est simple à comprendre, il faut pouvoir l'amener rigoureusement)

Ces deux arguments suffisent à dire que pour toute solution, on peut se ramener à neuf coups au pire.
Par exemple : F1 o F2 o F1 o F5 o F7 = F1 o F1 o F2 o F5 o F7 = F2 o F5 o F7

Pour prouver que je pouvais toujours faire cela, il me fallait l'involutivité des Fi ainsi que leur commutativité par rapport à la composition. Avec ça, j'ai juste donné la preuve qu'il ne sert à rien de s'affoler sur les boutons et qu'on doit cliquer maximum une fois sur chaque pylône.


Maintenant, l'existence. Je n'aurais pas dû te presser parce que du coup tu n'a spas tout lu ! Si tu te reportes à mon post de la première page où il y a des tas de schémas, j'y donne la solution explicite du problème ; c'est bien une solution que j'expose pas une réflexion inaboutie.

L'idée c'est que je regarde quels pylônes sont éteints, et je vais m'arranger pour les allumer un par un sans modifier le reste du circuit.

Pour faire ça, il suffit de voir qu'il y a 3 types de pylônes (reliés au centre, non reliés au centre, centre). Dès lors, on cherche :

- 1 /comment allumer le centre sans changer l'état des autres (il y a des étapes intermédiaires durant lesquels les autres pylônes vont changer mais au bout du compte on retrouvera les mêmes états sauf le centre, qui sera allumé plutôt qu'éteint)
- 2/ comment allumer un pylône relié au centre sans changer les autres
- 3/ comment allumer un pylône non relié au centre sans changer les autres

Il suffit alors d'utiliser les symétries du montage et un peu d'intuition pour trouver :

1/ il faut cliquer sur le centre et sur tous les pylônes reliés au centre. Au final, seul le centre a changé d'état.

2/ Il faut cliquer sur tous les pylônes sauf le pylône à allumer, les deux premiers pylônes à sa droite, les deux premiers pylônes à sa gauche. Au final, seul le pylône à allumer a changé d'état.

3/ il faut modifier tous les pylônes sauf le centre, le premier pylône à droite du pylône à allumer et le pylône. Au final, seul le pylône à allumer a changé d'état.

Tu peux tester au papier, ça marche. Ensuite, tu comptes pour chaque pylône le nombre de fois que tu devras cliquer, si c'est impair tu cliqueras une seule fois, sinon tu ne cliqueras pas du tout.
Cette décomposition en 3 sous-problèmes montre aussi que toutes les configuration imaginables sont accessibles depuis n'importe quelle autre puisqu'on peut séquentiellement éteindre un pylône sans modifier les autres.

------------------------------------------------------------------------------------------------------------------------------------------------------

PPS : pour la complexité ce calculs, je te rassure tout de suite ce problème n'est pas du tout encombrant. En fait, il est même très léger puisque cette solution le résout avec une complexité O(n)... C'est plus court que le plus court des algorithmes de tri d'un tableau d'entiers.
C'est parce que le tableau est totalement aléatoire et n'a aucune propriété tandis que dans le cas de Traken, le montage dispose de qualités intrinsèques que j'ai utilisées pour réussir à allumer un pylône donné sans modifier les autres au bout du compte.

Xhylette's Avatar


Xhylette
10.15.2012 , 05:29 AM | #14
Je te promets d'étudier tout cela, mais à mon aise, Dici !
"Qu'importe la destination, seul compte le voyage."

Dici's Avatar


Dici
10.15.2012 , 05:40 AM | #15
Je ne vais plus te presser ! J'ai toujours embêté mon entourage après avoir résolu quelque chose qui m'avait intéressé... maintenant que mon entourage se compose de gens qui me verraient en extraterrestre s'ils savaient que ça m'intéressait, je dois compenser d'une façon ou d'une autre !

Prends ton temps, bonne journée.

Hovergame's Avatar


Hovergame
11.02.2012 , 07:10 PM | #16
Mathématiquement, ce problème est du même acabit que le Rubik's Cube, en plus simple. Ces 2 problèmes se situent dans une domaine encore plus vaste : soit G un groupe fini dont on donne les générateur et g un de ses éléments; donner l'inverse de g en fonction des générateurs du groupe.

Parlons un peu math et algorithmique
Le fait qu'on puisse allumer chaque pylône indépendamment prouve qu'il y a 2^9 positions distinctes. en regardant le problème sous forme d'un groupe, omme tout élément est d'ordre 2 et commutatif, tu prouves qu'il existe des positions qui demandent au moins 9 mouvements.Tu prouves aussi l'unicité (à permutation des éléments prêts) de la solution (comme la décomposition en nombres premiers).

Question algorithmique, non tu n'es pas en O(n) à moins que tu ne me prouve que modifier un unique pylône est en O(1), et ça ne me semble pas le cas (au pifomètre, ça me semble du O(n), donc ton algo est en O(n²)).

Au final, ta solution est optimale mathématiquement (par unicité à permutation près et parle fait que tu n'as pas de répétitions), mais l'algorithme n'est sûrement pas en complexité optimale (ça reste à montrer, et c'est trop difficile ppur moi). Et de plus, déjà en 5x5, il existe des positions sans solutions (et le nombre de cas de base n'est plus 3 mais 6), donc je doute que ton approche se généralise

Dici's Avatar


Dici
11.03.2012 , 12:30 PM | #17
Quote: Originally Posted by Hovergame View Post
Mathématiquement, ce problème est du même acabit que le Rubik's Cube, en plus simple. Ces 2 problèmes se situent dans une domaine encore plus vaste : soit G un groupe fini dont on donne les générateur et g un de ses éléments; donner l'inverse de g en fonction des générateurs du groupe.

Parlons un peu math et algorithmique
Le fait qu'on puisse allumer chaque pylône indépendamment prouve qu'il y a 2^9 positions distinctes. en regardant le problème sous forme d'un groupe, omme tout élément est d'ordre 2 et commutatif, tu prouves qu'il existe des positions qui demandent au moins 9 mouvements.Tu prouves aussi l'unicité (à permutation des éléments prêts) de la solution (comme la décomposition en nombres premiers).

Question algorithmique, non tu n'es pas en O(n) à moins que tu ne me prouve que modifier un unique pylône est en O(1), et ça ne me semble pas le cas (au pifomètre, ça me semble du O(n), donc ton algo est en O(n²)).
Tu as raison je crois que je me suis un peu avancé car je n'ai programmé que le problème à 9 pylônes et je n'ai fait que voir que je savais généraliser sans regarder plus loin.

Je me disais, pour chaque type position de pylône que je dois commuter isolément des autres, j'effectue un nombre fixé d'opérations par pylône. Vu comme ça, ça fait penser à du O(n)... sauf que pas du tout car en fait les solutions élémentaires ont une longueur qui dépend de n.

Tu as donc vu juste, on est en O(n²), il est certain que ce n'est pas le pire algorithme vu que le problème est de taille exponentielle (2^n), mais il est très probable qu'il ne s'agisse effectivement pas du meilleur. Totalement sans justification, j'aurais tendance à penser que ça ne peut pas être plus rapide qu'un tri... mais bon je répète ça n'est pas du tout certain.

Merci d'avoir calmé mes ardeurs, je suis quand même satisfait de mon algo et même si j'en doute, si quelqu'un connaît une solution avec une complexité inférieure ou un minorant de la complexité (justifié) je veux bien m'y intéresser !

Dici's Avatar


Dici
11.03.2012 , 12:57 PM | #18
Quote: Originally Posted by Hovergame View Post
Et de plus, déjà en 5x5, il existe des positions sans solutions (et le nombre de cas de base n'est plus 3 mais 6), donc je doute que ton approche se généralise
Là par contre je proteste, peut-être à tort, peut-être pas.

On ne parle peut-être pas du même problème en fait, je m'explique : le fait de parler de problème n x n prouve que ça ne correspond pas à ce dont je parle... A vrai dire, je parlais de généraliser aux problèmes 2n+1.

Je veux dire par là qu'on prend un cercle, et on place 2n points sur son contour. Si on veut que ça soit joli, autant les confondre avec les racines 2n-ieme de l'unité mais c'est accessoire ! Ensuite, en commençant par n'importe quel point, on en relie un sur deux au centre, qui est le 2n+1-ieme point du problème. Ca explique aussi que les 3 cas de base restent les mêmes (centre, relié au centre, non relié au centre).

En fait je ne sais pas trop en quoi consistent ces histoires de carrés n x n mais une chose est certaine à mes yeux, la correspondance du cas 3x3 avec le problème 2n+1 (n=1) dont je parle est une exception, ainsi le problème 5x5 ne correspond pas à mon avis à mon problème 2n+1 (n=12). Autrement, comment on résoudrait le problème "17" avec un carré ?

Donc voilà, le carré 3x3 peut être utilisé pour Traken mais le 5x5 ne pourrait pas l'être sur un circuit identique à celui de Traken avec juste plus de points sur le "cercle".

Ceci dit tu m'as fait vérifier un truc et j'ai trouvé une autre erreur dans ce que j'avais dit.
En 4n+3, il n'est pas possible de généraliser facilement la règle d'allumage isolé du centre.
En 4n+1, ça marche toujours... cela tient au fait qu'on doit avoir un nombre pair de pylônes reliés au centre pour que ça fonctionne, puisque pour allumer tout seul le centre j'ai commuté tous les pylônes qui lui sont reliés, et lui-même. S'il est relié à un nombre impair de pylônes on commute donc le centre un nombre pair de fois et ça ne remplit pas l'objectif.


Je suis content que tu sois venu me contredire, j'ai trop souvent tendance à me lâcher et balancer des choses à l'intuition sans vérifier quand je viens de trouver quelque chose qui marche. Par contre, maintenant je suis à peu près sûr de moi, avec un petit schéma ça paraît bon !

xxBeebeexx's Avatar


xxBeebeexx
11.16.2012 , 08:20 AM | #19
Tout cela est très académique et c'est tant mieux.
Juste, heu, je ne sais pas si solvable ne serait pas mieux que résoluble.
Et les solveurs informatiques ne sont pas toujours des fins matheux mais exploitent plutôt la vitesse des processeurs pour tester bêtement toutes les solutions.

elyyn's Avatar


elyyn
11.23.2012 , 09:21 AM | #20
Vous vous prenez bien la tête... Le problème se ramène à un système d'équations linéaires sur F2 qui est un corps commutatif, donc on peut le traiter matriciellement, sous la forme A.X=B avec A une matrice 9x9 sur F2, X le vecteur inconnu des clics à effectuer, et B le vecteur connu des pylônes déjà allumés.

Soit les pylônes P1 à P9 représentés graphiquement par
(P1, P2, P3)
(P4, P5, P6)
(P7, P8, P9)

et qu'on utilisera ici sous la forme d'un vecteur P=t(P1, P2, P3, P4, P5, P6, P7, P8, P9)
P sert de modèle pour définir X et B.

On définit donc:
A=
(1,1,0,1,0,0,0,0,0)
(1,1,1,0,1,0,0,0,0)
(0,1,1,0,0,1,0,0,0)
(1,0,0,1,1,0,1,0,0)
(0,1,0,1,1,1,0,1,0)
(0,0,1,0,1,1,0,0,1)
(0,0,0,1,0,0,1,1,0)
(0,0,0,0,1,0,1,1,1)
(0,0,0,0,0,1,0,1,1)

Remarque: Chaque colonne représente les pylônes qui changent d'état quand on clique sur le nième pylône, où n est l'indice de la colonne.

On voit que la matrice est inversible par blocs (je vous épargne le petit calcul...); le système a donc une solution unique, et on obtient:
A^-1=
(1,0,1,0,0,1,1,1,0)
(0,0,0,0,1,0,1,1,1)
(1,0,1,1,0,0,0,1,1)
(0,0,1,0,1,1,0,0,1)
(0,1,0,1,1,1,0,1,0)
(1,0,0,1,1,0,1,0,0)
(1,1,0,0,0,1,1,0,1)
(1,1,1,0,1,0,0,0,0)
(0,1,1,1,0,0,1,0,1)

De sorte que A^-1.B=X
Chaque colonne de A^-1 représente les pylônes à cliquer pour inverser uniquement la lumière du nième pylône où n est l'indice de la colonne. Pour obtenir la solution pour un jeu de lumières donné, il suffit d'additionner les colonnes correspondantes modulo 2.