数学建模组合优化问题和计算复杂性.ppt

§1.3启发式算法对TSP,{0,1}3:{(0,0,0),(0,0,1)(0,1,0),(0,1,1)(1,0,0),(1,0,1)(1,1,0),(1,1,1)}可以定义它的一种邻域为：k为一个正整数。这个邻域定义使得x最多有k个位置的值可以发生变化，x的邻居有1+C1n(n-1)+C2n(n-1)+…+Ckn(n-1)个.Example8第37页,共57页，星期六，2024年，5月§1.3启发式算法定义邻域映射为2-opt即s中的两个元素进行对换,N(s)中共包含s的C2n个邻居。Example9TSP问题解的另一种表示法为D=F={S=(i1,i2,…,in)|i1,i2,…,in是1,2,…,n的一个排列}如四个城市的TSP问题，当s=(1,2,3,4)时，N(s)={（2，1，3，4），（3，2，1，4），（4，2，3，1），（1，3，2，4），（1，4，3，2），（1，2，4，3）}第38页,共57页，星期六，2024年，5月§1.3启发式算法Definition7若s*满足则称s*为f在F上的局部（local）最小（最大）解.f(s*)≤(≥)f(s),其中s∈N(s*)F若s∈F，则称s*为f在F上的全局(global)最小(最大)解。这其实也提供了一种启发式算法（heuristicalgorithm）的思想，局部搜索（或邻域搜索）算法。第39页,共57页，星期六，2024年，5月§1.3启发式算法二、启发式算法定义一个基于直观或经验构造的算法，在可接受的花费（指计算时间、占用空间等）下，给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计.则称该算法为启发式算法.启发式算法是相对于最优算法提出的，一个问题的最优算法，求得该问题每个实例的最优解,启发式算法是一种技术。Definition8第40页,共57页，星期六，2024年，5月§1.3启发式算法Definition9设A是一个问题，记问题A的任何一个实例I的最优解和启发式算法H解的目标值分别为Zopt(I)和ZH(I),于是对某个a0,称H是A的a-近似算法（a-approximationalgorithm）,当且仅当|ZH(I)-Zopt(I)|≤a|Zopt(I)|用启发式概念定义的算法集合包含了近似算法概念定义的算法集合，近似算法强调给出算法最坏情况的误差界限，而启发式算法不需考虑偏差程度。第41页,共57页，星期六，2024年，5月§1.3启发式算法算法为:step1任选一个初始解so∈S；step2在N(so)中按某一规则选一s，若f(s)f(so)，则so:=s返回step2；否则，N(so):=N(so)-s;若N(so)=ф，停止;否则，返回step2.Example10简单的邻域搜索（localsearch）算法给定组合优化问题，假设其邻域结构已确定，设S为可行解集合，f为S上的费用函数，N为邻域结构。第42页,共57页，星期六，2024年，5月§1.3启发式算法简单的邻域搜索达到一个局部最优点依赖于初始解选取、邻域结构、邻域选点的规则启发式算法的长处：1）数学模型是实际问题的简化，有可能使最优算法所得解比启发式算法所得解产生更大误差；2）不少难的组合优化问题可能还没找到有效的最优算法；3）一些启发式算法可以用在最优算法中，如在分支定界算法中，可以用启发式算法估界；第43页,共57页，星期六，2024年，5月§1.3启发式算法4）简单易行，比较直观，易被使用者接受；5）速度快，在适时管理中非常重要；6）多数情况下，程序简单，因此易于修改。1）不能保证求得最优解；启发式算法的不足：2）表现不稳定；3）算法的好坏依赖于实际问题、经验和设计者的技术，使不同算法之间难以比较。第44页,共57页，星期六，202