Bonjour,

Je suis en train de m'amuser à tester des algos de parcours de graphes sur le jeu du taquin (afin de faire un solveur):

Je recherche une facon de calculer la profondeur maximum du graphe pour etre statistiquement "presque" sûr (oui les matheux apprécieront ce magnifique terme ) d'avoir visité tous les états possibles.

Ce que je sais (en appelant n la largeur = hauteur de la grille):

- Il y a n! arrangements sur la grille (seulement la moitié peut être résolu d'après la loi de Sam Loyd)

- Le "branching factor" (nommé b ensuite) est de 2.66 pour une grille de 3x3 et tend jusqu'à 4 si n -> infini. Plus généralement, la formule est 4*n*(n-1)/n².

- A une profondeur (d), on a donc statistiquement b^d états possibles.

- Si on compte tous les états visités jusqu’à une profondeur d, on a somme(b^k) pour tous les k entre 0 et d.

Du coup, je peux estimer que pour visiter n!/2 états, il faut trouver la profondeur P tel que la somme des somme(b^k) > n!/2 pour k entre 0 et P.  Cependant, cela ne prends pas en considération les mouvements qui" s’entre-tuent". Par exemple dans le graphe, on peut avoir une alternance du même mouvement (bouger a gauche, bouger à droite, bouger à gauche, ... P fois) mais au final je n'aurais visité que 2 états.

Du coup existe-t-il une façon d'estimer la profondeur à partir de laquelle, on est sur d'avoir fait tous les états. Cela signifierait que tous taquins dits solvables peut-être résolu en P coups maximum.

Merci à vous !

Nicolas

Petit rectificatif avant de commencer. 

Tu emploies différentes formules avec n. Mais parfois n représente la largeur de la grille ; b = branching_factor = 4*n*(n-1)/n².  (pourquoi on ne simplifie pas par n ?)

Et parfois, n représente la 'surface' de la grille. Nombre d'arrangements = N!

Je vais noter n=la largeur de la grille, et N=n²=la surface de la grille.

A tout moment, on a b mouvements possibles. Mais, tu l'as souligné, un de ces b mouvements est 'stupide', on a donc b-1 mouvements utiles.  En dehors de ce cas précis, on a peu de configurations qui bouclent.

Donc notons bf=b-1=(4*(n-1)/n)-1.

On cherche d, tel que bf^d soit supérieur ou égal à N!/2

Et donc d >= ln(N!/2)/ln(bf).

Exemple de configuration qui boucle, et sur laquelle je fais l'impasse : la case vide fait un mouvement en carré, et fait ce carré 4 fois de suite. 

Je ne suis pas totalement sûr de la formule, mais comme tu veux être presque sûr de couvrir toutes les combinaisons, ça devrait être bon.

PS

Je fais l'impasse sur les mouvements en boucle, mais il y a aussi une autre impasse. Le branching-factor nous dit : à partir d'une position aléatoire, le nombre de mouvements possible est ...

Mais en fait, la 'case-vide' n'est pas dans une position aléatoire. Je pense que la case-vide est plus souvent dans une case 'centrale' que sur l'un des bords, ou dans l'un des 4 coins. Donc l'un dans l'autre, on peut considérer que les 2 impasses s'annulent, et que la formule ci-dessus doit être assez bonne. Surtout sur une grande grille.

Bonjour,

Merci pour la réponse. En effet, je me suis trompé sur le nombre d’arrangements c'est n²! (ou N! si N = n² ). 

Concernant ta formule pour avoir la profondeur, je suis d'accord (dans mon cas je l'ai programmé itérativement). Pour une grille 4x4 avec un branching factor de 3 (sans prendre en compte le mouvement précédent), il faut 44 niveaux de profondeur (de mémoire).

Ce que je me dit c'est qu'a 40 ou 41 niveau, on a peut être 99.99% de chance d'avoir eu tous les états de grilles car certains états du niveau 44 sont atteints entre le niveau 1 et 40/41 ?  Le problème c'est que mathématiquement, je ne sais pas comment trouver ça. C'est pareil avec un Rubik cube je suppose ou tout autres jeux de ce genre.

Actuellement avec 40 niveaux de profondeur les algos mettent beaucoup de temps à parcourir le graphe (et de mémoire selon le type d'algos) et je voudrais limiter au max la profondeur (et en parallèle optimiser leur code bien sur). 

En tout cas merci de la réponse

Nicolas