View Single Post

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