algorithm - 与人工智能中的最佳优先搜索相关的问题是什么？

Question

我知道一般问题包括局部最大值和高原，但我很好奇是否还有与此特定搜索相关的任何其他问题，以及为了克服这些问题我最好的行动方案是什么。

谁能给我举个例子，说明这个搜索适用于哪种问题？

Answer 1

最佳优先搜索的问题:

1. 它是贪婪的。在许多情况下，它会导致非常快速的解决方案(因为你的开发节点数不增加指数地，它随着深度的增加而线性增加解决方案!)，但是它通常没有优化，因为你的启发式函数有一些错误，有时会出错回答要探索的下一个节点。

2. 无限分支也存在问题。假设你是跟随一个分支，其中深度 i 处的节点具有启发式值h(v_i) = 2^-i。你永远不会归零，但最好先贪心将继续开发这些节点。
   例子:

                           2
                          / \  
                         /   \
                        /     \
                       1      1.5
                       |       |
                      1/2      1
                       |       |
                      1/4      0
                       |
                      1/8
                       |
                      1/16
                       |
                      ... 
   

注意上面是admissible heuristic function , 但尽管如此，最好的优先搜索永远不会得到解决方案，它会卡在无限分支中。

解决方案:

1. 为了克服它，我们可以使用统一的算法(例如 Dijkstra 的算法或未加权图的 BFS)
2. 您可以结合使用“最佳优先搜索”和 Dijkstra，这被称为 A* algorithm .
   A* 算法实际上是一个贪婪的最佳优先算法，但不是根据h(v) 来选择，而是通过f(v) = h 选择下一个要探索的节点(v) + g(v)(其中 g(v) 是“到目前为止的成本”)。该算法是完整的(如果存在则找到解决方案)并且是最优的(找到“最佳”解决方案)如果它被赋予 admissible heuristic function 。

何时使用最佳优先搜索:

1. 如果您有一个完美的启发式算法(在文献中表示为 h*)，最佳优先搜索将找到最佳解决方案 - 而且速度很快。
2. 如果您不关心最佳解决方案，您只想快速找到一个解决方案 - 它通常可以解决问题(但您必须小心无限分支问题)。
3. 当我们使用 A* 时，我们实际上使用的是最佳优先搜索 - 但在 f:V->R 而不是 h:V->R 上。<