Identifier les états en double dans un arbre espace d'état

Question

Je lis cette question pour référence: Graph Search vs Tree Search

Un des commentateurs a fait ce commentaire qui est exactement la situation dans laquelle je suis confronté. "Il est plus formel de dire qu'un" état unique "peut être visité plusieurs fois par une recherche d'arbre, et NON un nœud .Comme chaque nœud dans l'arbre de recherche correspond à un seul chemin le long du graphe d'espace d'état et est visité au plus une fois par des recherches d'arbres. "

Mon algorithme de recherche génère des nœuds identiques à ceux déjà présents dans l'arbre de recherche. Quelle est la meilleure façon de détecter que cet état nouvellement généré est déjà présent, donc je peux éviter d'entrer dans la boucle infinie? Je ne peux pas utiliser une liste fermée et j'ai besoin de faire une détection de cycle pour DFS. Quelle est la meilleure façon de procéder? C'est d'une question d'affectation dans un cours d'IA que je fais pour la pratique. Ce n'est pas pour la soumission. Je construis l'agent juste par curiosité. Toute aide est appréciée

Answer 1

Je voulais poster une réponse à ma propre question pour l'exhaustivité. J'ai fini par définir un bit visité dans chaque nœud que j'ai touché sur le chemin de la racine vers le bas et conclurais qu'il y a un cycle si jamais j'ai visité un nœud qui avait son drapeau visité, ce qui est la manière normale. J'ai essentiellement eu un tas d'objets appelés "sommets" et "arêtes", qui se trouvaient entre ces sommets et si jamais je traversais un bord à l'autre extrémité de laquelle était un sommet pour lequel le drapeau visité était fixé, je Sachez qu'il y a un cycle dans le code. Comme mentionné dans l'autre lien, chaque nœud est fondamentalement un nouvel objet avec un objet d'état différent mais l'objet d'état représente fondamentalement un emplacement que l'agent a été avant et nous voulons éviter de générer ce nœud dupliqué.