图search与树search
我很好奇，在graphicssearch和树search版本之间是否存在DFS，A *search在人工智能方面的基本区别？
从现有的答案来看，这个概念似乎有很多混淆。
问题总是一个图表
树search和图search的区别并不在于您的问题是树还是图。 它总是假定你正在处理一个graphics。 区别在于用于遍历graphics的遍历模式 ，该graphics可以是graphics或树形的。
如果您正在处理树形问题 ，则两种algorithm变体都会导致相同的结果。 所以你可以select更简单的树search变种。
图与树search的区别
您的基本graphicssearchalgorithm如下所示。 随着起始节点的start ，定向边和successors循环条件中使用的goal规范。 open将当前正在考虑的内存中的节点保存在打开的列表中 。 请注意，下面的伪代码在每个方面都是不正确的（2）。
树search
open <- [] next <- start while next is not goal { add successors of next to open next <- select from open remove next from open } return next
根据你如何实现select from open ，你可以获得searchalgorithm的不同变体，比如深度优先search（DFS）（挑选最新元素），广度优先search（BFS）（挑选最旧元素）或者统一成本search最低path成本），通过select具有最低成本加启发式值的节点的stream行的A-starsearch，等等。
上述algorithm实际上被称为树search 。 如果在起始状态下存在多条直接path，它将多次访问底层问题图的状态。 如果它位于有向循环上，甚至可以无限次访问一个状态。 但是每个访问对应于我们的searchalgorithm生成的树中的不同节点 。 正如后面所解释的，有时候这种明显的低效率是需要的
图表search
正如我们所看到的，树search可以多次访问一个状态。 因此，它将探索在这个状态之后几次发现的“子树”，这可能是昂贵的。 图search通过跟踪所有访问的状态在一个封闭的列表中修复。 如果新find的nextinheritance者已经知道，它将不会被插入到打开的列表中：
open <- [] closed <- [] next <- start while next is not goal { add next to closed add successors of next not in closed to open remove next from open next <- select from open } return next
对照
我们注意到图search需要更多的内存，因为它跟踪所有访问状态。 这可以通过较小的开放列表来补偿，这导致search效率的提高。
最佳的解决scheme
一些实现select方法可以保证返回最优解 – 即最短path或者成本最小的path（对于附加了边的成本的图）。 这基本上适用于每当节点按照成本增加的顺序进行扩展时，或者当成本是非零的正常数时。 实现这种select的通用algorithm是统一的成本search ，或者如果步骤成本相同，则使用BFS或IDDFS 。 IDDFS避免了BFS积极的内存消耗，并且当步长不变时，通常推荐使用不知情的search（aka蛮力）。
一个*
此外，（非常stream行的）A * 树searchalgorithm提供了一个最佳的解决scheme，当使用一个容许的启发式 。 然而，A * 图searchalgorithm仅在与一致（或“单调”）启发式 （比可接受性更强的条件）一起使用时才作出这种保证。
（2）伪代码的缺陷
为了简单起见，所提供的代码不：
- 处理失败的search，即它只有在find解决scheme的情况下才有效
树是图的一个特例，所以对一般图的任何作品都适用于树。 树是每对节点之间恰好有一条path的图。 这意味着它不包含任何循环，如前面的回答所述，但是没有循环的有向图（DAG，有向无环图）不一定是一棵树。
然而，如果你知道你的图有一些限制，例如它是一个树或一个DAG，通常可以find一个更有效的searchalgorithm，而不是一个无限制的图。 例如，在树上（只有一个path可以select，可以通过DFS或BFSfind）或者在树上使用A *或者它的非启发式对应“Dijkstraalgorithm”，或者在DAG上（通过考虑通过拓扑sorting获得的顺序中的顶点可以find最佳path）。
对于有向无向图而言，无向图是一个有向的特例，即遵循规则的情况“如果从u到v存在边（链接，转换），也有从v到u的边。
更新 ：请注意，如果您关心的是search的遍历模式，而不是graphics本身的结构，这不是答案。 见，例如，@ ziggystar的答案。
graphics和树之间的唯一区别是循环 。 一个图可能包含循环，一个树不能。 所以当你要在树上实现一个searchalgorithm时，你不需要考虑循环的存在，但是当使用任意图时，你需要考虑它们。 如果你不处理循环，algorithm可能最终会陷入无限循环或无限recursion。
还有一点要考虑的是你正在处理的图的方向性。 在大多数情况下，我们处理表示每个边的父子关系的树。 DAG（有向无环图）也显示类似的特征。 但双向图是不同的。 双向图中的每个边代表两个邻居。 所以algorithm的方法应该有所不同，这两种types的图。
graphicsVS树
- 图表有周期
- 树木没有周期“例如，想像一下你的头脑里有树，树枝不一定与根有直接的联系，但树枝与其他树枝有联系，向上”
但在AI图search与树search的情况下
图search有一个很好的属性，只要algorithm探索一个新的节点并将其标记为已访问，“无论使用的algorithm如何”，该algorithm通常会探索从当前节点可到达的所有其他节点。
例如，考虑下面的三个顶点AB和C的graphics，并考虑以下边缘
AB，BC和CA，从C到A有一个循环，
而当DFS从A开始时，A将产生一个新的状态B，B将产生一个新的状态C，但是当C被探索时，algorithm将尝试产生一个新的状态A，但A已经被访问，因此它将被忽略。 凉！
但是树呢？ 井树algorithm不会将被访问节点标记为已访问，但树没有循环，它将如何进入无限循环？
考虑这个树有3个顶点，并考虑以下边缘
A – B – C植根于A，向下。 假设我们正在使用DFSalgorithm
A将产生一个新的状态B，B将产生两个状态A和C，因为树没有“如果被探测到，就标记一个被访问的节点”，因此也许DFSalgorithm会再次探索A，从而产生一个新的状态B我们正在陷入一个无限循环。
但是你有没有注意到一些东西，我们正在处理无向边界，即AB和BA之间有一个连接。 当然这不是一个循环，因为循环意味着顶点必须大于等于3，除了第一个和最后一个结点之外，所有的顶点都是不同的。
ST A-> B-> A-> B-> A它不是一个循环，因为它违背了循环属性> = 3。但的确是A-> B-> C-> A是一个循环> = 3个不同的节点Checked，第一个和最后一个节点是相同的Checked。
再次考虑树的边缘，A-> B-> C-> B-> A，当然这不是一个循环，因为有两个B，这意味着并不是所有的节点都是不同的。
最后，你可以实现一个树searchalgorithm，以防止两次探索同一个节点。 但是这有后果。
简而言之，树不包含循环和graphics所在的位置。 所以当我们search的时候，我们应该避免图中的循环，这样我们就不会陷入无限循环。
另一个方面是树通常会有一些拓扑sorting或像二叉search树这样的属性，使search如此快速和容易比较图。
