算法——结合实例了解启发式搜索

一、启发式搜索相关思想

启发式搜索是一类基于估计值（启发式函数）来指导搜索的算法。其基本思想是利用启发信息来指导搜索过程，从而加速搜索并找到解决方案或更接近目标的解。启发信息通常由启发函数提供，该函数能够评估节点的重要性或接近目标的程度。在搜索过程中，启发式搜索算法会优先扩展那些更有可能包含解或更接近目标的节点，从而显著提高搜索效率。

二、启发式搜索技术

启发式搜索技术在计算机科学和人工智能领域有着广泛的应用，常见的启发式搜索算法包括A*算法、贪心算法等。以下是一些关键的技术要点：

1. 状态表示：定义问题的状态表示方式，通常是一个数据结构，其中包含描述问题状态的所有必要信息。
2. 启发式函数：实现一个启发式函数，用于评估当前状态到目标状态的距离或成本的估计。启发式函数的设计需要根据具体问题的特点，可以基于问题的领域知识或者简单的规则。
3. 搜索策略：选择适合问题的搜索策略，常见的搜索策略包括A算法、IDA算法、Greedy Best-First Search等。
4. 状态扩展：实现状态扩展操作，根据当前状态生成可能的后继状态。这通常涉及到问题定义中的状态转移操作。
5. 搜索控制：实现搜索控制机制，用于管理搜索过程。这可能包括设置搜索深度限制、时间限制、启发式函数的阈值等，以控制搜索的规模和复杂度。

三、实例代码

贪心算法

• 原理：在对问题求解时，总是做出在当前看来是最好的选择，不考虑整体最优，只考虑局部最优。
• 实例：找零问题。假设有面值为5元、2元、1元、5角、2角、1角的硬币，要找给顾客9元8角。贪心算法的思路是每次都选择面值最大的硬币，先选1个5元硬币，再选2个2元硬币，然后选1个5角硬币，1个2角硬币和1个1角硬币，这样就用最少的硬币数量完成了找零。
  

def greedy_change(amount):
    coins = [500, 200, 100, 50, 20, 10]  # 硬币面值，单位为角
    coin_count = [0] * len(coins)
    for i, coin in enumerate(coins):
        while amount >= coin:
            amount -= coin
            coin_count[i] += 1
    return coin_count

amount = 980  # 9 元 8 角，单位为角
result = greedy_change(amount)
coin_names = ["5 元", "2 元", "1 元", "5 角", "2 角", "1 角"]
for i in range(len(result)):
    if result[i] > 0:
        print(f"{coin_names[i]}: {result[i]} 个")

A*算法

• 原理：综合考虑节点的路径代价和到目标节点的估计代价，通过评估函数(f(n)=g(n)+h(n))来选择下一个要扩展的节点，其中(g(n))是从起始节点到节点(n)的实际代价，(h(n))是从节点(n)到目标节点的估计代价。
• 实例：在地图导航中，要从A地到B地，A算法会根据当前位置到已走过位置的距离(g(n))，以及当前位置到B地的直线距离估计值(h(n))（启发函数）来选择下一个要走的节点。比如在一个城市道路网络中，计算从当前路口到目标路口的最短路径，A算法会综合考虑已经走过的路程和到目标路口的直线距离等因素，快速找到最优路径。
  

import heapq

# 定义节点类
class Node:
    def __init__(self, x, y, g=float('inf'), h=float('inf'), parent=None):
        self.x = x
        self.y = y
        self.g = g
        self.h = h
        self.f = g + h
        self.parent = parent

    def __lt__(self, other):
        return self.f < other.f

# 曼哈顿距离作为启发函数
def heuristic(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

# A* 算法实现
def a_star(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    open_list = []
    closed_set = set()

    start_node = Node(start[0], start[1], 0, heuristic(start, goal))
    heapq.heappush(open_list, start_node)

    while open_list:
        current = heapq.heappop(open_list)
        if (current.x, current.y) == goal:
            path = []
            while current:
                path.append((current.x, current.y))
                current = current.parent
            return path[::-1]

        closed_set.add((current.x, current.y))
        neighbors = [(current.x + dx, current.y + dy) for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]
                     if 0 <= current.x + dx < rows and 0 <= current.y + dy < cols and grid[current.x + dx][current.y + dy] == 0]

        for neighbor in neighbors:
            if neighbor in closed_set:
                continue
            tentative_g = current.g + 1
            neighbor_node = Node(neighbor[0], neighbor[1])
            if tentative_g < neighbor_node.g:
                neighbor_node.parent = current
                neighbor_node.g = tentative_g
                neighbor_node.h = heuristic(neighbor, goal)
                neighbor_node.f = neighbor_node.g + neighbor_node.h
                heapq.heappush(open_list, neighbor_node)

    return None

# 示例网格地图，0 表示可通行，1 表示障碍物
grid = [
    [0, 0, 0, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0]
]
start = (0, 0)
goal = (3, 3)
path = a_star(grid, start, goal)
print("A* 算法找到的路径:", path)

遗传算法

• 原理：模拟生物在自然环境中的遗传和进化过程，通过选择、交叉和变异等操作，不断迭代优化种群，以找到最优解或近似最优解。
• 实例：在生产调度问题中，假设有多个订单需要在不同的机器上加工，每个订单有不同的加工时间和交货期。遗传算法可以将每个调度方案看作一个个体，通过对个体进行编码，如用数字序列表示订单在机器上的加工顺序。然后计算每个个体的适应度，比如根据订单的延迟交货时间等指标来衡量。在迭代过程中，选择适应度高的个体进行交叉和变异操作，产生新的后代个体，经过多代进化，逐渐找到使整体生产效率最高、延迟交货最少的调度方案。

import random
import copy

# 订单加工时间
job_processing_times = [2, 3, 4, 5]
num_jobs = len(job_processing_times)
num_machines = 1
population_size = 10
generations = 50

# 生成初始种群
def generate_population():
    population = []
    for _ in range(population_size):
        individual = list(range(num_jobs))
        random.shuffle(individual)
        population.append(individual)
    return population

# 计算适应度（总加工时间）
def fitness(individual):
    total_time = 0
    for job in individual:
        total_time += job_processing_times[job]
    return total_time

# 选择操作（锦标赛选择）
def tournament_selection(population):
    tournament_size = 3
    tournament = random.sample(population, tournament_size)
    best = min(tournament, key=lambda x: fitness(x))
    return best

# 交叉操作（顺序交叉）
def order_crossover(parent1, parent2):
    start, end = sorted(random.sample(range(num_jobs), 2))
    child = [-1] * num_jobs
    child[start:end] = parent1[start:end]
    remaining = [job for job in parent2 if job not in child[start:end]]
    index = 0
    for i in range(num_jobs):
        if child[i] == -1:
            child[i] = remaining[index]
            index += 1
    return child

# 变异操作（交换变异）
def swap_mutation(individual):
    index1, index2 = random.sample(range(num_jobs), 2)
    individual[index1], individual[index2] = individual[index2], individual[index1]
    return individual

# 遗传算法主循环
population = generate_population()
for _ in range(generations):
    new_population = []
    for _ in range(population_size):
        parent1 = tournament_selection(population)
        parent2 = tournament_selection(population)
        child = order_crossover(parent1, parent2)
        if random.random() < 0.1:
            child = swap_mutation(child)
        new_population.append(child)
    population = new_population

best_schedule = min(population, key=lambda x: fitness(x))
print("遗传算法找到的最优调度:", best_schedule)
print("最优调度的总加工时间:", fitness(best_schedule))

模拟退火算法

• 原理：模拟固体退火过程，在高温时，固体内部粒子处于快速运动状态，随着温度逐渐降低，粒子的运动逐渐稳定，最终达到能量最低的状态。在搜索过程中，以一定的概率接受比当前解更差的解，避免陷入局部最优。
• 实例：在旅行商问题（TSP）中，假设有一个旅行商需要访问多个城市，要求找到一条总路程最短的路径。模拟退火算法从一个初始路径开始，然后随机生成一个新的路径。如果新路径的长度比当前路径短，就接受新路径；如果新路径比当前路径长，就以一定的概率接受它。这个概率会随着算法的进行而逐渐降低，就像温度逐渐降低一样。例如，在初始阶段，可能会接受一些较长的路径，以便能够探索到更广阔的解空间，随着时间推移，接受较差解的概率越来越小，最终收敛到一个较优的路径。

import random
import math

# 城市坐标
cities = [(0, 0), (1, 5), (2, 3), (5, 1), (6, 4)]
num_cities = len(cities)

# 计算路径长度
def path_length(path):
    length = 0
    for i in range(num_cities - 1):
        x1, y1 = cities[path[i]]
        x2, y2 = cities[path[i + 1]]
        length += math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
    # 回到起点
    x1, y1 = cities[path[-1]]
    x2, y2 = cities[path[0]]
    length += math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
    return length

# 模拟退火算法
def simulated_annealing():
    current_path = list(range(num_cities))
    random.shuffle(current_path)
    current_length = path_length(current_path)
    temperature = 1000
    cooling_rate = 0.99

    while temperature > 1:
        new_path = copy.copy(current_path)
        index1, index2 = random.sample(range(num_cities), 2)
        new_path[index1], new_path[index2] = new_path[index2], new_path[index1]
        new_length = path_length(new_path)
        if new_length < current_length or random.random() < math.exp((current_length - new_length) / temperature):
            current_path = new_path
            current_length = new_length
        temperature *= cooling_rate

    return current_path, current_length

best_path, best_length = simulated_annealing()
print("模拟退火算法找到的最优路径:", best_path)
print("最优路径的长度:", best_length)

蚁群算法

• 原理：模拟蚂蚁群体寻找食物的行为，蚂蚁在运动过程中会在路径上留下信息素，信息素浓度越高的路径，被蚂蚁选择的概率越大，通过信息素的更新和扩散，引导蚂蚁群体找到最优路径。
• 实例：同样在解决TSP问题时，假设城市之间的道路是蚂蚁可以行走的路径。一开始，蚂蚁随机选择路径行走，在走过的路径上留下信息素。随着时间的推移，信息素会逐渐挥发，但较短路径上的信息素浓度会相对较高，因为蚂蚁在较短路径上往返的次数更多。这样，后续的蚂蚁选择较短路径的概率就会更大，最终整个蚁群会逐渐找到一条近似最优的旅行路线。
  

import random
import math

# 城市坐标
cities = [(0, 0), (1, 5), (2, 3), (5, 1), (6, 4)]
num_cities = len(cities)
num_ants = 10
iterations = 50
alpha = 1  # 信息素重要程度因子
beta = 2   # 启发式因子
rho = 0.5  # 信息素挥发因子
Q = 100    # 信息素增加强度系数

// 计算城市间距离
distance_matrix = [[0] * num_cities for _ in range(num_cities)]
for i in range(num_cities):
    for j in range(num_cities):
        x1, y1 = cities[i]
        x2, y2 = cities[j]
        distance_matrix[i][j] = math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

# 初始化信息素矩阵
pheromone_matrix = [[1] * num_cities for _ in range(num_cities)]

# 蚁群算法
best_path = None
best_length = float('inf')
for _ in range(iterations):
    all_paths = []
    all_lengths = []
    for _ in range(num_ants):
        current_city = random.randint(0, num_cities - 1)
        unvisited_cities = set(range(num_cities))
        unvisited_cities.remove(current_city)
        path = [current_city]
        while unvisited_cities:
            probabilities = []
            total_probability = 0
            for city in unvisited_cities:
                probability = (pheromone_matrix[current_city][city] ** alpha) * ((1 / distance_matrix[current_city][city]) ** beta)
                probabilities.append(probability)
                total_probability += probability
            if total_probability == 0:
                next_city = random.choice(list(unvisited_cities))
            else:
                probabilities = [p / total_probability for p in probabilities]
                next_city = random.choices(list(unvisited_cities), weights=probabilities)[0]
            path.append(next_city)
            unvisited_cities.remove(next_city)
            current_city = next_city
        path_length = 0
        for i in range(num_cities - 1):
            path_length += distance_matrix[path[i]][path[i + 1]]
        path_length += distance_matrix[path[-1]][path[0]]
        all_paths.append(path)
        all_lengths.append(path_length)
        if path_length < best_length:
            best_length = path_length
            best_path = path

    # 更新信息素矩阵
    for i in range(num_cities):
        for j in range(num_cities):
            pheromone_matrix[i][j] *= (1 - rho)
    for path, length in zip(all_paths, all_lengths):
        for i in range(num_cities - 1):
            pheromone_matrix[path[i]][path[i + 1]] += Q / length
        pheromone_matrix[path[-1]][path[0]] += Q / length

print("蚁群算法找到的最优路径:", best_path)
print("最优路径的长度:", best_length)

# 总结
启发式搜索通过领域知识显著提升搜索效率，但其成功依赖于合理的启发式函数设计。实际应用中需结合问题特性，灵活选择算法（如A*、IDA*、束搜索等），并持续优化启发式的准确性与计算成本。未来，随着机器学习的发展，数据驱动的启发式设计（如深度强化学习）将成为重要方向，进一步扩展启发式搜索的应用边界。