人工智能chapter5heuristic.ppt

1、第5章启发性搜索、启发性搜索和评价函数状态空间的启发性搜索A算法和A*算法和/或树的启发性搜索游戏树搜索、启发性搜索、启发性搜索是对发现和发明规则和方法的研究。在状态空间搜索中，启发式定义为一系列规则，在状态空间中选择最接近解决问题的路径。信息检索策略是除了问题本身的定义以外，利用问题特定知识的策略。有效地帮助确定启发性信息、启发性信息的种类和有关扩展节点的信息。有助于确定应创建哪些后续节点。展开节点时，您可以确定需要从搜索树中删除的节点。启发性信息的作用启发性信息的启发能力越强，扩展的无用物就越少。启发式搜索，在这两种情况下，启发式策略：问题说明和数据获取中固有的模糊性可能没有明确的解决方案

2、。最有可能通过医疗诊断、视觉系统、启发式政策选择进行解释。国际象棋等一个茄子问题可能有明确的解决方案，但在解决过程中，电脑费用难以接受。匮乏的搜索策略很可能在给定的时空里得不到最终答案。启发式策略将搜索引导到最有希望的方向，从而降低复杂性。消除分组爆炸，获得可接受的解决方案。但是启发式策略也容易出错。启发式搜索只有有限的信息，所以可能会得到最好的解决方案，也可能一无所获。启发式战略和算法设计一直是AI的核心问题。ES被认为是故障排除的重要组成部分。5.1启发式搜索和评估函数、启发式战略和算法设计一直是人工智能的核心问题。游戏和整理是两个最古老的茄子应用，两者都证明了为了减少状态空间需要启发性知

3、识。应用启发式减少搜索耗散。启发式算法(启发式)通常由搜索方法和状态空间的算法(方法)两部分组成。例如，单词国际象棋，“最佳优先级”选择算法每种状态都是搜索过程，启发式搜索和评估函数，智能活动中最常用的是完美的算法，但不一定是完整的启发式方法。在搜索问题空间时，要提高搜索效率，作为搜索的辅助策略，需要与和解相关的大量控制知识。控制信息反映在评估函数中。函数评估的任务是估计要搜索的节点的重要性。从初始节点到N的实际成本，从N到目标的最佳路径估计成本，5.2启发式搜寻演算法，5.2.1局部偏好搜索(盲登山法hilkliming)是从深度优先搜索方法演化而来的。每次到达一个节点时，后续节点的选择不是

4、计划的或随机的，而是在所有子节点上根据评估函数f(x)选择优化器。正如盲人爬山，老名盲人爬山。可以在本地首选搜索中取消OPEN表。每次展开后保留最佳子节点N，放弃所有其他子节点。n是下一个扩展节点，可以直接放置在CLOSED表中。function hill-climbing(problem)return A state that is A local maximum inputs 3360 problem，A problem local variables 3360 A node code因为只考虑局部友好，所以有单边性，甚至搜索失败。(威廉莎士比亚，奥赛罗)，本地首选搜索，状态空间地形图，目

5、标函数，状态空间，全局最大值，本地最大值，登山法经常会遇到以下问题：当地最大山脊是高原，登山法的变形，随机登山首选登山方法随机重新登山方法，5.2.定义：在Best-first Search(Ordered Search)AI图搜索中，节点的扩展顺序由要扩展的节点的评估函数值f(x)确定。也就是说，首先展开具有最佳函数值的节点是用F值引导搜索顺序。估计函数(评估函数)f(x):估计函数任务是估计OPEN表中每个节点的重要性并确定其顺序。估计函数f(x)可以是任意函数之一。有些定义是节点X在最佳路径上的概率。或节点x和目标节点之间的距离。或者X格句的分数等等。一般来说，要估计一个节点的价值，必须

6、考虑两个茄子因素：已经付出的代价和即将付出的代价。将估计函数f(n)定义为从初始节点通过N节点到达目标节点的最小成本估计。5.2.2优先搜索法最好。一般格式为f(n)=g(n) h(n)。其中g(n)是初始节点到n的实际成本。H(n)是从n到目标节点的估计成本。H(n)反映了从搜索中获得灵感的信息。实际成本g(n)可以根据生成的搜索树来计算，估计代h(n)来自我们对问题解决方案的某些特性的认识，这些特性可以帮助我们更快地找到问题的解决方案。(约翰f肯尼迪，美国电视电视剧，成功)H(n)=0，g(n)=d(n)时的广度优先搜索方法。通常，f(n)到g(n)的比重越大，广度优先搜索倾向越大。H(n

7、)的比重越大，倾向于深度优先搜索。F(n)使您可以估计要扩展的每个节点的价值，并选择OPEN表中最有希望的节点扩展。5.2.2优先级搜索方法，搜索过程：顺序搜索中的数据结构广度优先搜索使用团队，与深度优先搜索使用堆栈不同，按节点F值的大小顺序排列的表，也称为“优先级队列”。进入优先级队列的节点不仅仅位于队列的末尾，而是根据F值的大小值插入到相应的位置。每次先将具有最小f值的节点出队并展开时。5.2.2优先搜索方法，例如，一个节点上有多个通道的搜索树的有序搜索过程：(A)，A，J，I，H，D，C，B，E，G，F，设置H=4，有三个可茄子的通道通向f、B和H三个节点。显然，这三个节点的g值都是1。

8、图中的H值表示为精确值，但实际上必须是估计值。三个节点的f值分别计算为3、4和5。将三个牙齿节点按F的大小顺序发送到优先级组。要扩展的下一个节点是组中F值最小的节点，即节点F。只有一个后续节点D，节点值F为3。因为节点F已完全扩展，所以它成为闭合节点，将具有最小F值的节点D插入到团队头中，然后扩展D以继续，直到出现目标节点E。，首先是搜索方法，顺序搜索方法的流程图，开始，将So放在OPEN表中计算f(So)，将OPEN头N放在CLOSED中，扩展N，用f(x)评估Ni，将Ni合并到OPEN中，将f(。N=Sg，N可扩展，N，Y，失败，成功，Y，Y，N，流程最佳-第一while open do

9、begin remove the next state from open，call it x；if x is a goal then return the solution path that led to x；Process x，generating all its childrenfor each child of x do case the child is not already on open or closed : begin assign a heuristic value to the child state；ADD THE CHILD STATE TO OPEN；END；T

10、he child is already on open : if The child was reached along a shorter PATH than The state curren lty on open then give The state on open this short ER PPSPUT X ON CLOSED；re-order States on open according to heuristic merit(best values first)end；返回(failure)；% OPEN IS EXHAUSTED END。方法算法说明优先搜索，f(n)=G(

11、n)(n)h(n)G(n)=从n到初始状态的实际长度h(n)=位置不匹配的卡数G (n)=1，start，Closed=a4 3.open=e5，f5，g6，b6，D6；Closed=a4，C4 4.open=F5，h6，g6，B6，D6，i7；Closed=a4，C4，E5 5.open=j5，h6，g6，B6，D6，k7，i7；Closed=a4、C4、E5、F5 6.open=l5、h6、g6、B6、D6、k7、i7；Closed=a4、C4、E5、F5、j5 7.open=M5、h6、g6、B6、D6、n7、k7、i7；Closed=a4、c4、e5、f5、j5、l5 8。成功，m=目

12、标状态！5.2.3启发式函数实现，启发式搜索的一般规则为： 1.根据规则创建当前节点的子状态。2.为了避免循环，请确保每个状态已存在于open表或closed表中。3.每个状态n都指定了f(n)值。其中，f=g h，h值对搜索有更好的启发。g值防止搜索在错误的路径上无限继续。4.开放表的状态按f值排序。保存这些状态可能会从无效路径返回。5.设计开放表和关闭的表存储方法以提高算法效率。5.2.3启发估算函数实现，随机搜索、搜索问题是计算机科学和人工智能驱动研究的兴趣之一。“无限猴子定理”Arthur Eddington(如果猴子很多的话，每个人继续敲自己的一台打字机)。总有一天，一只猴子会偶然弹

13、哈姆雷特剧本。复习：登山法搜寻演算法，决不“下山”。也就是说，不在低于当前节点(或消耗高)的方向上搜索是不完整的。这是因为可以停留在局部极值中，概念：在图搜寻演算法中，在搜索的所有阶段，如果可以使用评估函数f(n)=g(n) h(n)对Open表中的节点进行排序，则搜寻演算法A算法。，5.3 A算法和A*算法，估价函数中有关于问题本身的启发性信息，因此A算法也称为启发性搜寻演算法。根据搜索期间选择扩展节点的范围，启发式搜寻演算法可以分为全局首选搜寻演算法和本地首选搜寻演算法。全局首选：在Open表的所有节点中，选择并展开最小的评估函数值之一。本地首选：从刚创建的子节点中选择最小的评估函数值之一进行展开。全局首选搜索a算法说明：(1)在开放表中放置初始节点S0，f(S0)=g(S0)h(S0)；(2)如果