图搜索和树搜索有什么区别? [英] What is the difference between graph search and tree search?

问题描述

图搜索和树搜索版本在Dem，人工智能中的A *搜索之间有什么区别?

What is the difference between graph search and tree search versions regarding DFS, A* searches in artificial intelligence?

推荐答案

从现有的答案来看，这个概念似乎有很多困惑.

Judging from the existing answers, there seems to be a lot of confusion about this concept.

树搜索和图搜索之间的区别并不基于问题图是树还是普通图这一事实.始终假定您正在处理一般图形.区别在于用于遍历图的遍历模式，该图可以是图形或树形.

The distinction between tree search and graph search is not rooted in the fact whether the problem graph is a tree or a general graph. It is always assumed you're dealing with a general graph. The distinction lies in the traversal pattern that is used to search through the graph, which can be graph-shaped or tree-shaped.

如果您要处理树形的问题，则这两种算法变体都会得出相同的结果.因此，您可以选择更简单的树形搜索变体.

If you're dealing with a tree-shaped problem, both algorithm variants lead to equivalent results. So you can pick the simpler tree search variant.

您的基本图形搜索算法如下所示.对于起始节点start，在循环条件中使用有向边为successors和goal规范. open将节点保存在内存中，这些节点目前正在考虑使用开放列表.请注意，以下伪代码并非在各个方面(2)都是正确的.

Your basic graph search algorithm looks something like the following. With a start node start, directed edges as successors and a goal specification used in the loop condition. open holds the nodes in memory, which are currently under consideration, the open list. Note that the following pseudo code is not correct in every aspect (2).

open <- []
next <- start

while next is not goal {
    add all successors of next to open
    next <- select one node from open
    remove next from open
}

return next

根据实现方式select from open，可以获得不同的搜索算法变体，例如深度优先搜索(DFS)(选择最新元素)，宽度优先搜索(BFS)(选择最旧元素)或统一成本搜索(选择具有最低路径成本的元素)，通过选择具有最低成本加启发式值的节点来进行流行的A星搜索，等等.

Depending on how you implement select from open, you obtain different variants of search algorithms, like depth-first search (DFS) (pick newest element), breadth first search (BFS) (pick oldest element) or uniform cost search (pick element with lowest path cost), the popular A-star search by choosing the node with lowest cost plus heuristic value, and so on.

上述算法实际上称为树搜索.如果有多个指向其的根源始于起始状态，它将多次访问基础问题图的状态.如果状态位于有向循环中，则甚至有可能无数次访问状态.但是每次访问都对应于由我们的搜索算法生成的树中的不同 node .有时需要这种明显的低效率，如稍后所述.

The algorithm stated above is actually called tree search. It will visit a state of the underlying problem graph multiple times, if there are multiple directed paths to it rooting in the start state. It is even possible to visit a state an infinite number of times if it lies on a directed loop. But each visit corresponds to a different node in the tree generated by our search algorithm. This apparent inefficiency is sometimes wanted, as explained later.

如我们所见，树搜索可以多次访问一个状态.因此，它将探索在此状态之后多次发现的子树"，这可能会很昂贵.图形搜索通过在封闭列表中跟踪所有访问状态来解决此问题.如果已经知道新找到的next的后继者，则不会将其插入到打开的列表中:

As we saw, tree search can visit a state multiple times. And as such it will explore the "sub tree" found after this state several times, which can be expensive. Graph search fixes this by keeping track of all visited states in a closed list. If a newly found successor to next is already known, it won't be inserted into the open list:

open <- []
closed <- []
next <- start

while next is not goal {
    add next to closed
    add all successors of next to open, which are not in closed 
    remove next from open
    next <- select from open
}

return next

比较

我们注意到图搜索需要更多的内存，因为它可以跟踪所有访问过的状态.较小的打开列表可以弥补这一点，从而提高搜索效率.

Comparison

We notice that graph search requires more memory, as it keeps track of all visited states. This may compensated by the smaller open list, which results in improved search efficiency.

某些实现select的方法可以保证返回最优解-即最短路径或具有最小成本的路径(对于将成本附加到边上的图) .只要按成本增加顺序扩展节点，或者当成本为非零正常数时，这基本上成立.实现这种选择的常见算法是统一成本搜索，或者如果分步成本是相同， BFS 或

Some methods of implementing select can guarantee to return optimal solutions - i.e. a shortest path or a path with minimal cost (for graphs with costs attached to edges). This basically holds whenever nodes are expanded in order of increasing cost, or when the cost is a nonzero positive constant. A common algorithm that implements this kind of select is uniform cost search, or if step costs are identical, BFS or IDDFS. IDDFS avoids BFS's aggressive memory consumption and is generally recommended for uninformed search (aka brute force) when step size is constant.

(非常流行的)A * tree 搜索算法与 可允许的启发式 .但是，A * graph 搜索算法仅在与 一致(或单调")启发式 (比可允许性强的条件).

Also the (very popular) A* tree search algorithm delivers an optimal solution when used with an admissible heuristic. The A* graph search algorithm, however, only makes this guarantee when it used with a consistent (or "monotonic") heuristic (a stronger condition than admissibility).

为简单起见，显示的代码没有:

For simplicity, the presented code does not:

• 处理搜索失败，即仅在找到解决方案的情况下才有效

这篇关于图搜索和树搜索有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！