计算机问题求解一论题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). 退而求其次，也是一个很好的策略
局部最优解 退而求其次，也是一个很好的策略