algorithm - “爬山”和“分支定界”搜索算法有什么区别？

Question

爬山搜索和分支定界是人工智能中使用的两种启发式搜索算法。这两种方法有什么区别？

Answer 1

爬山搜索从对解决方案的初始猜测开始，然后迭代地对其进行局部更改，直到找到解决方案或启发式算法陷入局部最大值。有很多方法可以避免陷入局部最大值，例如并行运行多次搜索，或者概率性地选择后继状态等。在许多情况下，爬山算法会迅速收敛到正确答案。但是，这些方法都不能保证找到最佳解决方案。

分支定界解决方案的工作原理是将搜索空间切割成碎片，探索一个碎片，然后根据每次搜索期间获得的信息尝试排除搜索空间的其他部分。他们保证最终会找到最佳答案，尽管这样做可能需要很长时间。对于许多问题，基于分支定界的算法工作得很好，因为少量的信息可以迅速缩小搜索空间。

简而言之，爬山并不能保证找到正确的答案，但通常运行得非常快并给出了很好的近似值。分支定界法总能找到正确的答案，但可能需要一段时间才能做到。

希望这可以帮助！

Answer 2

爬山的工作方式如下： 带有修剪的深度优先搜索（这是一种简单的分支定界形式）的工作方式如下：

分支和绑定通常不会扩展到 1000 多个变量和 1000 多个值。爬山确实如此，但它陷入了局部最优，可以通过添加禁忌搜索来修复。