Mercredi prochain, je donnerai une conférence au séminaire "mathématiques et société" intitulée « Un jeu sur smartphones pour expliquer les méta-heuristiques».

Mercredi 15 octobre 2014 à 16h15
Auditoire Louis-Guillaume, ALG, F 200
Rue Emile-Argand 11
2000 Neuchâtel

Le séminaire est ouvert au public. A mercredi ?

Résumé
Il existe des problèmes d'optimisation pour lesquels il est difficile de trouver un optimum global, car il y a trop de possibilités pour les tester toutes dans un temps raisonnable. Alors comment faire ? Dans cet exposé, on présentera quelques techniques d'optimisation, appelées "méta-heuristiques", appliquées à un des jeux pour smartphones les plus téléchargés en 2013 : "Ruzzle". Dans ce jeu, il s'agit de former le plus de mots possibles avec les seize lettres disponibles dans une grille de quatre par quatre. Les mots peuvent être composés d'au moins deux lettres, et être formés en utilisant des lettres adjacentes les unes aux autres sans réutiliser deux fois la même case de la grille. Le problème d'optimisation est le suivant : quelle est la grille qui contient le plus de mots français ? Cinq techniques seront proposées et comparées pour trouver une bonne solution : le hasard pur, la descente de plus grande pente, la méthode taboue, le recuit simulé et un algorithme génétique.

Pour en savoir plus, vous trouverez mon article sur le sujet à la page :
www.nymphomath.ch/info/algo/corriges/ruzzle/