图3-4所示的搜索树包含了一条从 Arad 到 Sibiu 再回到 Arad的路径。这时我们称 Arad 为搜索树中的一个重复状态，在本例中该重复状态是由循环生成的。因此，即使状态空间只有20种状态，完整的搜索树也是无限的，因为遍历循环的频率没有限制。
循环是冗余路径的一种特殊情况。例如，我们可以通过路径 Arad——Sibiu（总长140英里）或路径 Arad——Zerind——Oradea——Sibiu(总长297英里)到达 Sibiu. 第二条路径是冗余的——是达到相同状态的一种比较差的方式——在我们需要最优路径时不需要考虑它。
考虑一个 10 ×10网格世界种的智能体，它能移动到8个相邻方格种的任何一个。如果没有障碍，智能体可以在9步或更少的移动内到达100个方格中的任何一个。但是长度为9的路径数量几乎是89(由于网格边缘的存在，路径数稍微少了一点)，超过了1亿条。也就是说，平均意义下，有超过100万条长度为9的冗余路径到达同一个单元格，如果我们消除了冗余路径，搜索完成的速度可以快大约100万倍。俗话说，不记得历史的算法注定要重复历史。有3种方法可以解决这一问题.
第一，我们可以记住之前到达的所有状态（就像最佳优先搜索一样），这样能够检测到所有冗余路径，并只保留每个状态的最优路径。这适用于存在大量冗余路径的状态空间，当内存可以容纳下已达状态表时，它是首选方法。
第二，我们不必担心对过去的重复。在一些问题形式化中，很少或不可能出现两条路径到达相同状态。以装配问题为例，每个动作都会将一个零件添加到一个不断发展的装配中，零件是有序的，因此可以先添加A，然后添加B，但不能先添加B，然后再添加B。对于这些问题，如果我们不记录已达状态也不检查冗余路径，则可以节省内存空间。如果搜索算法会检查冗余路径，我们称之为图搜索；否则，称之为树状搜索。
第三，我们可以选择折中方法，检查循环，当通常不检查冗余路径。由于每个节点都有一个父指针链，因此可以通过跟踪父指针链来查看路径末端的状态之前是否在路径中出现过，从而不需要额外内存即可检查是否存在循环。某些算法实现一直沿着这个链向上移动，从而消除了所有循环。另一些算法实现仅跟踪少数几个链接，因此仅仅需要花费固定的时间就可以消除所有循环，并依靠其他机制来处理长循环。
