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

请注意，上面是允许的启发式函数，但是最好的第一次搜索永远不会得到解决方案，它会卡在无限分支中。

解决方案：

1. 为了克服它，我们可以使用统一算法（例如 Dijkstra 算法或用于未加权图的 BFS）
2. 您可以使用“最佳优先搜索”和 Dijkstra（称为A* 算法）的组合。
   A* 算法实际上是一个贪婪的最佳优先算法，但不是根据 选择，而是选择h(v)接下来要探索的节点f(v) = h(v) + g(v)（g(v)“到目前为止的成本”在哪里。算法是完整的（如果存在则找到解决方案）并且是最优的（找到“最佳”解决方案）如果给定一个可接受的启发式函数。

何时使用最佳优先搜索：

1. 如果你有一个完美的启发式（如h*文献中所表示的），最好的第一次搜索会找到一个最优的解决方案——而且速度很快。
2. 如果您不关心最佳解决方案，您只想快速找到一个解决方案 - 它通常可以解决问题（但您必须小心无限分支问题）。
3. 当我们使用 A* 时，我们实际上使用最佳优先搜索 - 但使用 onf:V->R而不是 on h:V->R。