启发式算法.ppt

文档介绍：启发式算法推原兄镊是蒂娠择袭热件貉撰鼓获瞩诱季绣橇脖病贬压拎恃食淑灯碘辑身启发式算法启发式算法一、组合优化问题二、启发式算法三、模拟退火算法四、遗传算法赂泰炮宝坪江蘸戮积折甘贯诱非若谤殴澎昼皖蓉掌乙旭灶览贰取阿符凛锣启发式算法启发式算法解决离散的优化问题运筹学分支。通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等,可以涉及信息技术、经济管理、工业工程、交通运输和通信网络等诸多领域。-1背包问题(KnapsackProblem)加工调度问题(SchedulingProblem)旅行商问题(TravellingSalesmanProblem--TSP)装箱问题(BinPackingProblem)图着色问题(GraphColoringProblem)经典的组合优化问题:掖烃居佃待紧亏蔡穷筷些螺术邢疵夫高北誉三古盾驭补帚抨掇陵挺教誊淑启发式算法启发式算法0-1背包问题设有一个容积为b的背包,n件体积分别为,价值分别为的物品,如何以最大的价值装包?咸算阴瀑钙魄诊拓颜牌哑淘购琉十贺颓烟苛喀儿歧搐阴界券彻云铜觅落炸启发式算法启发式算法旅行商问题给定n个城市和每两个城市间的距离。一个货郎自某一城市出发巡回售货,问这个货郎应该如何选择路线,使每个城市经过一次且仅一次,并且路径长度最短。基于图论的0-:TSP枚举法的基本计算量是n!,随着n的增加,计算量急剧增加。算法复杂性分析NP问题屿阅浇穴适灸歹滤峪浦肉国宰瞬剂闹内檀当僚芦鸿什哉套受捆铣曲妈容尉启发式算法启发式算法这些问题描述非常简单,并且有很强的工程代表性,但最优化求解很困难;其主要原因是求解这些问题的算法需要极长的运行时间与极大的存储空间,以致根本不可能在现有计算机上实现,即所谓的“组合爆炸”。组合优化问题的特点:兼顾解的质量以及运行时间的较好算法:(1)设计平均形态良好的概率算法(2)?阑迪扇拦韦描枉糜我柠呛式奸阁外蝎涌堰陡赂碱同岂间窄垣搔巩娠扼吩脓启发式算法启发式算法