人工智能课件第2章.ppt

《人工智能课件第2章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.4.2A算法与A*算法1．A算法与A*算法定义或图通用算法在采用如下形式的估计函数时,称为A算法。f(n)=g(n)+h(n)其中g(n)表示从S0到n点费用的估计，因为n为当前节点，搜索已达到n点，所以g(n)可计算出。h(n)表示从n到Sg接近程度的估计，因为尚未找到解路径，所以h(n)仅仅是估计值。例2.10在地图上寻找城市A至B的最短路径，双虚线表示ni与Sg的直线距离(可以从地图上量出）,虚线表示ni与Sg的路径，则实线表示的路径为g(n），虚线表示的路径为h(n）。A=S0B=Sgn1n2n3n4n52.4.2A算法与A*算法若规定h(n)≥0，并且定义

2、：f*(n)=g*(n)+h*(n)表示S0经点n到Sg最优路径的费用，也有人将f*(n)定义为实际最小费用。其中g*(n)为S0到点n的最小费用,h*(n)为n到Sg的实际最小费用。在上例中，双虚线表示的路径就可以作为h*(n），显然有g(n）≥g*(n）。h(n）h*(n）若令h(n）≡0，则A算法相当于广度优先，因为上一层节点的搜索费用一般比下一层的小。g(n）≡h(n）≡0，则相当于随机算法。g(n）≡0，则相当于最佳优先算法。特别是当要求h(n）≤h*(n），就称为这种A算法为A*算法。A*算法设S0：初态,Sg：目标状态1.open={S0}；2.clos

3、ed={}；3.如果open={}，失败退出；4.在open表上取出f最小的结点n，n放到closed表中；f(n)=g(n)+h(n)h<=h*5.若n∈Sg，则成功退出；6.产生n的一切后继，将后继中不是n的先辈点的一切点构成集合M7.对M中的元素P，分别作两类处理：7.1若P∈G，则P对P进行估计加入open表，记入G和Tree。7.2P∈G，则决定更改Tree中P到n的指针并且更改P的子节点n的指针和费用。8.转3。2．A*算法的性质A*算法与一般的最佳优先比较，有其特有的性质：如果问题有解，即S0→Sg存在一条路径，A*算法一定能找到最优解。这一性质称为可采纳

4、性(admissibility）。（p35例2.11)下面要证明A*算法的可采纳性，证明分两步：(1）证若问题有解，A*一定终止，由如下命题1-3证出。(2）证若问题有解，A*终止时一定找到最优解，由如下命题4证出。命题1对有限图而言，A*一定终止。证：考察A*算法，算法终止只有二处：第一处在第5步，找到解时成功终止。第二处在第3步，open为空时失败退出。算法每次循环从open上去掉一个点，而有限图的open表只有有限个节点加入，所以找不到解也会因为open表为空而停止命题2若A*不终止，则搜索图中open表上的点的f值将会越来越大。证：设n为open中任一节点，d*

5、(n）为从S到n中最短路径长度，由于从某一点求出其后继的费用不小于某个小的正数e，所以g*(n）≥d*(n）·e而g(n）≥g*(n）≥d*(n）·e又因为h(n）≥0所以f(n）≥g(n）≥g*(n）≥d*(n）·e(2-1）命题3若问题有解，在A*终止前，open表上必存在一点n’，n’位于从S0→Sg的最优路径上，且有f(n’）≤f*(S0）(2-2）f*(S0）表示从S0到Sg的最优路的实际最小费用。f*(n）表示从S0经过n到Sg的最优路的实际最小费用。证：令S0=n0，n1，n2，…，nk=Sg为一条最优路径，设n’∈path(n0，n1，…，nk）中最后一

6、个出现在open表上的元素。显然n’一定存在，因为至少有S0=n0必然在open上，只考虑当nk还未在closed表中时，因为若nk已在closed表中时，则nk=Sg，A*算法将终止于成功退出。由定义有f(n’）=g(n’）+h(n’）=g*(n’）+h(n’）(因为n’在最优路径上）≤g*(n’）+h*(n’）=f*(n’）=f*(S0）(由于A*的定义h(n)≤h*(n))所以f(n’）≤f*(S0）成立。推论1若问题有解，A*算法一定终止。因为若A*算法不终止，则命题2的(2-1）与命题3的(2-1）同时成立，则产生矛盾。命题4若问题有解，A*算法终止时一定找到

7、最优解,即A*算法是可采纳的。证：A*终止只有两种情况。(1) 在第3步,因open为空而失败退出但由命题3可知：A*终止前，open表上必存在一点n’，满足f(n’）≤f*(S0）即open表不会空，所以，不会终止于第3步。推论2凡open表中任一点n，若f(n）