图搜索与树搜索 [英] Graph Search vs Tree Search

问题描述

图表搜索和树形搜索与DFS有关的版本与人工智能中的A *搜索有什么区别？

解决方案

从现有的答案来看，这个概念似乎存在很多混淆。

问题总是一个图

树搜索和图搜索的区别并不在于事实不管你的问题是树还是图。它总是假定你正在处理一个图。区别在于遍历模式用于搜索图形，图形可以是图形或树形。

如果你正在处理一个树状问题问题，两种算法变体都会导致相同的结果。因此，您可以选择更简单的树形搜索变体。

图形和树搜索之间的区别

您的基本图形搜索算法看起来如下所示。使用起始节点 start ，将有向边作为后继和a 目标循环条件中使用的规范。 open 包含当前正在考虑的内存中的节点打开列表。请注意，以下伪代码在每个方面都是不正确的（2）。

树搜索

 打开< -  [] 
下一个< - 开始
 
而下一个不是目标{
添加旁边的所有后继开放
下一个<  - 从打开的
中选择一个节点从下一个打开的
删除下一个
 
返回下一个
  

根据实现从打开中选择的方式，您可以获得不同的搜索算法变体，如深度优先搜索（DFS） （选择最新的元素），广度优先搜索（BFS）（挑选最旧的元素）或统一的成本搜索（挑选具有最低路径成本的元素），通过选择具有最低成本加启发式 value等。

上述算法实际上称为树搜索。如果存在多个定向路径，则它将多次访问底层问题图的状态，这些路径都是以起始状态为根。如果它位于有向循环上，甚至可以无限次地访问一个状态。但是每次访问对应于我们的搜索算法生成的树中的不同节点。正如我们后面将要解释的那样，这种明显的低效率是有用的。

图表搜索

多次访问一个国家。因此它会探索在这个状态之后几次发现的子树，这可能是昂贵的。图搜索通过跟踪封闭列表中的所有访问状态来修复此问题。如果新找到的 next 后继者已知，它将不会被插入到打开的列表中：

 打开< -  [] 
关闭<  -  [] 
下一个< - 开始
 
，而下一个不是目标{
添加在关闭的
旁边添加旁边的所有后续打开的，未关闭的
从开放的
删除下一个<  - 从打开的
中选择
 
返回下一个
  





比较

<我们注意到图搜索需要更多的内存，因为它跟踪所有访问状态。这可以通过较小的开放列表进行补偿，从而提高搜索效率。

最佳解决方案

实现选择可以保证返回最优解 - 即最短路径或最小开销路径（对于图成本附加到边缘）。这基本上适用于每当节点按照成本增加的顺序进行扩展时，或者当成本为非零正常数时。实现这种选择的常见算法是统一费用搜索，或者如果步骤费用是相同， BFS 或 IDDFS 。 IDDFS避免了BFS积极的内存消耗，并且当步长不变时，通常建议将其用于不知情的搜索（aka蛮力）。

wikipedia.org/wiki/A*_search_algorithmrel =noreferrer> A *

另外（非常受欢迎的）A * / em>搜索算法与 受理启发式 。然而，A * 图搜索算法仅在与 一致（或单调）启发式 （比可接受性更强的条件）。

为简单起见，所提供的代码不会：

• 处理失败的搜索，即只有在找到解决方案时才可以使用

What is the basic 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 Problem Is Always a Graph

The distinction between tree search and graph search is not rooted in the fact whether your problem is a tree or a graph. It is always assumed you're dealing with a 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.

Difference Between Graph and Tree Search

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).

Tree Search

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

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.

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.

Graph Search

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.

Optimal solutions

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*

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).

(2) Flaws of pseudo-code

For simplicity, the presented code does not:

• handle failing searches, i.e. it only works if a solution can be found

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