欢迎来到天天文库
浏览记录
ID:59133882
大小:176.26 KB
页数:8页
时间:2020-09-25
《人工智能搜索与问题求解总复习ppt课件.pptx》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、SearchandProblemSolvingReview07121101韩煦1120112009理想的搜索算法:-在最短的时间内搜索到最好的解。-满足解的最优性与计算的可行性相矛盾。-盲目VS启发局部VS全局可行解VS最优解问题的表现方式:-状态空间表示法:将问题求解所涉及的每个可能的步骤表示成一个状态。-与或图表示法:一个原始问题往往既需要通过分解,又需要通过变换才能得到其本原问题,其归约过程可用与或图表示。图搜索:-盲目图搜索算法:-启发式图搜索算法:博弈搜索:-极大极小搜索方法:-α-β剪枝技术:状态空间五元组:-
2、(S,F,C,I,G)--状态的集合、用于状态转换的操作符的集合、状态转换代价的集合、初始状态的集合、目标状态的集合。基于状态空间表示的问题求解算法:(P28)-step1:定义问题状态的计算机描述形式,表达出可能的状态,定义初始状态&&目标状态。-step2:确定促使状态发生转换的操作。-step3:状态之间所允许的操作为有向边,获得图。-step4:应用图搜索方法,在状态空间中搜索最优路径
3、
4、可行路径。返回分解:与-只有当所有子问题都有解时,原问题才有解。变换:或-只要一个子问题有解,原问题就有解。基于与或图表示的问题
5、求解算法:-step1:确定单个问题的描述形式,可采用状态空间表示法。-step2:从原始问题开始,逐步进行分解和变换。然后将全部分解和变换表示为与或图。-step3:从端顶点向上回溯,标注各顶点为可解顶点或不可解顶点。-step4:当原始顶点被确定为可解顶点时,输出解。返回图搜索:-表示出完整的图需要占用大量存储空间。所以在图搜索中逐步展开搜索所需要的子图。(与或图目标是确定初始顶点可解性,需反向回溯,确定祖先顶点是否可解。)图搜索算法基本步骤:(P33)-step1:把初始顶点放入OPEN表,建立仅包含初始顶点的图G。
6、-step2:按一定策略,取出待扩展顶点,放入CLOSED表。-step3:扩展从OPEN表中取出的待扩展顶点。若可扩展:对于状态空间,扩展得到的不重复的,子顶点放入OPEN表。根据需要修改G中顶点之间的福字关系。对于与或图,将扩展得到的子顶点放入OPEN表。子顶点中的终止顶点,标注其可解,并逐步回溯确定祖先借点是否不可解。若不可扩展:对于状态空间,不作任何处理。对于与或图,标注顶点为不可解,并逐步回溯。-step5:重复。对于状态空间,结束条件是待扩展顶点为目标顶点,或者OPEN表空。对于与或图,初始顶点被标注为可解或不
7、可解,或OPEN表为空。返回盲目图搜索:-广度优先搜索:先进先出。-深度优先搜索:后进先出。-有界深度优先搜索:在搜索路径深度超过所限定的深度界线后立即向上回退。-迭代加深深度优先搜索:首先在小的深度限制下进行有界深度优先搜索,找不到解则增大深度限制。启发式图搜索:-A*算法:针对状态空间。条件:①估计出的代价值小于等于实际最小代价。②选中目标节点并扩展才停止。f(n)=g(n)+h(n)f(n)顶点的启发式函数值,g(n)从初始顶点到顶点n的实际代价,h(n)是从顶点n到目标顶点的最优路径估计代价,值越大越好,表明与实际
8、最小代价的差距越小。-AO*算法:针对与或图。分为两个阶段。自上而下的图生成过程:自下而上的代价值计算过程:返回博弈树:在结构上就是一颗与或树-极大极小搜索:MAX顶点的倒退值应取其子顶点估值的极大值,利于我方。做最坏的打算,MIN会选择对他自己最好的走步,取极小值。-α-β剪枝技术:根据倒退结果,在非叶顶点的向下分枝中,剪掉那些目前尚未扩展,但无论其扩展与否,都不会改变非叶顶点倒退值的分枝。α值:MAX顶点倒退值的最小边界。β值:MIN顶点倒退值的最大边界。α剪枝:任何MIN顶点的n的β值小于或等于它的某一祖先MAX顶点
9、的α值,则n以下的分枝可停止搜索,并令顶点n的倒退值为β。β剪枝:任何MAX顶点的n的α值大于或等于它的某一祖先MIN顶点的β值,则n以下的分枝可停止搜索,并令顶点n的倒退值为α。TheEnd
此文档下载收益归作者所有