我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:六合报码室 > 多项式时间 >

近似算法和启发式算法的区别与联系

归档日期:05-14       文本归类:多项式时间      文章编辑:爱尚语录

  在计算机科学与运筹学,近似算法是指用来发现近似方法来解决优化问题的算法。近似算法通常与NP-hard问题相关; 由于不可能有效的多项式时间精确算来解决NP-hard问题,所以一个求解多项式时间次优解。与启发式算法不同,通常只能找到合理的解决方案相当快速,需要可证明的解决方案质量和可证明的运行时间范围。理想情况下,近似值最优可达到一个小的常数因子(例如在最优解的5%以内)。近似算法越来越多地用于已知精确多项式时间算法但由于输入大小而过于昂贵的问题。

  启发式算法(heuristic algorithm)是相对于最优化算法提出的。一个问题的最优算法求得该问题每个实例的最优解。启发式算法可以这样定义:一个基于直观或经验构造的算法,在可接受的花费(指计算时间和空间)下给出待解决组合优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度一般不能被预计。现阶段,启发式算法以仿自然体算法为主,主要有蚁群算法、模拟退火法、神经网络等。

本文链接:http://barstaffuk.com/duoxiangshishijian/415.html