Suivi des états visités dans Recherche en priorité

J'essayais donc d'implémenter BFS sur un puzzle de blocs coulissants (type numérique). Maintenant, la principale chose que j'ai remarquée est que si vous avez une 4*4carte, le nombre d'états peut être aussi grand que 16!je ne peux pas énumérer tous les états à l'avance.

Ma question est donc de savoir comment suivre les états déjà visités? (J'utilise un tableau de classe chaque instance de classe contient un modèle de tableau unique et est créée en énumérant toutes les étapes possibles de l'étape en cours).

J'ai cherché sur le net et apparemment, ils ne reviennent pas à l'étape précédente qui vient d'être terminée, MAIS nous pouvons également revenir à l'étape précédente par un autre itinéraire, puis réénumérer à nouveau toutes les étapes précédemment visitées. Alors, comment garder une trace des États visités alors que tous les États n'ont pas déjà été énumérés? (comparer les états déjà présents à l'étape actuelle coûtera cher).

Vous pouvez utiliser un set(au sens mathématique du mot, c'est-à-dire une collection qui ne peut pas contenir de doublons) pour stocker des états que vous avez déjà vus. Les opérations dont vous aurez besoin pour effectuer ces opérations sont les suivantes:

• insertion d'éléments
• tester si des éléments sont déjà là

Presque tous les langages de programmation devraient déjà avoir un support pour une structure de données qui peut effectuer ces deux opérations en temps constant ( ). Par exemple:$O(1)$

• set en Python
• HashSet en Java

À première vue, cela peut sembler ajouter tous les états que vous voyez à un ensemble comme celui-ci sera coûteux en mémoire, mais ce n'est pas trop mauvais par rapport à la mémoire dont vous avez déjà besoin pour votre frontière; si votre facteur de branchement est , votre frontière augmentera de b - 1 éléments par nœud que vous visitez (supprimez 1 nœud de la frontière pour le "visiter", ajoutez b nouveaux successeurs / enfants), tandis que votre ensemble ne grandira que de $b$$b - 1$$1$$b$$1$ supplémentaire nœud par nœud visité.

En pseudocode, un tel ensemble (nommons-le closed_set, pour être cohérent avec le pseudocode sur wikipedia pourrait être utilisé dans une recherche en largeur comme suit:

frontier = First-In-First-Out Queue
frontier.add(initial_state)

closed_set = set()

while frontier not empty:
    current = frontier.remove_next()

    if current == goal_state:
        return something

    for each child in current.generate_children()
        if child not in closed_set:    // This operation should be supported in O(1) time regardless of closed_set's current size
            frontier.add(child)

    closed_set.add(current)    // this should also run in O(1) time

(certaines variantes de ce pseudocode peuvent également fonctionner et être plus ou moins efficaces selon la situation; par exemple, vous pouvez également prendre le closed_setpour contenir tous les nœuds dont vous avez déjà ajouté des enfants à la frontière, puis éviter complètement l' generate_children()appel si currentest déjà dans leclosed_set .)

Ce que j'ai décrit ci-dessus serait la manière standard de gérer ce problème. Intuitivement, je soupçonne qu'une autre "solution" pourrait être de toujours randomiser l'ordre d'une nouvelle liste d'États successeurs avant de les ajouter à la frontière. De cette façon, vous n'évitez pas le problème d'ajouter occasionnellement des états que vous avez déjà étendus à la frontière, mais je pense que cela devrait réduire considérablement le risque de rester coincé dans des cycles infinis.

Attention : je ne connais aucune analyse formelle de cette solution qui prouve cependant qu'elle évite toujours les cycles infinis. Si j'essaie de «faire fonctionner» cela dans ma tête, intuitivement, je pense que cela devrait fonctionner, et cela ne nécessite aucune mémoire supplémentaire. Il y a peut-être des cas marginaux auxquels je ne pense pas pour le moment, donc cela pourrait tout simplement ne pas fonctionner, la solution standard décrite ci-dessus sera un pari plus sûr (au prix de plus de mémoire).

La réponse de Dennis Soemers est correcte: vous devez utiliser un HashSet ou une structure similaire pour garder une trace des états visités dans BFS Graph Search.

Cependant, cela ne répond pas tout à fait à votre question. Vous avez raison, dans le pire des cas, BFS vous demandera alors d'en stocker 16! nœuds. Même si les temps d'insertion et de vérification dans l'ensemble seront O (1), vous aurez toujours besoin d'une quantité de mémoire absurde.

Pour résoudre ce problème, n'utilisez pas BFS . Il est insoluble pour tous, mais le plus simple des problèmes, car il nécessite à la fois du temps et de la mémoire qui sont exponentiels dans la distance à l'état de but le plus proche.

Un algorithme beaucoup plus efficace en mémoire est l' approfondissement itératif . Il possède toutes les propriétés souhaitables de BFS, mais utilise uniquement la mémoire O (n), où n est le nombre de mouvements pour atteindre la solution la plus proche. Cela peut encore prendre un certain temps, mais vous atteindrez les limites de mémoire bien avant les limites liées au processeur.

Mieux encore, développez une heuristique spécifique au domaine et utilisez la recherche A * . Cela devrait vous obliger à examiner uniquement un très petit nombre de nœuds et à permettre à la recherche de se terminer dans quelque chose de beaucoup plus proche du temps linéaire.

Bien que les réponses données soient généralement vraies, un BFS dans le casse-tête 15 n'est pas seulement tout à fait réalisable, il a été fait en 2005! L'article qui décrit l'approche peut être trouvé ici:

http://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf

Quelques points clés:

• Pour ce faire, une mémoire externe était nécessaire - c'est-à-dire que le BFS utilisait le disque dur pour le stockage au lieu de la RAM.
• Il n'y a en fait que 15! / 2 états, car l'espace d'état a deux composants mutuellement inaccessibles.
• Cela fonctionne dans le puzzle de tuiles coulissantes car les espaces d'état se développent très lentement d'un niveau à l'autre. Cela signifie que la mémoire totale requise pour n'importe quel niveau est beaucoup plus petite que la taille complète de l'espace d'état. (Cela contraste avec un espace d'état comme le Rubik's Cube, où l'espace d'état croît beaucoup plus rapidement.)
• Parce que le puzzle des tuiles coulissantes n'est pas orienté, vous n'avez qu'à vous soucier des doublons dans le calque actuel ou précédent. Dans un espace dirigé, vous pouvez générer des doublons dans n'importe quelle couche précédente de la recherche, ce qui rend les choses beaucoup plus compliquées.
• Dans le travail original de Korf (lié ci-dessus), ils n'ont pas réellement enregistré le résultat de la recherche - la recherche a simplement calculé le nombre d'états à chaque niveau. Si vous souhaitez stocker les premiers résultats, vous avez besoin de quelque chose comme WMBFS ( http://www.cs.du.edu/~sturtevant/papers/bfs_min_write.pdf )
• Il existe trois approches principales pour comparer les états des couches précédentes lorsque les états sont stockés sur disque.
  • Le premier est basé sur le tri. Si vous triez deux fichiers de successeurs, vous pouvez les numériser dans un ordre linéaire pour trouver des doublons.
  • Le second est basé sur le hachage. Si vous utilisez une fonction de hachage pour regrouper les successeurs dans des fichiers, vous pouvez charger des fichiers plus petits que l'espace d'état complet pour rechercher les doublons. (Notez qu'il y a deux fonctions de hachage ici - une pour envoyer un état à un fichier et une pour différencier les états dans ce fichier.)
  • Le troisième est la détection des doublons structurés. Il s'agit d'une forme de détection basée sur le hachage, mais elle est effectuée de manière à ce que les doublons puissent être vérifiés immédiatement lorsqu'ils sont générés plutôt qu'après qu'ils ont tous été générés.

Il y a beaucoup plus à dire ici, mais les articles ci-dessus donnent beaucoup plus de détails.

Ironiquement, la réponse est «utilisez le système que vous voulez». Un hashSet est une bonne idée. Cependant, il s'avère que vos préoccupations concernant l'utilisation de la mémoire ne sont pas fondées. BFS est si mauvais dans ce genre de problèmes qu'il résout ce problème pour vous.

Considérez que votre BFS vous oblige à conserver une pile d'états non traités. Au fur et à mesure que vous progressez dans le puzzle, les états avec lesquels vous traitez deviennent de plus en plus différents, vous verrez donc probablement que chaque pli de votre BFS multiplie le nombre d'états à examiner par environ 3.

Cela signifie que, lorsque vous traitez le dernier pli de votre BFS, vous devez avoir au moins 16! / 3 états en mémoire. Quelle que soit l'approche que vous avez utilisée pour vous assurer que la mémoire en place sera suffisante pour que votre liste précédemment visitée soit également en mémoire.

Comme d'autres l'ont souligné, ce n'est pas le meilleur algorithme à utiliser. Utilisez un algorithme mieux adapté au problème.

Le problème des 15 puzzles se joue sur une planche 4x4. L'implémentation de cela dans le code source se fait par étapes. Au début, le moteur de jeu lui-même doit être programmé. Cela permet de jouer au jeu par un opérateur humain. Le jeu de 15 casse-têtes n'a qu'un seul élément gratuit et sur cet élément les actions sont exécutées. Le moteur de jeu accepte quatre commandes possibles: gauche, droite, haut et bas. D'autres actions ne sont pas autorisées, et il est possible de contrôler le jeu uniquement avec ces instructions.

La couche suivante pour jouer au jeu est une interface graphique. C'est très important, car cela permet de tester le moteur de jeu et d'essayer de résoudre le jeu à la main. En outre, une interface graphique est importante car nous devons trouver des heuristiques potentielles. Et maintenant, nous pouvons parler de l'IA elle-même. L'IA doit envoyer des commandes au moteur de jeu (gauche, droite, haut et bas). Une approche naïve pour un solveur serait un algorithme de recherche par force brute, ce qui signifie que l'IA envoie des commandes aléatoires jusqu'à ce que l'état cible soit atteint. Une idée plus avancée consiste à implémenter une sorte de base de données de modèles qui réduit l'espace d'état. L'étendue de la première recherche n'est pas directement une heuristique, mais c'est un début. Il est égal de créer un graphique pour tester les mouvements possibles de manière chronologique.

Le suivi des états existants peut être effectué avec un graphique. Chaque état est un nœud, a un identifiant et un identifiant parent. L'IA peut ajouter et supprimer des nœuds dans le graphique, et le planificateur peut résoudre le graphique pour trouver un chemin vers l'objectif. Du point de vue de la programmation, un moteur de jeu du puzzle 15 est l'objet et la liste de nombreux objets est un arraylist. Ils sont stockés dans une classe graphique. La réalisation de cela dans le code source est un peu délicate, généralement le premier essai échouera et le projet produira beaucoup d'erreurs. Pour gérer la complexité, un tel projet se fait généralement dans un projet académique, c'est-à-dire qu'il s'agit d'un sujet d'écriture d'un article à ce sujet qui peut avoir 100 pages et plus.

Approches du jeu

Il est vrai que le conseil a $16!$états possibles. Il est également vrai que l'utilisation d'un ensemble de hachage est ce que les étudiants apprennent dans un cours d'algorithme de première année pour éviter la redondance et les boucles sans fin lors de la recherche d'un graphique qui peut contenir des cycles de graphique.

Cependant, ces faits triviaux ne sont pas pertinents si le but est de terminer le puzzle dans le moins de cycles de calcul. L'étendue de la première recherche n'est pas un moyen pratique de terminer un puzzle de mouvement orthogonal. Le coût très élevé d'une première recherche étendue ne serait nécessaire que si le nombre de mouvements est d'une importance capitale pour une raison quelconque.

Descente de sous-séquence

La plupart des sommets représentant des états ne seront jamais visités, et chaque état visité peut avoir entre deux et quatre fronts sortants. Chaque bloc a une position initiale et une position finale et la planche est symétrique. La plus grande liberté de choix existe lorsque l'espace ouvert est l'une des quatre positions médianes. Le moins, c'est quand l'espace ouvert est l'une des quatre positions de coin.

Une fonction de disparité (erreur) raisonnable est simplement la somme de toutes les x disparités plus la somme de toutes les disparités y et un nombre représentant heuristiquement lequel des trois niveaux de liberté de mouvement existe en raison du placement résultant de l'espace ouvert (milieu, bord , coin).

Bien que les blocs puissent s'éloigner temporairement de leur destination pour soutenir une stratégie d'achèvement nécessitant une séquence de mouvements, il y a rarement un cas où une telle stratégie dépasse huit mouvements, générant, en moyenne, 5 184 permutations pour lesquelles les états finaux peuvent être comparés en utilisant la fonction de disparité ci-dessus.

Si l'espace vide et les positions des blocs 1 à 15 sont codés comme un tableau de quartets, seules les opérations d'addition, de soustraction et de bits sont nécessaires, ce qui rend l'algorithme rapide. La répétition des huit stratégies de force brute de mouvement peut être répétée jusqu'à ce que la disparité tombe à zéro.

Sommaire

Cet algorithme ne peut pas faire de cycle car il y a toujours au moins une des permutations de huit mouvements qui diminue la disparité, quel que soit l'état initial, à l'exception d'un état de départ déjà complet.