南京大学：《计算机问题求解》课程教学资源（PPT课件讲稿）启发式算法

计算机问题求解一论题4.14 启发式算法的概念 陶先平 2021年6月7日

计算机问题求解—论题4.14 启发式算法的概念 陶先平 2021年6月7日

问题1：在一个优化问题中，什么是问题 空间？什么是解空间？ Let U (SI,>o,L,LI,M,cost,goal) 问题2：启发式算法本质上来讲，是一种解 空间搜索算法。你如何理解这个说法？

问题1：在一个优化问题中，什么是问题 空间？什么是解空间？ 问题2：启发式算法本质上来讲，是一种解 空间搜索算法。你如何理解这个说法？

问题3：定义一个可行解的”邻居”是什么用 意？ Definition 3.6.1.1.Let U (SI,So,L,LI,M,cost,goal)be an optimiza- tion problem.For every x E LI,a neighborhood on M(x)is any mapping f M(x)Pot(M(x))such that (i)a∈fx(a）for every a∈M(x), i)fB∈fz(a)for some a∈M(zx),then a∈fr(B),and (iii)for all a,BEM(x)there exists a positive integer k and1,...,YkE M(x) such that Y∈fx(a),Y+1∈fz(a)fori=1,,k-1,andB∈fx(Yk). 提示：定义的第三点，寓意深刻

问题3：定义一个可行解的”邻居”是什么用 意？ 提示：定义的第三点，寓意深刻

可行解的邻居图 The (undirected)graph GM().f=(M(x),{fa,B)laE fz(B),a#B,a,BEM()}) is the neighborhood graph of M(x)according to the neighborhood fa. 理论上：1，邻居图连通； 2,最优解必定在图中； 3,遍历解空间的难度，决定了问题难度

可行解的邻居图 理论上：1，邻居图连通； 2，最优解必定在图中； 3，遍历解空间的难度，决定了问题难度

局部最优解 Definition 3.6.1.4.Let U =(SI,So,L,LI,M,cost,goal)be an optimiza- tion problem,and let,for every x E LI,the function fr be neighborhood on M(x).A feasible solution a E M(x)is a local optimum for the input instance x of U according to f,if cost(a)=goalfcost(B)BE fz(a)}. We denote the set of all local optima for x according to the neighborhood fx by LocOPTU(x,f). 退而求其次，也是一个很好的策略

局部最优解 退而求其次，也是一个很好的策略

LSS算法框架 LSS(Neigh)-Local Search Scheme according to a neighborhood Neigh Input:An input instance z of an optimization problem U. Step 1: Eind 2 foasiblo solution) 我们有可能写出 Step 2: while ag LocOPTu(a,Neigh)do begin find a B E Neigh(a)such that 个LocOPTui函数吗？ cost(B)cost(a)if U is a maximization problem;a:=B end Output:output(a)

LSS算法框架 我们有可能写出一 个LocOPTU函数吗？

can essentially influence LSS算法框架 the quality of the result: arbitrary poor local LSS(Neigh)-Local Sear h Sc. optima a neighborhood Neigh Input:An input instance x of an optimization problem U. Step 1:Finda feasible solution a E M(x) Step 2:while ag LocOPTu(x,Neigh)do begin fir∈Neigh cost(B)cost improvement end may lead to very different Output:output(a). results for the same initial feasible solution. LSS算法一定能找到局部取 Find对结果的优劣和算法的效率是有影响的

LSS算法框架 LSS算法一定能找到局部最优！但上述两个 Find对结果的优劣和算法的效率是有影响的 can essentially influence the quality of the result： arbitrary poor local optima first improvement, best improvement may lead to very different results for the same initial feasible solution

LSS算法的典型示例：爬山算法 E A点、E点出发，结果大相径庭 任何一点出发，我们得到的近邻最优，只保证是极值！ 近邻最优，往往是个“陷阱

LSS算法的典型示例：爬山算法 A B C D E F A点、E点出发，结果大相径庭 任何一点出发，我们得到的近邻最优，只保证是极值！ 近邻最优，往往是个“陷阱

必须解决局部搜索方法中的 poor local optima”问题 The basic idea of simulated annealing is to add the possibility of leaving a local optimum (i.e.,to move to a weaker solution than the current one)by some kind of coin tossing (random decision)

必须解决局部搜索方法中的 “poor local optima”问题

物理学中的“退火”是什么？ (1)The temperature of the heat bath is increased to a maximum value at which the solid melts.This causes all the particles to arrange themselves randomly. (2)The temperature of the heat bath is slowly decreased according to a given cooling schedule until a low-energy state of the solid (a perfect crystal structure)is achieved

物理学中的“退火”是什么？