Jump to content

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


Recommended Posts

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 !

Edited by Dici
Link to comment
Share on other sites

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.

Edited by Dici
Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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é.

Link to comment
Share on other sites

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.
Link to comment
Share on other sites

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 !

Edited by Dici
Link to comment
Share on other sites

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)

Link to comment
Share on other sites

Ou sinon t'as plus simple ;)

 

http://www.ueda.info.waseda.ac.jp/~n-kato/lightsout/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).

Edited by Dici
Link to comment
Share on other sites

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.

Edited by Dici
Link to comment
Share on other sites

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_th%C3%A9or%C3%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%A9or%C3%A8me_des_quatre_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 ... :eek:

Edited by Xhylette
Link to comment
Share on other sites

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.

Edited by Dici
Link to comment
Share on other sites

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.

Link to comment
Share on other sites

  • 3 weeks later...

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 ;)

Link to comment
Share on other sites

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 !

Edited by Dici
Link to comment
Share on other sites

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 !

Edited by Dici
Link to comment
Share on other sites

  • 2 weeks later...

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.

Link to comment
Share on other sites

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.

Edited by elyyn
Link to comment
Share on other sites

Bonjour elyyn,

 

Ton idée a ses avantages, mais en voici les inconvénients.

 

Rappelons l'implantation la plus simple (algorithmiquement) de l'inversion d'une matrice par un ordinateur utilise la formule :

transposée(comatrice(A)) x A = det A * Identité

 

Le calcul de la transposée ne pose pas de soucis. La comatrice en revanche demande de calculer n déterminants d'ordre n-1 si A est carrée d'ordre n. Le calcul d'un déterminant est une somme sur un ensemble à n! éléments, dont chaque terme est un produit à n facteurs. Le calcul d'un déterminant d'ordre n-1 est donc en (n-1)!, le calcul de l'inverse avec cet algorithme est en n x (n-1)! = n!... c'est ENORME !!!

 

Si tu veux inverser une matrice avec une complexité raisonnable, tu introduis un autre problème beaucoup plus complexe que le premier. Certes, il existe des algorithmes faisant ça très bien, mais c'est vraiment utiliser des théorèmes très puissants pour résoudre un problème ridicule (la terminaison d'un certain algorithme d'inversion repose sur la densité des matrices inversibles dans l'ensemble des matrices sur R. Sans être hyper raffiné, c'est largement plus élaboré que mes schémas bêbêtes de résolution).

 

 

Autrement, il est vrai que mathématiquement ta solution est meilleure. La mienne n'a reposé que sur la recherche intuitive d'une "base de solution", tandis que tu rationalises le problème en utilisant des outils classiques. Seulement, ma technique de résolution est faisable à la main car sa complexité est faible, la tienne non. Mon algorithme peut s'implanter informatiquement et s'exécuter en un temps raisonnable, le tien également mais demande un grand raffinement dans la méthode employée, ce qui n'est pas mon cas.

 

Pour conclure je dirais que c'est plus élégant mais un peu inapproprié pour un solveur informatique.

 

PS : gros point pour toi par contre, tu peux généraliser très, très simplement ce problème à tout n et à toute configuration. Ma solution en revanche n'est pas du tout flexible...

 

Quand j'y pense, c'est d'ailleurs l'universalité de ta réponse qui fait que sa complexité est supérieure.

Edited by Dici
Link to comment
Share on other sites

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.

 

Ca c'est quand on n'a pas peur de bouffer de la mémoire pour rien... Je pense quand même que dans de nombreux domaines on cherche l'optimisation algorithmique : depuis quelques années, on peine à augmenter la puissance de calcul. La loi de Moore n'est plus vérifiée, il y a quelques pistes plus ou moins fouillées allant du calcul parallèle (très utilisé) aux ordinateurs quantiques (prémices) mais globalement, on freine.

 

Ainsi, pourquoi, au lieu de rendre les PC plus puissants, ne rendraient-on pas les algorithmes plus intelligents ? Dans ce cas précis l'ensemble des solutions est exponentiel... pas terrible !! (L'ensemble des solutions se construit par exemple comme suit : on choisit toutes les solutions possible impliquant 0 pylône parmi les n totaux, puis 1 pylône parmi n, ..., puis n parmi n. La somme du nombre d'éléments trouvés vaut 2^n)

Edited by Dici
Link to comment
Share on other sites

L'exemple d'un problème simple ayant une solution exponentielle (factorielle) est une bonne idée, mais l'inversion de matrice se fait en n^3 simplement, via la matrice compagnon (méthode de Gauss généralisé), qui n'implique pas de définir un déterminant ;)
Link to comment
Share on other sites

J'ai inversé la matrice parce qu'elle était simple, mais il n'est absolument pas nécessaire de faire une inversion pour trouver la solution. L'inversion ne s'applique qu'au cas d'une solution unique, et monte effectivement rapidement en complexité. De façon plus généralisée, on applique directement le pivot de Gauss sur la matrice de départ, ou encore mieux une décomposition LU, afin de trouver "une" solution si elle existe. Ce sont des algorithmes relativement simples, rapides et faciles à implémenter. (en o(n^3) pour la décomposition LU comme dit au-dessus...) Edited by elyyn
Link to comment
Share on other sites

L'exemple d'un problème simple ayant une solution exponentielle (factorielle) est une bonne idée, mais l'inversion de matrice se fait en n^3 simplement, via la matrice compagnon (méthode de Gauss généralisé), qui n'implique pas de définir un déterminant ;)

 

J'ai inversé la matrice parce qu'elle était simple, mais il n'est absolument pas nécessaire de faire une inversion pour trouver la solution. L'inversion ne s'applique qu'au cas d'une solution unique, et monte effectivement rapidement en complexité. De façon plus généralisée, on applique directement le pivot de Gauss sur la matrice de départ, ou encore mieux une décomposition LU, afin de trouver "une" solution si elle existe. Ce sont des algorithmes relativement simples, rapides et faciles à implémenter.

 

 

Oui j'en ai parlé sans l'évoquer explicitement. Ce que je voulais dire c'est que les algorithmes performants pour l'inversion d'une matrice n'étaient pas vraiment triviaux.

 

Par exemple pour la décomposition LU, si on veut prouver sa terminaison dans "presque tous les cas", il faut savoir prouver la densité des matrices inversibles dans l'ensemble des matrices d'un corps. Nous sommes d'accord, c'est pas non plus d'un niveau incroyable mais c'est quand même moins bateau que mon approche naïve.

 

M'enfin... je m'avoue battu ce que je propose s'étend facile à un nombre beaucoup trop limité de cas : il me faut les mêmes symétries que celles de Traken 4... Je n'avais pas pensé à voir ça comme ça, merci d'avoir élargi l'approche de ce problème !

 

Promis, je sècherai plus les cours d'algèbre pour dormir un peu plus...

Edited by Dici
Link to comment
Share on other sites

×
×
  • Create New...