用Python实现字符串匹配的模拟退火算法

import random
import math

def simulated_annealing(text, pattern, initial_solution, temperature, cooling_rate, max_iterations):
    current_solution = initial_solution
    best_solution = current_solution

    for i in range(max_iterations):
        energy = calculate_energy(text, pattern, current_solution)
        if energy == 0:
            return current_solution

        new_solution = generate_neighbor(current_solution)
        new_energy = calculate_energy(text, pattern, new_solution)

        if new_energy < energy:
            current_solution = new_solution
            if new_energy < calculate_energy(text, pattern, best_solution):
                best_solution = new_solution
        else:
            probability = math.exp((energy - new_energy) / temperature)
            if random.random() < probability:
                current_solution = new_solution

        temperature *= cooling_rate

    return best_solution

def calculate_energy(text, pattern, solution):
    # 计算当前解的能量，即模式串与文本串的不匹配程度
    energy = 0
    for i in range(len(pattern)):
        if pattern[i] != text[solution + i]:
            energy += 1
    return energy

def generate_neighbor(solution):
    # 生成当前解的邻居解，即在当前位置上随机移动一个步长
    return solution + random.randint(-1, 1)

# 示例用法
text = "This is a test string."
pattern = "test"
initial_solution = 0
temperature = 100.0
cooling_rate = 0.99
max_iterations = 1000

result = simulated_annealing(text, pattern, initial_solution, temperature, cooling_rate, max_iterations)
print("Best match found at index:", result)