A la FAC on a un projet à faire en C++ d’un jeu (Boggle). Bref pour afficher les dés j’ai juste fait une matrice 4x4. ça donnera une grille 4x4 avec une lettre par case niveau affichage pour le joueur.
Bref la question que je me pose c’est quel procédé utiliser pour retrouver tous les mots que l’on peut faire avec les lettres de cette grille. On ne doit utiliser qu’une fois un dés, les mots peuvent avoir un max de 16 lettres (très peu peu probable mais bon). J’ai bien l’idée alacon qui consiste à prendre toutes les combinaison possible mais bon j’arrive à 20 000 k de possibilités environ pour du 16 lettre sans prendre en compte de fait de devoir prendre une lettre une seule fois. Mais bon si il faut rajouter les autres longueurs se n’est pas top. Surtout que l’on doit vérifier que les mots soient dans le dico.
Sinon il y a aussi la possibilité d’essayer de retrouver les mots du dictionnaires dans la grille en partant du dico. Mais bon il y a 270k de mots dans le dico, ce n’est pas optimal.
Le dictionnaire étant déjà classé par ordre alphabétique j’ai déjà mis un compteur histoire de ne pas avoir à me retaper tout le dico pour la recherche.
Aussi nous n’avons pas le droit de créer plusieurs thread (sinon là se serait intéressant).
Bref la question est : Y-a-t-il u pilote dans l’avion ?
Existe-t-il une méthode plus appropriée à ce genre de problème ??
Edité le 04/04/2010 à 21:31
Ce qui me gene dans ta question, c’est -si je comprends bien- d’obtenir une solution a ton projet.
Vous a-t-on donné des cours de recherche opérationnelle ? Je veux dire, est ce que l’on vous donne un projet à faire “comme ca”, ou est-il associé à des cours magistraux sur le sujet ? Si oui à une des deux questions, c’est qu’il faudrait à priori partir des méthodes proposées par le cours.
La question des thread est hors propos si le but est d’avoir un algo ou plusieurs algos de recherche.
Mon but n’est pas d’avoir un algo mais une méthode de recherche, j’entend par là un processus/méthode pour arriver au résultat. Après je compare les divers solution qui s’offre à moi et passe quelques heures à écrire l’algoritme et le programmer.
Si bien sûr qu’on a eu les cours. On a même le syllabus où il y a quelques algo de marqués. Mais aucun n’est utilisé pour retrouver des mots dans une grille (ce qui n’est pas compliqué à faire donc inutile à marquer), ni en devant comparer avec les mots possibles dans le fichier texte (chargé en mémoire sous forme de tableau) pour voir si la combinaison de lettre est valable ou non.
Bref le truc c’est pour la comparaison avec le dico. Disons que ça pèse dans la balance. Je ne sais pas si je devrais d’abord partir du dico et rechercher chaque mot dans la grille. Ou sinon faire toutes les combinaisons possibles dans la grille et comparer avec le dico. Il me semble que la première solution est plus rapide mais ça reste déjà peu efficace.
Pour finir ce qu’il me plairait se serait quels sont les méthodes applicable (le plus grand nombre possible) à ce gebre de problème. Après je choisirai lequel je vais implémenter.
Hum, les algorithmes que l’on vous présente, ils servent à quoi au juste ? De mémoire, aux cours, on m’en avait présenté -principalement- pour rechercher (graphes, etc etc) et pour trier.
Vous a-t-on présenté des algos de recherche ? Si oui, c’est une solutione est toute trouvée …
Après, de savoir s’il vaut mieux recourir à un dico : à priori oui, sinon comment identifier un mot ?
Pour la problématique de performance plus ou moins évoquée, je pense, personnellement, que la méthode la plus formatrice est de ne te donner aucun conseil d’amélioration. Par contre, une fois que tu auras une solution, ce qui me paraitrait intéressant est d’en mesurer sa complexité en temps et sa complexité en espace (mémoire). Et a partir de ces mesures envisager des actions.
Au feeling, perso je partirai de la grille. Je prend la première lettre, je vérifie qu’il existe un mot dans le dico commençant par cette lettre. Puis pour chaque lettre adjacente, j’ajoute la lettre, je vérifie qu’il existe un mot qui commence par ces deux lettres, et ainsi de suite. En gros tu pars de la méthode bête et méchante qui consiste à tout essayer, mais en vérifiant à chaque fois que cela mêne bien à des choix possibles. Selon la manière dont ton dictionnaire est stocké ça peut être très performant (idéalement, sous la forme d’un arbre)
Ah mince je n'avais pas vu que ce topic était aussi vieux :D
Edité le 05/06/2010 à 16:07
(idéalement, sous la forme d’un arbre)