Reprise du message précédent :

 
Oui et non. Vu l'explosion combinatoire, une stratégie exhaustive (i.e "force brute" ) n'est pas réaliste. Pour simplifier, ne considère qu'une minuscule grille 7×7 que l'algo devrait remplir sans case noire: il doit donc trouver un certain arrangement "gagnant" de 14 mots (7 horiz + 7 vertic) puisés dans un ensemble de 50.000 mots env. (les mots de 7 lettres, c'est un ordre de grandeur).
Je résume: le loto c'est 7 boules sur 49, là c'est 14 mots sur 50.000, et ordonnés en plus! Je vous dispense d'une estimation...
 
Moralité: la difficulté de cet algo n'est pas de trouver comment cracher très vite toutes les possibilités (c'est pas jouable), mais d'arriver à optimiser des stratégies d'accélération dans la recherche, éliminer rapidement des voies de garage, etc., c'est ce que fait le concepteur humain de grilles!
 
Alors, le hasard, ouais, c'est une manière comme une autre d'élaguer les branches, mais je ne pense pas que le hasard soit une stratégie optimale. La stratégie c'est de l'injecter au bon moment si besoin.
 
NB. - En fait, la grille admet en entrée un paramétrage tel que l'utilisateur remplit, par exemple, la première ligne et la première colonne de la matrice. L'algo doit alors finir le boulot. Avec ce type de contrainte initiale, tu n'auras jamais deux fois la même grille si tu la "charges" différemment, y compris si l'algorithme est déterministe.

Une approche possible: pour tous les mots de 7 lettres (par exemple) compter le nombre de mots qui commencent par une combinaison de 2 lettres : aa, ab,ac...,zz. Ceci pour chaque combinaison possible.
Puis choisir arbitrairement le premier mot horizontal ensuite pour choisir le deuxieme mot horizontal essayer tous les mots de 7 lettres et choisir par exemple celui qui donne le plus grand nombre quand on multiplie les 7 nombres correspondant au nombre de mots possibles pour les 7 mots verticaux. Refaire pareil ensuite pour le troisieme mot horizontal en calculant les combinaisons pour les trois premieres lettres aaa...zzz. Si on tombe sur 0 revenir en arriere et prendre le mot suivant qui donne le plus grand nombre. L'idee qui est peut etre fausse d'ailleurs est de maximiser la probabilite de finir sa grille et de prendre en compte les proprietes des mots quant a l'agencement des lettres.
 

Dal elg, je viens de relire 3 fois posément ton algo, c'est pas de la mauvaise volonté, je ne bite absolument rien. Est-ce que tu peux vulgariser (à 35°C, les neurones faut les aider un peu!)
 
Merci.

 
Soit j'ai pas compris l'algo proposé, soit je vois pas où il veut en venir...

Oui je reconnais que c'est pas tres clair. Bon je reessaye.
D'abord on choisit arbitrairement le premier mot de 7 lettres  
et on le place a la premiere ligne. Ensuite pour choisir  
le deuxieme mot a placer sur la deuxieme ligne on essaye  
de trouver un mot tel que les debuts des 7 mots verticaux  
va offrir le plus de possibilites. Par exemple si le premier mot
horizontal est du genre SA..... tu vas pas choisir comme  
deuxieme mot horizontal un mot du genre ZA..... car il va alors  
te falloir trouver verticalement un mot qui commence par SZ...  
et le suivant verticalement par AA ce qui est improbable.
D'ou l'idee de calculer combien de mot y a t'il qui commencent
par AA, AB,AC,AD....ZW,ZX,ZY,ZZ. On choisira donc le second mot  
horizontal de telle facon qu'il offre le plus de mots possible  
comme choix pour les 7 mots verticaux. La question est  
de choisir le critere correctement. En premiere idee je pensais  
multiplier les 7 nombres de telle facon qui si il y a un 0  
le nombre  final est 0 signifiant qu'il est impossible de completer
la grille.

 
ok, je penses avoir compris. Du reste, ça me fait penser à qq chose. Il serait peut-être intéressant de travailler sur les mots, je veux dire par là définir des relations entre les mots du dictionnaire. Pourquoi pas définir un taux de resemblance entre les mots. Ainsi 2 mots qui auraient un taux 0 de ressemblance ne pourront jamais se croiser...

C'est ce que je pense aussi.
AMHA, ce n'est pas sur la grille qu'il faut se pencher, mais sur une représentation des mots et leurs relations.
Car on passe l'essentiel de son temps à tester si un mot "rentre" dans un autre ...

J'avais vaguement essayé une approche probabiliste et je m'étais complètement cassé les dents parce que j'oubliais que chaque lettre d'une séquence est intriquée non pas dans une probabilité globale (combien y a-t-il de mots commençant par tel n-uplet de lettres, etc.), mais dans une probabilité LOCALE qui dépend entièrement de l'ascendance verticale ET horizontale de chaque case.
 
Supposons que tu connaisses la fréquence de chaque "préfixe bigramme" (AA....., AB....., etc.) dans ton dico de 7 lettres.
 
Je vois vaguement comment tu cherches à traduire cette connaissance statistique en stratégie pour les deux premières lignes de la grille: tu commences par essayer les préfixes les + probables pour les démarrages de mots verticaux. Mais ça ne nous dit pas comment, par surcroît, tu les combines horizontalement, ces préfixes les + probables. Aux rangs 1, 2, 3 etc.
 
D'autre part, le fait qu'un préfixe soit hyperfréquent de façon globale (par exemple IN..... ou EX.....) n'implique pas de façon certaine qu'il soit le choix judicieux dans un contexte donné.
 
Ainsi, la notion de VARIETE me paraît importante à prendre en compte. Par exemple, tu peux avoir des milliers de mots commençant par "TR...", mais tels que la lettre suivant "TR" soit hypercontrainte (c'est une voyelle: 6 choix) alors que tu auras peut-être moins de mots commençant par un autre digramme -- genre "AN" -- mais "AN" a plus de potentiel pour sa troisième lettre, qui sera une voyelle ou une consonne.
 
Or, le potentiel d'un préfixe "au rang suivant" est extrêmement important puisqu'il va déterminer les possibilité de croisement: "AN..." peut croiser + de mots au rang 3 que "TR...", bien qu'il y ait plus de mots préfixés "TR"!
 
Voilà le genre de difficultés auxquelles on s'affronte dans une approche statistique GLOBALE des n-uplets. Je persiste à penser que la structure intime du problème est arborescente. Et que l'algorithme malin serait celui qui "accélérerait" la navigation dans ces arbres entrecroisés... Mais comment?

est-ce-que ce serait pas intéressant de faire une BD où pour chaque lettre de l'alphabet, tu définisses la liste des mots qui contiennent la lettre avec sa position dans le mot?... Ainsi, par des requêtes SQL, tu pourrais interroger ta BD pour qu'elle te sorte une liste des mots dont tu aurais besoin à un instant t lors de la génération de ta grille...
 
Et qui sait, en fonction des mots proposés et du nb de cases noires que ça engendrerait, tu pourrais faire intervenir un algo génétique (celui que j'avais proposé dans l'un de mes précédents posts.

Je n'arrive pas à me représenter comment tu "maries" l'algo génétique avec cette base de données...
 
Mais ton idée n'est pas sans perspectives...

 
A un instant t de ta génération de grille (mettons une 7x7), tu a déjà mis qq mots dans ta grille et tu viens de faire une requête SQL (avec les contraintes liées aux mots déjà présents) afin de trouver le nouveau mot à mettre dans ta grille qui sera pris dans la liste de mots renvoyée par ta requête. l'algo génétique arrive alors. Plutôt que de prendre systématiquement le mot qui génèrera le moins de cases noires (ex: un des mots contenu dans ta liste fait 5 lettres => le nb de cases noires est donc de 2, cf la grille faisant 7x7 dans mon ex), tu vas faire une sélection "naturelle" dont la probabilité de sélection va dépendre du nb de cases noires associées à chaque mot. Bien sûr, plus un mot a entraînera des cases noires, moins il aura de chance d'être pris, MAIS il aura malgré tout une chance ce qui fait qu'au final, ton algo glabal ne sera pas déterministe... Et en plus, le temps d'exécution de ton algo ne devrait pas trop dériver, partir dans des temps d'exécution faramineux

Je n'essaye pas de combiner les bigrammes horizontalement.  
je me contente de trouver le deuxieme mot horizontal qui me donnera  
les meilleurs bigrammes possibles avec la contrainte du premier
mot horizontal qui lui est impose.  
Par contre effectivement la variete n'est pas prise en compte.  
Dans ce cas au lieu d'utiliser un critere base sur le plus  
grand nombre de mots on peut utiliser un critere  
qui choisit le mot qui offrira la plus grande variete pour le
mot suivant. Je ne sais pas si cette methode marche mais si tu me dis  
ou je peux trouver un dico des 7 lettres par exemple je veux bien
essayer.

 
J'ai pas sous la main mes dicos sources, désolé, mais à la limite tu prends n'importe quelle liste à 7 lettres si c'est juste pour tester.
 
Edit: ...sous-entendu tu serais capable de pondre un code là comme ça au stade où on en est? Alors là respect.

Je pense qu'une phase d'analyse des mots du dico avant de remplir la grille serait utile : amasser tout un tas de statistiques sur la fréquence des lettres, la fréquence de telle ou telle suite de lettres etc. Ensuite tu peux faire intervenir un algo genetique en te basant sur ces statistiques pour calculer la qualité des configurations de grilles obtenues.
Je verrais bien un truc comme ça :
- tu remplis ta grille au hasard
- tu regarde si ta grille est valable (il n'y a que des vrais mots, pas plus de X cases noires)
- tant qu'elle n'est pas valide, tu la transforme en faisant "muter" des lettres ou des ensembles de lettres : plus une lettre forme avec ses voisines une sequence susceptible de faire partie d'un mot, moins elle a de chances de muter. Si une lettre doit muter, tu la remplace par une lettre tirée au hasard, sachant que les lettres ont des probabilités différentes d'être tirées selon leur fréquence dans le dictionnaire (comme au scrabble).

Dans la mesure où je ne suis pas du tout familier des algorithmes génétiques, j'ai tendance à traduire comme un "while-do" ta stratégie :
[citation=487508,2]
...
TANT qu'elle n'est pas valide, tu la TRANSFORMES en faisant "muter" des lettres ou des ensembles de lettres
...
[/citation] (nb: c'est moi qui uppercase)
 
Or, pendant le process, la condition while ("tant que la grille n'est pas valide" ) est non seulement vérifiée presque tout le temps (sinon on aurait gagné!), mais aussi "presque partout", çàd que presque tous les mots vont poser un problème AUX AUTRES MOTS avant d'avoir muté!
 
Tout génétique que soit ton algorithme, il n'en est pas pour autant multi-process. Les opérations se font dans un certain ordre, séparément, malgré tout. Même si elles reposent sur une analyse probabiliste de "qui doit muter" maintenant -- donnant une tournure imprévisible aux opérations -- il n'en reste pas moins qu'une opération va en précéder une autre, et que chaque nouveau choix va rebouleverser assez profondément les choses. Ca risque d'être extrêmement long, tout ça, non?
 
Pourquoi le hasard des mutations génétiques -- même un peu téléguidé par de la statistique -- serait-il plus rapide, à la limite, que de la "force brute" old school?
 
D'autre part, pour qu'une sélection naturelle s'opère, je suppose que des traits dominants (donc stables) doivent apparaître, s'instituer, en exclure d'autres. Ce type de traits doit-il être une relation entre l'individu et le tout ("il est + fort que tout le monde, mieux burné, etc." ) ou bien peut-on se contenter d'une relation inter-individuelle hyper-locale ("le mot CHEVAL croise vachement bien sa 3e lettre avec la 4e lettre des mots en RE... qui sont à son voisinage" )?
 
Je ne crois pas que la deuxième option soit très prometteuse, et je crois malheureusement que c'est l'option qui se dessine ici.
 
Détrompez-moi.

J'ai l'impression que t'as des a priori vis à vis des algos génétiques. Tu devrais te documenter dessus et tu verras que c'est assez puissant et en +, bien souvent, y'a pas besoin de beaucoup de ligne de codes pour les implémenter. En +, un algo génétique bien adapté à un pb converge vers la (ou l'une d'elles) solution "relativement vite".
 
Ex: moi, je voulais développer un algo pour optimiser le remplissage de CDs-R (mais ça marche pour tout support). En entrée, j'avais une liste de fichiers dans laquelle l'algo devait piocher une partie des fichiers voire tous (si c'était possible) afin de remplir une liste de CDs (dont les tailles étaient définies). Un algo combinatoire mettait plusieurs minutes pour remplir 2 CDs avec 25/30 fichiers! Rappel : le nb de combinaisons est (nb de CDs + 1)^(nb de fichiers). le +1 c'est le cd de rejet -> le fichier n'est pas pris. J'ai ensuite codé un algo génétique (algo par séquence) : en qq secondes j'avais une des solutions optimales (à condition que les paramètres de réglages de l'aglo soient bons par rapport au nb de Cds et fichiers en entrée)...

 
Tout à fait exact, rufo. C'est pour cette raison que ça m'intéresse de me déniaiser sur ce sujet et que je pose des questions.

 
y'a 1.5 an de ça, je connaissais pas. maintenat que je connais, je trouve ça très puissant et en général, facile à mettre en oeuvre. Bien sûr, faut pas vouloir mettre de l'ago génétique à toute les sauces. C'est adapté pour certain es catégories de pbs...