识别状态空间树中的重复状态 [英] Identify duplicate states in a state space tree

问题描述

我一直在阅读此问题以供参考: 图形搜索与树形搜索

I have been reading this question for reference: Graph Search vs Tree Search

其中一位评论者发表了此评论，而这正是我所面临的情况.

One of the commenters made this comment which is exactly the situation I am facing.

更正式地说，可以通过树搜索而不是节点多次访问'单一状态'.因为搜索树中的每个节点都对应于沿着状态空间图的单个路径并被访问最多只能通过树搜索一次."

"It is more formal to say that a 'single state' could be visited multiple times by a tree search, and NOT a node. As every node in search tree corresponds to a single path along the state space graph and is visited at most once by tree searches."

我的搜索算法生成的节点与搜索树中已经存在的节点相同.检测此新生成状态是否已存在的最佳方法是什么，这样我就可以避免进入无限循环? 我无法使用封闭列表，需要对DFS进行周期检测.做这个的最好方式是什么?这是我为练习而在AI课程中提出的作业问题，而不是提交的问题.我是出于好奇而建立代理.感谢您的帮助

My search algorithm is generating nodes that are identical to ones already in the search tree. What is the best way to detect that this newly generated state is already present, so i can avoid going into the infinite loop? I cannot use a closed list, and need to do cycle detection for DFS. What is the best way to do this? This is from an assignment question in an AI course that I am doing for practice.It is not for submission. I am building the agent just out of curiosity. Any help is appreciated

推荐答案

出于完整性考虑，我想发布自己问题的答案.我最终在从根到下的路径中接触的每个节点中设置了一个访问位，如果我访问了一个设置了访问标志的节点，那将得出一个周期，这是正常的方法.

I wanted to post an answer to my own question for completeness. I ended up setting a visited bit in each node i touched on the path from the root down and would conclude there is a cycle if i ever visited a node that had its visited flag set, which is the normal way.

我基本上有一堆称为顶点"和边缘"的对象，它们位于这些顶点之间，并且如果我遍历了另一端是顶点的边缘，则我将访问标记设置为该对象代码中有一个循环.就像在其他链接中提到的那样，每个节点基本上都是一个具有不同状态对象的新对象，但是状态对象基本上代表了代理程序之前所在的位置，因此我们希望避免生成此重复节点.

I basically had a bunch of objects called "vertices" and "edges", which were between these vertices and if i ever traverse an edge at the other end of which was a vertex i had the visited flag set for, i know there is a cycle in the code. As mentioned in the other link, each node is basically a new object with a different state object but the state object basically represents a location the agent has been before and we want to avoid generating this duplicate node.

这篇关于识别状态空间树中的重复状态的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！