View Single Post

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 !