人工智能中的最佳优先搜索有哪些问题？

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)"到目前为止的成本".算法是完整的(找到解决方案,如果存在)并且最优(如果给出一个允许的启发式函数,则找到"最佳"解决方案).

何时使用Best First Search:

1. 如果你有一个完美的启发式(h*在文献中表示),最好的第一次搜索将找到一个最佳解决方案 - 并且快速.
2. 如果您不关心最佳解决方案,您只需要快速找到一个解决方案 - 它通常可以解决问题(但您必须小心无限分支问题).
3. 当我们使用A*时,我们实际上使用最好的第一次搜索 - 但是f:V->R而不是on h:V->R.