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