Cette application web vous permet de visualiser une représentation graphique d’une gamme de différents algorithmes de recherche de graphes, tout en résolvant votre choix de problèmes de 8 puzzles.
Démarrer
Sur le côté gauche de cette application, vous verrez le panneau de contrôle. En utilisant le panneau de configuration, vous pouvez configurer les aspects suivants de l’application :
- État initial et état du but
- Quel algorithme de recherche utiliser
- Quelle fonction heuristique utiliser, si vous utilisez un algorithme de recherche informée
- Et s’il faut utiliser le mode en une seule étape ou en rafale
Chacune de ces options sera décrite plus en détail ci-dessous.
États initial et cible
Pour définir les états initial ou cible, vous pouvez cliquer soit sur le bouton « Modifier l’état », soit sur la représentation graphique de l’état.
Vous devriez voir une popup comme la suivante:
Pour changer une tuile, cliquez simplement sur la tuile que vous souhaitez remplacer, puis entrez la nouvelle valeur sur votre clavier. Cela échangera la tuile avec celle qui détenait précédemment cette valeur.
Algorithme de recherche
N-Puzzle prend en charge cinq algorithmes de recherche différents basés sur le graphique. Les trois premiers sont des algorithmes de recherche non informés :
- Recherche en largeur d’abord
- Recherche en profondeur d’abord
- Recherche itérative d’approfondissement
Les deux autres sont des algorithmes de recherche informés :
- Recherche A*
- Recherche grégaire
Si vous choisissez un algorithme de recherche informée, alors vous devrez également choisir une fonction heuristique.
Fonction heuristique
N-Puzzle prend en charge trois fonctions heuristiques différentes :
- Distance euclidienne
- Distance Manhattan (distance ville-bloc)
- Carreaux hors de place
Mode en une seule étape ou en rafale
N-Puzzle peut être utilisé dans deux modes. Le mode par défaut est le mode Single-Step, qui vous permet de » rembobiner » une recherche, une étape à la fois. Ceci est utile pour mieux comprendre le fonctionnement d’un algorithme de recherche.
L’autre mode est le mode rafale. Une fois lancé, le Burst Mode continue à exécuter une recherche jusqu’à ce que l’état but soit trouvé. Une recherche en mode rafale peut être mise en pause, mais ne peut pas être « rembobinée ».
L’arbre de recherche
Représentation de l’état
Pendant qu’une recherche est active, vous pourrez voir une représentation visuelle de l’arbre de recherche. Chaque nœud de cet arbre de recherche représente un arrangement de tuiles (ou état), et est dessiné comme une boîte qui est divisée en 4 sections.
Le diagramme suivant montre un nœud pris dans une recherche Greedy:
La plus grande section est l’état du puzzle. En dessous, vous verrez deux sections plus petites.
Sous l’état du puzzle se trouvent deux sections. La section de gauche est la profondeur du nœud. La section à droite est le score heuristique. Le score heuristique n’est utilisé qu’avec les algorithmes de recherche informée, donc si vous utilisez la recherche par largeur, profondeur ou approfondissement itératif, le score heuristique sera omis.
La dernière section enregistre l’ordre dans lequel les nœuds ont été développés. Par exemple, le nœud racine sera toujours ‘#1’, et le prochain nœud à être développé sera marqué comme ‘#2’.
Couleurs des nœuds
Pour aider à rendre l’arbre de recherche plus ‘lisible’, la bordure de chaque nœud est codée en couleur en fonction de son état actuel.
Le diagramme suivant montre l’algorithme A* (avec l’heuristique de la distance euclidienne) appliqué à un problème qui peut être résolu en seulement deux coups :
Les couleurs peuvent être interprétées comme suit :
| Couleur | Message |
|---|---|
| Bleu | Si un nœud est dans la liste ouverte alors il sera surligné en bleu. |
| Rouge | Après chaque itération d’un algorithme de recherche, le nœud qui sera développé ensuite sera surligné en rouge. Cela s’applique même lorsque le nœud but a été trouvé. |
| Gris | Si un état a été exploré, il sera grisé. Par exemple, à l’étape 2) du diagramme ci-dessus, l’état initial a été coloré en gris pour indiquer qu’il a été exploré. A l’étape 3), un nœud représentant l’état initial est redécouvert mais il ne sera pas développé puisque l’état initial a été développé via le nœud racine. |
| Vert | Une fois que l’état but a été trouvé, il sera surligné en vert. |
| Or | Une fois qu’un nœud représentant l’état but a été trouvé, tous les nœuds sur le chemin de retour au nœud racine seront surlignés en or. |
| Pourpre | Lorsque vous utilisez la recherche itérative d’approfondissement, les nœuds inexplorés qui dépassent la profondeur maximale ne seront pas ajoutés à la liste ouverte. Ces nœuds seront colorés en violet. |
Listes ouvertes et fermées
Pendant l’exécution des algorithmes de recherche, deux listes sont maintenues. La première est la liste ouverte – elle est utilisée pour garder la trace des nœuds qui ont été découverts, mais pas encore explorés.
La seconde est la liste fermée – elle est utilisée pour garder la trace des nœuds qui ont été explorés, ou des nœuds qui ne seront pas explorés car ils représentent des états qui ont déjà été explorés via d’autres nœuds.
Lorsqu’une recherche est active, le nombre de nœuds dans les listes ouvertes et fermées sera visible dans le coin supérieur gauche :
Crédits
.