爬山算法（Hill Climbing Algorithm）是一种局部搜索算法，它通过迭代搜索的方式寻找问题的局部最优解。在爬山过程中，算法总是选择当前状态邻域中最好（即函数值最大或最小）的状态作为下一个状态，直到达到局部最优解。由于爬山算法只关注当前状态及其邻域，因此它可能会陷入局部最优解而非全局最优解。
以下是一个用C++实现的简单爬山算法示例，用于求解一元函数的局部最大值。在这个例子中，我们将使用一个简单的二次函数 `f(x) = -x^2 + 4x - 3`，它有一个全局最大值点 `x = 2`。代码如下。
#include <iostream>
#include <cmath>
#include <random>
#include <chrono>// 目标函数
double f(double x) {return -x * x + 4 * x - 3;
}// 爬山算法
double hillClimbing(double start, double stepSize, int maxIter) {double current = start;double currentVal = f(current);double next, nextVal;for (int i = 0; i < maxIter; ++i) {double left = current - stepSize;double right = current + stepSize;nextVal = std::max(f(left), f(right));if (nextVal > currentVal) {// 如果邻域中存在更好的解，则移动到该解if (f(left) > f(right)) {next = left;} else {next = right;}current = next;currentVal = nextVal;} else {// 如果没有更好的解，则停止搜索break;}}return current;
}int main() {// 设置初始点、步长和最大迭代次数double start = 0.0; // 可以随机初始化或设置为特定值double stepSize = 0.1;int maxIter = 100;// 运行爬山算法并输出结果double result = hillClimbing(start, stepSize, maxIter);std::cout << "找到最大值 x = " << result << ", f(x) = " << f(result) << std::endl;return 0;
}结果如下图所示。
上面的示例程序定义了一个简单的爬山算法实现，它接受一个初始点、步长和最大迭代次数作为输入，并返回找到的局部最大值点的x坐标。在`main`函数中，我们设置了初始点、步长和最大迭代次数，并调用`hillClimbing`函数来运行爬山算法。最后，我们输出找到的局部最大值点的x坐标和函数值。
请注意，这个示例仅用于演示爬山算法的基本原理。在实际应用中，目标函数可能更加复杂，需要更复杂的邻域搜索策略和停止条件。此外，为了获得更好的性能，还可以考虑使用更高级的局部搜索算法，如模拟退火、遗传算法等。
