启发式算法 demo

启发式算法是一种通过“试错”来搜索最优解的算法，它常被用于解决复杂的优化问题。常见的启发式算法包括遗传算法、模拟退火算法、禁忌搜索算法等。以下是一个简单的模拟退火算法的Python代码示例，用于解决旅行商问题。

import math
import random

def distance(city1, city2):
    """计算两个城市之间的距离"""
    x1, y1 = city1
    x2, y2 = city2
    return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)

def generate_neighbor(state):
    """生成当前状态的邻居状态"""
    i, j = sorted(random.sample(range(len(state)), 2))
    return state[:i] + state[j:j+1] + state[i+1:j] + state[i:i+1] + state[j+1:]

def anneal(state, temperature, cooling_rate):
    """模拟退火算法"""
    current_energy = energy(state)
    while temperature > 1:
        neighbor = generate_neighbor(state)
        neighbor_energy = energy(neighbor)
        delta = neighbor_energy - current_energy
        if delta < 0 or math.exp(-delta/temperature) > random.random():
            state, current_energy = neighbor, neighbor_energy
        temperature *= cooling_rate
    return state, current_energy

def energy(state):
    """计算状态的能量，即路径长度"""
    total_distance = 0
    for i in range(len(state)):
        total_distance += distance(state[i], state[(i + 1) % len(state)])
    return total_distance

def main():
    # 生成随机城市坐标
    cities = [(random.randint(0, 100), random.randint(0, 100)) for _ in range(10)]
    # 初始化状态为随机排列
    state = list(range(len(cities)))
    random.shuffle(state)
    # 设置初始温度和冷却速率
    temperature, cooling_rate = 1000, 0.99
    # 运行模拟退火算法
    state, energy = anneal(state, temperature, cooling_rate)
    # 输出最优解
    print("最优解：", state)
    print("路径长度：", energy)

if __name__ == '__main__':
    main()

以上代码实现了一个简单的模拟退火算法，用于解决旅行商问题。它通过随机生成城市坐标，然后随机排列城市，最后通过模拟退火算法搜索最优路径。运行代码可以得到最优路径和路径长度。