启发式算法教程(个人总结版)

2024-06-03 19:20

本文主要是介绍启发式算法教程(个人总结版),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. 引言

1.1 什么是启发式算法

启发式算法是一类用于寻找复杂优化问题近似解的方法,特别适用于在计算资源有限的情况下求解大型问题。与精确算法不同,启发式算法不保证找到全局最优解,但能在可接受的时间内提供一个质量较高的解。

1.2 启发式算法的应用领域

启发式算法广泛应用于诸多领域,包括但不限于:

  • 工程设计:如结构优化和电路设计。
  • 生产调度:如车间作业调度和生产计划优化。
  • 物流配送:如车辆路径优化和仓库选址。
  • 网络优化:如网络路由和拓扑设计。
  • 机器学习:如参数调优和特征选择。
1.3 启发式算法与精确算法的区别

精确算法(如动态规划、线性规划)能在有限时间内找到问题的最优解,但其计算复杂度较高,难以应对大规模问题。启发式算法通过经验和启发式规则,在合理时间内找到近似最优解,具有计算速度快、适应性强的优点。

2. 启发式算法的类型及基本概念

2.1 局部搜索算法

局部搜索算法从一个初始解出发,通过邻域搜索找到更好的解,直到没有更好的邻域解。

  • 基本概念:解空间、邻域结构、局部最优解。
  • 应用实例:解决旅行商问题(TSP)。
  • 算法实现
    def local_search(schedule):best_schedule = schedulebest_cost = calculate_cost(schedule)while True:neighbors = generate_neighbors(schedule)improved = Falsefor neighbor in neighbors:cost = calculate_cost(neighbor)if cost < best_cost:best_schedule = neighborbest_cost = costimproved = Trueif not improved:breakreturn best_schedule, best_cost
    
2.2 模拟退火算法

模拟退火算法模拟物理退火过程,通过控制温度逐渐降低的策略寻找全局最优解。

  • 基本概念:退火过程、温度控制策略、接受概率。
  • 应用实例:生产调度问题。
  • 算法实现
    import random
    import mathdef simulated_annealing(tsp, initial_temp, cooling_rate, stop_temp):current_solution = random.sample(tsp, len(tsp))current_temp = initial_tempbest_solution = current_solutionbest_cost = calculate_cost(current_solution)while current_temp > stop_temp:new_solution = generate_new_solution(current_solution)new_cost = calculate_cost(new_solution)if new_cost < best_cost or accept_new_solution(best_cost, new_cost, current_temp):current_solution = new_solutionbest_cost = new_costbest_solution = current_solutioncurrent_temp *= cooling_ratereturn best_solution, best_costdef calculate_cost(solution):cost = 0for i in range(len(solution) - 1):cost += distance(solution[i], solution[i+1])cost += distance(solution[-1], solution[0])return costdef generate_new_solution(solution):new_solution = solution[:]i, j = random.sample(range(len(solution)), 2)new_solution[i], new_solution[j] = new_solution[j], new_solution[i]return new_solutiondef accept_new_solution(best_cost, new_cost, temp):return math.exp((best_cost - new_cost) / temp) > random.random()def distance(city1, city2):return math.sqrt((city1[0] - city2[0])**2 + (city1[1] - city2[1])**2)tsp = [(0, 0), (1, 2), (3, 5), (6, 1), (7, 7), (8, 8), (10, 10)]
    initial_temp = 1000
    cooling_rate = 0.995
    stop_temp = 1
    best_solution, best_cost = simulated_annealing(tsp, initial_temp, cooling_rate, stop_temp)
    print(f"最优路径: {best_solution}, 最短距离: {best_cost}")
    
2.3 遗传算法

遗传算法通过模拟生物进化过程,通过选择、交叉、变异等操作优化种群,寻找最优解。

  • 基本概念:种群、适应度函数、选择、交叉、变异。
  • 应用实例:机器学习中的特征选择。
  • 算法实现
    import randomdef genetic_algorithm(func, bounds, pop_size, generations, crossover_rate, mutation_rate):population = [random_individual(bounds) for _ in range(pop_size)]best_individual = max(population, key=lambda ind: func(ind))for _ in range(generations):selected = selection(population, func)offspring = crossover(selected, crossover_rate)population = mutation(offspring, mutation_rate, bounds)current_best = max(population, key=lambda ind: func(ind))if func(current_best) > func(best_individual):best_individual = current_bestreturn best_individualdef random_individual(bounds):return [random.uniform(bound[0], bound[1]) for bound in bounds]def selection(population, func):total_fitness = sum(func(ind) for ind in population)probabilities = [func(ind) / total_fitness for ind in population]selected = random.choices(population, probabilities, k=len(population))return selecteddef crossover(population, rate):offspring = []for i in range(0, len(population), 2):parent1, parent2 = population[i], population[i+1]if random.random() < rate:point = random.randint(1, len(parent1)-1)child1 = parent1[:point] + parent2[point:]child2 = parent2[:point] + parent1[point:]offspring.extend([child1, child2])else:offspring.extend([parent1, parent2])return offspringdef mutation(population, rate, bounds):for individual in population:if random.random() < rate:point = random.randint(0, len(individual)-1)individual[point] = random.uniform(bounds[point][0], bounds[point][1])return populationdef func(x):return -(x[0]**2 + x[1]**2) + 10bounds = [(-5, 5), (-5, 5)]
    pop_size = 50
    generations = 100
    crossover_rate = 0.8
    mutation_rate = 0.05
    best_solution = genetic_algorithm(func, bounds, pop_size, generations, crossover_rate, mutation_rate)
    print(f"最优解: {best_solution}, 目标函数值: {func(best_solution)}")
    

2.4 蚁群算法

蚁群算法模拟蚂蚁觅食行为,通过信息素的积累和挥发机制优化路径选择。

  • 基本概念:信息素更新、路径选择、挥发率。
  • 应用实例:网络路由优化。
  • 算法实现
    import randomdef ant_colony_optimization(graph, num_ants, num_iterations, alpha, beta, evaporation_rate):num_nodes = len(graph)pheromones = [[1 / num_nodes for _ in range(num_nodes)] for _ in range(num_nodes)]best_solution = Nonebest_cost = float('inf')for _ in range(num_iterations):solutions = []for _ in range(num_ants):solution = generate_solution(graph, pheromones, alpha, beta)solutions.append(solution)update_pheromones(pheromones, solutions, evaporation_rate)for solution in solutions:cost = calculate_cost(solution, graph)if cost < best_cost:best_cost = costbest_solution = solutionreturn best_solution, best_costdef generate_solution(graph, pheromones, alpha, beta):solution = []current_node = random.randint(0, len(graph) - 1)solution.append(current_node)while len(solution) < len(graph):probabilities = []for next_node in range(len(graph)):if next_node not in solution:pheromone = pheromones[current_node][next_node] ** alphadistance = 1 / graph[current_node][next_node] ** betaprobabilities.append((next_node, pheromone * distance))total_prob = sum(prob for _, prob in probabilities)probabilities = [(node, prob / total_prob) for node, prob in probabilities]next_node = random.choices([node for node, _ in probabilities], [prob for _, prob in probabilities])[0]solution.append(next_node)current_node = next_nodereturn solutiondef update_pheromones(pheromones, solutions, evaporation_rate):for i in range(len(pheromones)):for j in range(len(pheromones[i])):pheromones[i][j] *= (1 - evaporation_rate)for solution in solutions:for i in range(len(solution) - 1):pheromones[solution[i]][solution[i+1]] += 1 / calculate_cost(solution)def calculate_cost(solution, graph):cost = 0for i in range(len(solution) - 1):cost += graph[solution[i]][solution[i+1]]return costgraph = [[0, 2, 2, 5, 7],[2, 0, 4, 8, 2],[2, 4, 0, 1, 3],[5, 8, 1, 0, 2],[7, 2, 3, 2, 0]
    ]num_ants = 10
    num_iterations = 100
    alpha = 1
    beta = 2
    evaporation_rate = 0.5
    best_solution, best_cost = ant_colony_optimization(graph, num_ants, num_iterations, alpha, beta, evaporation_rate)
    print(f"最优路径: {best_solution}, 最小代价: {best_cost}")
    
2.5 粒子群优化算法

粒子群优化算法(Particle Swarm Optimization, PSO)通过模拟鸟群觅食行为,通过粒子间的信息交流和协同搜索最优解。

  • 基本概念:粒子、速度更新、位置更新。
  • 应用实例:多目标优化问题。
  • 算法实现
    import randomdef particle_swarm_optimization(func, bounds, num_particles, num_iterations, w, c1, c2):particles = [random_particle(bounds) for _ in range(num_particles)]global_best = max(particles, key=lambda p: func(p['position']))for _ in range(num_iterations):for particle in particles:update_velocity(particle, global_best, w, c1, c2)update_position(particle, bounds)if func(particle['position']) > func(particle['best_position']):particle['best_position'] = particle['position']global_best = max(particles, key=lambda p: func(p['best_position']))return global_best['position']def random_particle(bounds):position = [random.uniform(bound[0], bound[1]) for bound in bounds]velocity = [random.uniform(-abs(bound[1] - bound[0]), abs(bound[1] - bound[0])) for bound in bounds]return {'position': position, 'velocity': velocity, 'best_position': position}def update_velocity(particle, global_best, w, c1, c2):for i in range(len(particle['velocity'])):r1, r2 = random.random(), random.random()particle['velocity'][i] = (w * particle['velocity'][i] +c1 * r1 * (particle['best_position'][i] - particle['position'][i]) +c2 * r2 * (global_best['position'][i] - particle['position'][i]))def update_position(particle, bounds):for i in range(len(particle['position'])):particle['position'][i] += particle['velocity'][i]particle['position'][i] = min(max(particle['position'][i], bounds[i][0]), bounds[i][1])def func(x):return -(x[0]**2 + x[1]**2) + 10bounds = [(-5, 5), (-5, 5)]
    num_particles = 30
    num_iterations = 100
    w = 0.5
    c1 = 1.5
    c2 = 1.5
    best_solution = particle_swarm_optimization(func, bounds, num_particles, num_iterations, w, c1, c2)
    print(f"最优解: {best_solution}, 目标函数值: {func(best_solution)}")
    

3. 启发式算法的改进与优化

3.1 混合启发式算法

混合启发式算法是将多种启发式算法结合,发挥各算法优势,提高求解效果。这种方法可以利用一种算法的全局搜索能力和另一种算法的局部搜索能力,达到更好的求解效果。

  • 应用实例:将模拟退火算法与遗传算法结合,解决复杂优化问题。
    • 算法实现:先使用遗传算法进行种群进化,得到一组优秀的解,再使用模拟退火算法对这些解进行局部优化,从而找到全局最优解。
3.2 参数调优

参数调优是通过实验调整算法参数,以提高算法性能。不同的参数设置会对算法的收敛速度和求解质量产生重大影响。

  • 应用实例:在遗传算法中调优交叉概率和变异概率。
    • 实验步骤
      1. 选择初始参数值。
      2. 运行算法并记录结果。
      3. 调整参数值,重复运行并记录结果。
      4. 比较结果,选择最佳参数组合。
3.3 自适应启发式算法

自适应启发式算法根据问题特性自动调整参数,提高算法适应性和求解效果。通过引入自适应机制,算法可以在运行过程中动态调整参数,使其更好地适应当前问题的特性。

  • 应用实例:自适应模拟退火算法。
    • 算法实现:根据当前解的变化情况动态调整温度控制参数,提高算法的自适应性和求解效果。

4. 启发式算法在实际问题中的应用

4.1 启发式算法在物流优化中的应用

启发式算法在物流优化中的应用广泛,主要包括配送路径优化和库存管理等方面。

  • 应用实例:使用蚁群算法优化物流配送路径。
    • 问题描述:在一个城市内,有多个配送点,要求找到一条最短的配送路径,使总配送时间最短。
    • 算法实现
      import randomdef ant_colony_optimization(graph, num_ants, num_iterations, alpha, beta, evaporation_rate):num_nodes = len(graph)pheromones = [[1 / num_nodes for _ in range(num_nodes)] for _ in range(num_nodes)]best_solution = Nonebest_cost = float('inf')for _ in range(num_iterations):solutions = []for _ in range(num_ants):solution = generate_solution(graph, pheromones, alpha, beta)solutions.append(solution)update_pheromones(pheromones, solutions, evaporation_rate)for solution in solutions:cost = calculate_cost(solution, graph)if cost < best_cost:best_cost = costbest_solution = solutionreturn best_solution, best_costdef generate_solution(graph, pheromones, alpha, beta):solution = []current_node = random.randint(0, len(graph) - 1)solution.append(current_node)while len(solution) < len(graph):probabilities = []for next_node in range(len(graph)):if next_node not in solution:pheromone = pheromones[current_node][next_node] ** alphadistance = 1 / graph[current_node][next_node] ** betaprobabilities.append((next_node, pheromone * distance))total_prob = sum(prob for _, prob in probabilities)probabilities = [(node, prob / total_prob) for node, prob in probabilities]next_node = random.choices([node for node, _ in probabilities], [prob for _, prob in probabilities])[0]solution.append(next_node)current_node = next_nodereturn solutiondef update_pheromones(pheromones, solutions, evaporation_rate):for i in range(len(pheromones)):for j in range(len(pheromones[i])):pheromones[i][j] *= (1 - evaporation_rate)for solution in solutions:for i in range(len(solution) - 1):pheromones[solution[i]][solution[i+1]] += 1 / calculate_cost(solution)def calculate_cost(solution, graph):cost = 0for i in range(len(solution) - 1):cost += graph[solution[i]][solution[i+1]]return costgraph = [[0, 2, 2, 5, 7],[2, 0, 4, 8, 2],[2, 4, 0, 1, 3],[5, 8, 1, 0, 2],[7, 2, 3, 2, 0]
      ]num_ants = 10
      num_iterations = 100
      alpha = 1
      beta = 2
      evaporation_rate = 0.5
      best_solution, best_cost = ant_colony_optimization(graph, num_ants, num_iterations, alpha, beta, evaporation_rate)
      print(f"最优路径: {best_solution}, 最小代价: {best_cost}")
      
4.2 启发式算法在网络设计中的应用

启发式算法在网络设计中的应用包括网络路由优化和网络拓扑设计。

  • 应用实例:使用粒子群优化算法优化网络路由。
    • 问题描述:在一个计算机网络中,有多个路由节点,要求找到一条最优的路由,使数据传输延迟最小。
    • 算法实现
      import randomdef particle_swarm_optimization(func, bounds, num_particles, num_iterations, w, c1, c2):particles = [random_particle(bounds) for _ in range(num_particles)]global_best = max(particles, key=lambda p: func(p['position']))for _ in range(num_iterations):for particle in particles:update_velocity(particle, global_best, w, c1, c2)update_position(particle, bounds)if func(particle['position']) > func(particle['best_position']):particle['best_position'] = particle['position']global_best = max(particles, key=lambda p: func(p['best_position']))return global_best['position']def random_particle(bounds):position = [random.uniform(bound[0], bound[1]) for bound in bounds]velocity = [random.uniform(-abs(bound[1] - bound[0]), abs(bound[1] - bound[0])) for bound in bounds]return {'position': position, 'velocity': velocity, 'best_position': position}def update_velocity(particle, global_best, w, c1, c2):for i in range(len(particle['velocity'])):r1, r2 = random.random(), random.random()particle['velocity'][i] = (w * particle['velocity'][i] +c1 * r1 * (particle['best_position'][i] - particle['position'][i]) +c2 * r2 * (global_best['position'][i] - particle['position'][i]))def update_position(particle, bounds):for i in range(len(particle['position'])):particle['position'][i] += particle['velocity'][i]particle['position'][i] = min(max(particle['position'][i], bounds[i][0]), bounds[i][1])def func(x):return -(x[0]**2 + x[1]**2) + 10bounds = [(-5, 5), (-5, 5)]
      num_particles = 30
      num_iterations = 100
      w = 0.5
      c1 = 1.5
      c2 = 1.5
      best_solution = particle_swarm_optimization(func, bounds, num_particles, num_iterations, w, c1, c2)
      print(f"最优解: {best_solution}, 目标函数值: {func(best_solution)}")
      
4.3 启发式算法在机器学习中的应用

启发式算法在机器学习中的应用包括参数优化和特征选择。

  • 应用实例:使用遗传算法进行机器学习模型的参数调优。
    • 问题描述:对一个机器学习模型进行参数调优,以提高模型的预测精度。
    • 算法实现
      import randomdef genetic_algorithm(func, bounds, pop_size, generations, crossover_rate, mutation_rate):population = [random_individual(bounds) for _ in range(pop_size)]best_individual = max(population, key=lambda ind: func(ind))for _ in range(generations):selected = selection(population, func)offspring = crossover(selected, crossover_rate)population = mutation(offspring, mutation_rate, bounds)current_best = max(population, key=lambda ind: func(ind))if func(current_best) > func(best_individual):best_individual = current_bestreturn best_individualdef random_individual(bounds):return [random.uniform(bound[0], bound[1]) for bound in bounds]def selection(population, func):total_fitness = sum(func(ind) for ind in population)probabilities = [func(ind) / total_fitness for ind in population]selected = random.choices(population, probabilities, k=len(population))return selecteddef crossover(population, rate):offspring = []for i in range(0, len(population), 2):parent1, parent2 = population[i], population[i+1]if random.random() < rate:point = random.randint(1, len(parent1)-1)child1 = parent1[:point] + parent2[point:]child2 = parent2[:point] + parent1[point:]offspring.extend([child1, child2])else:offspring.extend([parent1, parent2])return offspringdef mutation(population, rate, bounds):for individual in population:if random.random() < rate:point = random.randint(0, len(individual)-1)individual[point] = random.uniform(bounds[point][0], bounds[point][1])return populationdef func(x):return -(x[0]**2 + x[1]**2) + 10bounds = [(-5, 5), (-5, 5)]
      pop_size = 50
      generations = 100
      crossover_rate = 0.8
      mutation_rate = 0.05
      best_solution = genetic_algorithm(func, bounds, pop_size, generations, crossover_rate, mutation_rate)
      print(f"最优解: {best_solution}, 目标函数值: {func(best_solution)}")
      

5. 启发式算法的优缺点分析

5.1 启发式算法的优势
  • 求解速度快:相比精确算法,启发式算法通常能在较短时间内找到一个较优解。
  • 适应性强:启发式算法可以应用于各种不同类型的优化问题,具有较强的通用性。
  • 易于实现:启发式算法的实现通常比较简单,易于在实际应用中进行推广。
5.2 启发式算法的局限性
  • 不能保证全局最优解:启发式算法通常只能找到一个近似最优解,不能保证一定找到全局最优解。
  • 对参数依赖较大:启发式算法的性能通常对参数设置比较敏感,参数选择不当可能导致求解效果不佳。
  • 陷入局部最优:有些启发式算法可能会陷入局部最优解,难以跳出局部最优找到更好的解。

6. 总结与展望

6.1 启发式算法的发展方向

随着计算技术的发展,启发式算法在实际应用中展现出越来越强的求解能力和广泛的应用前景。未来的发展方向包括:

  • 混合启发式算法:将多种启发式算法结合,发挥各算法优势,提高求解效果。
  • 智能自适应算法:引入智能自适应机制,根据问题特性动态调整参数,提高算法适应性和求解效果。
  • 并行计算:利用并行计算技术,加速启发式算法的求解过程,提高计算效率。
6.2 新兴启发式算法介绍

新兴启发式算法在优化求解领域展现出新的潜力,如量子启发式算法和深度强化学习算法。

  • 量子启发式算法:利用量子计算的特性,通过量子叠加和量子纠缠实现并行搜索,提高求解效率。
  • 深度强化学习算法:结合深度学习和强化学习的优势,通过学习和探索找到最优解。
6.3 启发式算法在未来技术中的应用前景

启发式算法在未来技术中的应用前景广阔,包括智能制造、智慧城市等领域。

  • 智能制造:在智能制造中,启发式算法可以用于优化生产调度、设备维护等问题,提高生产效率和产品质量。
  • 智慧城市:在智慧城市中,启发式算法可以用于优化交通管理、能源调度等问题,提高城市运行效率和居民生活质量。

结论

本教程详细介绍了启发式算法的基本概念、类型、原理及其在实际问题中的应用。通过多个实例,读者可以深入理解并应用启发式算法解决实际问题。在未来,随着计算技术的发展,启发式算法将在更多领域展现其强大的解决问题的能力。

这篇关于启发式算法教程(个人总结版)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1027885

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

Makefile简明使用教程

文章目录 规则makefile文件的基本语法:加在命令前的特殊符号:.PHONY伪目标: Makefilev1 直观写法v2 加上中间过程v3 伪目标v4 变量 make 选项-f-n-C Make 是一种流行的构建工具,常用于将源代码转换成可执行文件或者其他形式的输出文件(如库文件、文档等)。Make 可以自动化地执行编译、链接等一系列操作。 规则 makefile文件

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO