人工智能爬山算法 - 人工智能（AI）教程

爬山(Hill Climbing)算法是一种局部搜索算法，它在增加高度/值的方向上连续移动，以找到山峰或最佳解决问题的方法。它在达到峰值时终止，其中没有邻居具有更高的值。
爬山算法是一种用于优化数学问题的技术。其中一个广泛讨论的爬山算法的例子是旅行商问题，其中我们需要最小化推销员的行进距离。
它也称为贪婪的本地搜索，因为它只关注其良好的直接邻居状态而不是超越它。爬山算法的节点有两个组成部分，即状态和值。
Hill Climbing主要用于有良好启发式的时候。在此算法中，不需要维护和处理搜索树或图形，因为它只保留单个当前状态。

爬山算法的特点

以下是爬山算法的一些主要特征：

生成和测试变体：Hill Climbing是Generate和Test方法的变体。生成和测试方法产生反馈，有助于确定在搜索空间中移动的方向。
贪婪的方法：爬山算法搜索朝着优化成本的方向发展。
没有回溯：它不会回溯搜索空间，因为它不记得以前的状态。

爬山的国家空间图

状态空间景观是爬山算法的图形表示，其示出了算法的各种状态和目标函数/成本之间的图。

在Y轴上，我们采用了可以是目标函数或成本函数的函数，以及x轴上的状态空间。如果Y轴上的函数是成本，那么搜索的目标是找到全局最小值和局部最小值。如果Y轴的函数是目标函数，那么搜索的目标是找到全局最大值和局部最大值。

人工智能爬山算法

状态的不同区域

局部最大值：局部最大值是一个比其邻居状态更好的状态，但也有另一个高于它的状态。
全局最大值：全局最大值是状态空间最佳状态。它具有最高的目标函数值。
当前状态：它是当前存在代理的横向图中的状态。
平局局部最大值：它是景观中的平坦空间，其中当前状态的所有邻居状态具有相同的值。
肩部：这是一个具有上坡边缘的高原地区。

爬山类型算法：

简单爬山
Steepest-Ascent爬山
随机爬山

1 简单爬山

简单的爬山是实现爬山算法的最简单方法。它一次只评估邻居节点状态，并选择第一个优化当前成本并将其设置为当前状态的状态。它只检查它的一个后继状态，如果它发现优于当前状态，则移动其他状态。该算法具有以下特征：

减少耗时
不太保证不太理想的解决方案和解决方案

简易爬山算法：

步骤1：评估初始状态，如果是目标状态，则返回成功并停止。
步骤1：循环直到找到解决方案或没有新的运算符可供应用。
步骤3：选择并将运算符应用于当前状态。
步骤4：检查新状态：
- 如果是目标状态，则返回成功并退出。
- 否则，如果它优于当前状态，则将新状态指定为当前状态。
- 否则如果不比当前状态好，则返回步骤2。
步骤5：退出

Steepest-Ascent爬坡：

最陡峭的Ascent算法是简单爬山算法的变体。该算法检查当前状态的所有相邻节点，并选择最接近目标状态的一个邻居节点。该算法在搜索多个邻居时会消耗更多时间

最速爬坡爬山算法：

步骤1：评估初始状态，如果是目标状态，则返回成功并停止，否则将当前状态作为初始状态。
步骤2：循环直到找到解决方案或当前状态不变。
- 让SUCC成为一个状态，使得当前状态的任何继承者都会比它更好。
- 对于适用于当前状态的每个运算符：
  - 应用new运算符并生成新状态。
  - 评估新的状态。
  - 如果是目标状态，则返回并退出，否则将其与SUCC进行比较。
  - 如果它优于SUCC，则将新状态设置为SUCC。
  - 如果SUCC优于当前状态，则将当前状态设置为SUCC。
步骤3：退出

随机爬山：

随机爬山在移动之前不会检查其所有邻居。相反，该搜索算法随机选择一个邻居节点并决定是将其选择为当前状态还是检查另一个状态。