爬山算法设计与分析

前面几章讨论的算法是系统运行的。为了实现这一目标，需要存储一条或多条先前探索的解决方案路径，以找到最佳解决方案。

对于许多问题来说，实现目标的路径是无关紧要的。例如，在N皇后问题中，我们不需要关心皇后的最终配置以及皇后添加的顺序。

爬山

爬山是一种解决某些优化问题的技术。在这种技术中，我们从次优解决方案开始，并反复改进该解决方案，直到某个条件最大化。

爬山

从次优解决方案开始的想法与从山脚开始相比，改进解决方案与步行上山相比，最后最大化某些条件与到达山顶相比。

因此，爬山技术可以被视为以下阶段 -

  • 构造服从问题约束的次优解
  • 逐步改进解决方案
  • 改进解决方案，直到无法再改进为止

爬山技术主要用于解决计算难题。它只关注当前状态和近期的未来状态。因此，该技术具有内存效率，因为它不维护搜索树。

Algorithm: Hill Climbing 
Evaluate the initial state. 
Loop until a solution is found or there are no new operators left to be applied: 
   - Select and apply a new operator 
   - Evaluate the new state: 
      goal -→ quit 
      better than current state -→ new current state

迭代改进

在迭代改进方法中，最优解是通过在每次迭代中向最优解前进来实现的。然而，该技术可能会遇到局部最大值。在这种情况下，附近没有更好的解决方案。

这个问题可以通过不同的方法来避免。这些方法之一是模拟退火。

随机重启

这是解决局部最优问题的另一种方法。该技术进行一系列搜索。每次，它都从随机生成的初始状态开始。因此，比较所执行的搜索的解决方案可以获得最佳或接近最佳的解决方案。

爬山技术存在的问题

局部极大值

如果启发式不是凸的，爬山法可能会收敛到局部最大值，而不是全局最大值。

山脊和小巷

如果目标函数创建了一个狭窄的山脊，那么登山者只能通过之字形爬上山脊或下山。在这种情况下，登山者需要采取非常小的步骤，需要更多的时间才能到达目标。

高原

当搜索空间平坦或足够平坦以至于目标函数返回的值与附近区域返回的值无法区分时，就会遇到平台期，这是由于机器用来表示其值的精度所致。

爬山技术的复杂性

该技术不会遇到与空间相关的问题，因为它只查看当前状态。以前探索过的路径不会被存储。

对于随机重启爬山技术中的大多数问题，可以在多项式时间内获得最优解。然而，对于 NP 完全问题，计算时间可以根据局部最大值的数量呈指数增长。

爬山技术的应用

爬山技术可用于解决许多问题，其中当前状态允许精确的评估函数，例如网络流、旅行商问题、8皇后问题、集成电路设计等。

爬山法也用于归纳学习方法。该技术用于机器人技术，用于团队中多个机器人之间的协调。使用该技术还存在许多其他问题。

例子

该技术可用于解决旅行商问题。首先确定一个初始解决方案，即访问所有城市一次。因此，这个初始解决方案在大多数情况下都不是最佳的。即使这个解决方案也可能非常糟糕。爬山算法从这样的初始解开始，并以迭代的方式对其进行改进。最终，可能会获得更短的路线。

例子

C C++ Java Python 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define NUM_CITIES 4
// Distance matrix representing distances between cities
// Replace this with the actual distance matrix for your problem
int distance_matrix[NUM_CITIES][NUM_CITIES] = {
    {0, 10, 15, 20},
    {10, 0, 35, 25},
    {15, 35, 0, 30},
    {20, 25, 30, 0}
};
int total_distance(int* path, int num_cities) {
    // Calculate the total distance traveled in the given path
    int total = 0;
    for (int i = 0; i < num_cities - 1; i++) {
        total += distance_matrix[path[i]][path[i + 1]];
    }
    total += distance_matrix[path[num_cities - 1]][path[0]]; // Return to starting city
    return total;
}
void hill_climbing_tsp(int num_cities, int max_iterations) {
    int current_path[NUM_CITIES]; // Initial solution, visiting cities in order
    for (int i = 0; i < num_cities; i++) {
        current_path[i] = i;
    }
    int current_distance = total_distance(current_path, num_cities);
    for (int it = 0; it < max_iterations; it++) {
        // Generate a neighboring solution by swapping two random cities
        int neighbor_path[NUM_CITIES];
        for (int i = 0; i < num_cities; i++) {
            neighbor_path[i] = current_path[i];
        }
        int i = rand() % num_cities;
        int j = rand() % num_cities;
        int temp = neighbor_path[i];
        neighbor_path[i] = neighbor_path[j];
        neighbor_path[j] = temp;
        int neighbor_distance = total_distance(neighbor_path, num_cities);
        // If the neighbor solution is better, move to it
        if (neighbor_distance < current_distance) {
            for (int i = 0; i < num_cities; i++) {
                current_path[i] = neighbor_path[i];
            }
            current_distance = neighbor_distance;
        }
    }
    printf("Optimal path: ");
    for (int i = 0; i < num_cities; i++) {
        printf("%d ", current_path[i]);
    }
    printf("\nTotal distance: %d\n", current_distance);
}
int main() {
    srand(time(NULL));
    int max_iterations = 10000;
    hill_climbing_tsp(NUM_CITIES, max_iterations);
    return 0;
}

输出

Optimal path: 1 0 2 3 
Total distance: 80

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#define NUM_CITIES 4
// Distance matrix representing distances between cities
// Replace this with the actual distance matrix for your problem
int distance_matrix[NUM_CITIES][NUM_CITIES] = {
    {0, 10, 15, 20},
    {10, 0, 35, 25},
    {15, 35, 0, 30},
    {20, 25, 30, 0}
};
int total_distance(const std::vector<int>& path) {
    // Calculate the total distance traveled in the given path
    int total = 0;
    for (size_t i = 0; i < path.size() - 1; i++) {
        total += distance_matrix[path[i]][path[i + 1]];
    }
    total += distance_matrix[path.back()][path[0]]; // Return to starting city
    return total;
}
void hill_climbing_tsp(int num_cities, int max_iterations) {
    std::vector<int> current_path(num_cities); // Initial solution, visiting cities in order
    for (int i = 0; i < num_cities; i++) {
        current_path[i] = i;
    }
    int current_distance = total_distance(current_path);
    for (int it = 0; it < max_iterations; it++) {
        // Generate a neighboring solution by swapping two random cities
        std::vector<int> neighbor_path = current_path;
        int i = rand() % num_cities;
        int j = rand() % num_cities;
        std::swap(neighbor_path[i], neighbor_path[j]);
        int neighbor_distance = total_distance(neighbor_path);
        // If the neighbor solution is better, move to it
        if (neighbor_distance < current_distance) {
            current_path = neighbor_path;
            current_distance = neighbor_distance;
        }
    }
    std::cout << "Optimal path: ";
    for (int city : current_path) {
        std::cout << city << " ";
    }
    std::cout << std::endl;
    std::cout << "Total distance: " << current_distance << std::endl;
}
int main() {
    srand(time(NULL));
    int max_iterations = 10000;
    hill_climbing_tsp(NUM_CITIES, max_iterations);
    return 0;
}

输出

Optimal path: 0 1 3 2 
Total distance: 80

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class HillClimbingTSP {
    private static final int NUM_CITIES = 4;
    // Distance matrix representing distances between cities
    // Replace this with the actual distance matrix for your problem
    private static final int[][] distanceMatrix = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };
    private static int totalDistance(List<Integer> path) {
        // Calculate the total distance traveled in the given path
        int total = 0;
        for (int i = 0; i < path.size() - 1; i++) {
            total += distanceMatrix[path.get(i)][path.get(i + 1)];
        }
        total += distanceMatrix[path.get(path.size() - 1)][path.get(0)]; // Return to starting city
        return total;
    }
    private static List<Integer> generateRandomPath(int numCities) {
        List<Integer> path = new ArrayList<>();
        for (int i = 0; i < numCities; i++) {
            path.add(i);
        }
        Random rand = new Random();
        for (int i = numCities - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            int temp = path.get(i);
            path.set(i, path.get(j));
            path.set(j, temp);
        }
        return path;
    }
    public static void hillClimbingTSP(int numCities, int maxIterations) {
        List<Integer> currentPath = generateRandomPath(numCities); // Initial solution
        int currentDistance = totalDistance(currentPath);
        for (int it = 0; it < maxIterations; it++) {
            // Generate a neighboring solution by swapping two random cities
            List<Integer> neighborPath = new ArrayList<>(currentPath);
            int i = new Random().nextInt(numCities);
            int j = new Random().nextInt(numCities);
            int temp = neighborPath.get(i);
            neighborPath.set(i, neighborPath.get(j));
            neighborPath.set(j, temp);
            int neighborDistance = totalDistance(neighborPath);
            // If the neighbor solution is better, move to it
            if (neighborDistance < currentDistance) {
                currentPath = neighborPath;
                currentDistance = neighborDistance;
            }
        }
        System.out.print("Optimal path: ");
        for (int city : currentPath) {
            System.out.print(city + " ");
        }
        System.out.println();
        System.out.println("Total distance: " + currentDistance);
    }
    public static void main(String[] args) {
        int maxIterations = 10000;
        hillClimbingTSP(NUM_CITIES, maxIterations);
    }
}

输出

Optimal path: 1 3 2 0 
Total distance: 80

import random
# Distance matrix representing distances between cities
# Replace this with the actual distance matrix for your problem
distance_matrix = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]
def total_distance(path):
    # Calculate the total distance traveled in the given path
    total = 0
    for i in range(len(path) - 1):
        total += distance_matrix[path[i]][path[i+1]]
    total += distance_matrix[path[-1]][path[0]]  # Return to starting city
    return total
def hill_climbing_tsp(num_cities, max_iterations=10000):
    current_path = list(range(num_cities))  # Initial solution, visiting cities in order
    current_distance = total_distance(current_path) 
    for _ in range(max_iterations):
        # Generate a neighboring solution by swapping two random cities
        neighbor_path = current_path.copy()
        i, j = random.sample(range(num_cities), 2)
        neighbor_path[i], neighbor_path[j] = neighbor_path[j], neighbor_path[i]
        neighbor_distance = total_distance(neighbor_path)
        
        # If the neighbor solution is better, move to it
        if neighbor_distance < current_distance:
            current_path = neighbor_path
            current_distance = neighbor_distance
    return current_path
def main():
    num_cities = 4  # Number of cities in the TSP
    solution = hill_climbing_tsp(num_cities)
    print("Optimal path:", solution)
    print("Total distance:", total_distance(solution))
if __name__ == "__main__":
    main()

输出

Optimal path: [1, 0, 2, 3]
Total distance: 80