D’ailleurs ce devrait être au robot de monter les kallax.
1 « J'aime »
C’est bien pour ça que je disais de continuer à le résoudre à la main, ça ira plus vite que d’écrire du code et ça sera tout aussi proche de l’optimal, tout en te permettant d’ajuster selon tes propres obsessions d’orientation, de couleur, de thème…
Sur ceux que j’utilise vraiment très très souvent (pour du calepinage), c’est un nombre d’itérations qui indique l’espace perdu en % (qui va décroissant) : au bout d’un certains nombres d’essais ça ne bouge presque plus. Ce qui me convient parfaitement mais ne présage en rien de la nature optimale de la solution proposée.
Et sinon une option pour juste prendre en photo le nom d’une boîte de jeu et elle s’ajoute toute seule sur une appli genre my Ludo ?
Mais j’aime bien l’idée de l’algorithme associée avec le nombre de nos kallax
Ah et le module associé sur okkazeo pour les sorties et réarrangement direct
Pour affirmer qu’un problème est NP difficile, il faut une preuve formelle (des maths). En informatique théorique, on aime bien ranger les problèmes dans des kalax des classes. Prenons l’exemple du problème du voyageur de commerce : on se donne des villes reliées par des routes et on cherche à trouver un chemin le plus court possible qui passe une fois par chaque ville et revient à son point de départ (un chemin comme ça est une tournée). Ça va me permettre de définir les classes…
- un problème binaire (auquel on répond par oui ou par non) est NP si on peut vérifier la preuve d’une réponse positive en temps polynomial par rapport à sa taille. Dans le cas du voyageur de commerce, un problème binaire classique est le suivant : « existe-t-il une tournée de longueur inférieure à X kilomètres ? » avec X fixé. Une preuve que la réponse est positive est justement de donner une telle tournée. Et il est facile de vérifier que la preuve marche : on calcule les distances entre les villes de la tournée et on en profite pour vérifier que c’est bien une tournée (on passe une fois par chaque ville et on revient à notre ville de départ). Le temps de calcul est proportionnel au nombre de villes, c’est bien polynomial (ici linéaire). Dans la version kalax, le problème binaire est : « existe-t-il un rangement de tous mes jeux dans mes K cases de kalax ? » et c’est clairement vérifiable en temps polynomial ;
- un problème binaire est NP-complet si le fait de savoir le résoudre nous permet de résoudre aussi efficacement tous les problèmes NP. On passe par une réduction polynomiale. Par exemple je me pose la question existe-t-il un rangement de tous mes jeux dans mes K cases de kalax ? ». Comme le voyageur de commerce est NP-complet, je peux construire en un temps polynomial une instance de ce problème s’appuyant sur mes jeux et mes kalax telle que une réponse positive à cette instance implique une réponse positive à la question d’origine. En d’autres termes, je vais prendre mes jeux et mes kalax, et je vais fabriquer à partir de ça des villes artificielles dans un pays imaginaire, avec des distances bien choisies. Tellement bien choisies que si je trouve une tournée de longueur inférieur à un X bien choisi, ça voudra dire qu’il existe un rangement de mes jeux dans mes kalax !
- un problème est NP-difficile s’il est NP-complet sans être lui-même forcément NP
Ça semble encore plus fumé qu’au dessus mais en fait, c’est assez simple. Beaucoup de problèmes intéressants ne sont pas binaires et on ne peut donc pas les ranger dans la classe NP. Par exemple ni le voyageur de commerce ni le bin packing (les kalax) ne sont des problèmes binaires. Ce sont en fait des problèmes d’optimisation car on cherche la meilleure solution possible, pas s’il existe une solution assez bonne (bon, dans le cas des kalax, on est plutôt sur du binaire par moment 
). La tradition en informatique est de transformer un problème d’optimisation en une collection de problèmes binaires, en fixant a priori la qualité de la solution, comme je l’ai fait au dessus. On parle alors du problème de décision associé au problème d’optimisation. Et en général, on se retrouve avec des problèmes de décision NP-complet, et donc mécaniquement à des problèmes d’optimisation NP-difficile (exercice laissé aux lecteurs : pourquoi ?) - enfin, pour les problèmes d’optimisation, on a introduit les classes APX (pour approximation). L’idée est de trouver des garanties sur des solutions approximatives, à un facteur multiplicatif près, par exemple on trouve une tournée de longueur au plus 2 fois la longueur optimale. Les problèmes APX-hard sont bien méchants car on pense qu’ils n’ont pas d’approximation efficace à partir d’un certain ratio. Par exemple le bin packing est gentil dans les problèmes NP-difficile car il possède des approximations efficaces arbitrairement bonnes (il est PTAS). Le voyageur de commerce est plus compliqué : dans un espace euclidien il est PTAS mais dès que ça se complique (avec des « distances » étranges entre les villes), ce n’est plus le cas et il devient même un des problèmes d’optimisation les plus complexes.
Et comment on fait en pratique ? Montrer qu’un problème est NP est généralement facile. Si on coince déjà là dessus, ça commence très mal. Montrer que c’est NP-complet peut sembler impossible : comment faire pour prouver que ça marche dans tous les cas ? L’astuce est que que ça a déjà été fait par Cook et Karp dans les années 70. En gros on a une collection de problèmes dont on sait qu’ils sont NP-complet. Il suffit alors de montrer que l’un de ces problèmes peut être résolu si on sait résoudre le problème qui nous intéresse et bingo, ça s’étend automatiquement à tous les autres. Comme la collection des problèmes NP-complet ne fait que croître, on a pas mal de choix pour se lancer dans une preuve. Ceci dit, ça reste difficile.
Edit : il manque le plus important 
: aujourd’hui, on ne sait pas résoudre efficacement les problèmes NP complets (les algorithmes connus sont exponentiels, autant dire impossible à utiliser pour des problèmes réels) et pour beaucoup de problèmes d’optimisation associés, on doit se contenter de solutions approximatives (parfois excellentes comme pour le bin packing ou le voyageur de commerce).
10 « J'aime »
Mouais, bof. Ça fait d’abord l’hypothèse implicite qu’on serait capable de résoudre les problèmes NP rapidement (edit : avec notre cerveau). En tant que matérialiste, cette hypothèse ne me plaît pas trop. Et surtout, de façon moins « philosophique » beaucoup d’algorithmes d’optimisation avec garanties sont hautement non triviaux et ne peuvent pas être reproduit de tête. Dans ma fac actuelle, on est passé il y a très longtemps (genre 20 ans) à des affectations d’emploi du temps et de salles algorithmiques, et ça a changé notre vie (en bien).
2 « J'aime »
Moi je suis hyper rapide en calcul mental, tu me dis par exemple 13428230 x 423 je te réponds 4325420324 directos. Alors, c’est peut-être faux ; mais c’est super rapide.
11 « J'aime »
Ah ça me rappelle des souvenirs 
Et alors, t’es team P!=NP 
?
Je ne fais pas d’informatique théorique en tant que chercheur, difficile d’avoir une opinion informée sur ce qu’on pourrait trouver un jour. Ceci dit, on a des résultats assez profonds sur les techniques de preuve qui semblent indiquer que certaines d’entre elles ne pourront pas être utilisées pour prouver P=NP. Et beaucoup de théoriciens semblent penser que P!=NP.
1 « J'aime »
Y a que moi… ou ….
2 « J'aime »
J’ai voulu voir d’où ça venait cette connerie, mais c’est trop long à lire, la flemme ><.
Mais je mets un coeur pour l’effort 
.
4 « J'aime »
Oui mais si le commercial est bourré et zigzag sur la route, ça rallonge d’autant la distance. Peut on alors dire que le problème est toujours NP ?
c’est forcément faux, ton résultat ne termine déjà pas par 0. De rien
même des non théoriciens comme moi pensent ça maintenant, surtout depuis que tu viens de l’écrire, c’est pour dire !!
3 « J'aime »
Le triple post, respect. 
Sinon, si je comprends bien… Le projet n’a pas avancé d’un poil de zob? C’est bien ça? Décevant tss 
Sinon moi j’ai rien contre les PNP si ce n’est que c’est du boulot 
Est ce que ce serait pas plus simple de demander de l’aide à un champion de Tetris?
5 « J'aime »
Attends, on va essayer avec kptaingroSTATS.
Ca va peut-être lui raviver la mémoire @Kptaingrostas
2 « J'aime »
Bon ben epic fail pourtant jsuis sur que vous n’avez rien a foutre au taf.
4 « J'aime »
Suivre tous les sujets du forum et y répondre, c’est l’équivalent d’au moins 3 temps plein, je suis entrain de négocier une augmentation.
5 « J'aime »
Non mais on l’a aussi la réponse. C’est 42.
Mais ce qu’on cherche en fait c’est la question !
1 « J'aime »
Tiens, je me suis récemment intéressé à l’API BGG pour faire un truc un peu équivalent (y a pas d’IKEA chez moi donc je ne m’intéresse pas aux Kallax mais j’aimerais faire un truc dans l’idée des Box Thrones et il faut que je calcule de combien d’étagères j’ai besoin).
Bref, j’ai trouvé ces topics qui pourraient vous intéresser :
- GitHub - secnot/rectpack: Python 2D rectangle packing library
- GeekSort: Collection->Shelves sorter | Geek Tools (ça trie même les jeux par couleur !)
- Excel + solver = optimized shelf space (avec Excel pour les gens qui aiment se faire du mal)
3 « J'aime »