计算机问题求解一论题4.10 启发式算法的概念 陶先平 2017年6月5日
计算机问题求解—论题4.10 启发式算法的概念 陶先平 2017年6月5日
问题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∈fr(a)for some a∈M(x),then a∈fr (iii)for all a,BE M(x)there exists a positive integ 由定义，因人 such that Y∈fx(a),Y+1∈fz(Y)fori=1,. 因事而不同 提示：定义的第三点，寓意深刻
问题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 aE M(x)is a local optimum for the input instance x of U according to f,if cost(a)=goal{cost(3)川lB∈fx(a). 退而求其次，也是一个很好的策略
局部最优解 退而求其次，也是一个很好的策略