Skip to content
Menu
CDhistory
CDhistory

N-Puzzle

Posted on novembre 4, 2021 by admin

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
  • États initial et cible
  • Algorithme de recherche
  • Fonction heuristique
  • Mode en une seule étape ou en rafale
  • L’arbre de recherche
  • Représentation de l’état
  • Couleurs des nœuds
  • Listes ouvertes et fermées
  • Crédits

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

.

Laisser un commentaire Annuler la réponse

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Articles récents

  • Acela est de retour : NYC ou Boston pour 99 $
  • Entrée OMIM – # 608363 – SYNDROME DE DUPLICATION DU CHROMOSOME 22q11.2
  • Les parents de Kate Albrecht – En savoir plus sur son père Chris Albrecht et sa mère Annie Albrecht
  • Temple Fork Outfitters
  • Burr (roman)

Archives

  • février 2022
  • janvier 2022
  • décembre 2021
  • novembre 2021
  • octobre 2021
  • septembre 2021
  • août 2021
  • juillet 2021
  • juin 2021
  • mai 2021
  • avril 2021
  • DeutschDeutsch
  • NederlandsNederlands
  • SvenskaSvenska
  • DanskDansk
  • EspañolEspañol
  • FrançaisFrançais
  • PortuguêsPortuguês
  • ItalianoItaliano
  • RomânăRomână
  • PolskiPolski
  • ČeštinaČeština
  • MagyarMagyar
  • SuomiSuomi
  • 日本語日本語
©2022 CDhistory | Powered by WordPress & Superb Themes