《人工智能初步用搜索解决问题》AI培训教案幻灯课件.ppt

1、人工智能初步人工智能初步-用搜索用搜索解决问题解决问题AI培训教案培训教案ppt-幻灯幻灯2022-11-5人工智能初步用搜索解决问题AI培训教案ppt幻灯主要内容搜索及其类型搜索及其类型盲目搜索盲目搜索宽度优先搜索宽度优先搜索深度优先搜索深度优先搜索启发式搜索与博弈启发式搜索与博弈上机实践上机实践人工智能初步用搜索解决问题AI培训教案ppt幻灯搜索及其类型1 1、什么是搜索、什么是搜索人工智能所要解决的问题大部分不具备明确的解题步骤，人工智能所要解决的问题大部分不具备明确的解题步骤，而只能是利用已有的知识一步一步地摸索前进。而只能是利用已有的知识一步一步地摸索前进。根据问题的实际情况不断寻找

2、可利用的知识，从而构造一根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程称之条代价较少的推理路线，使问题得到圆满解决的过程称之为搜索为搜索 。人工智能初步用搜索解决问题AI培训教案ppt幻灯搜索及其类型2 2、可以用搜索解决的问题、可以用搜索解决的问题8 8数码问题数码问题猴子和香蕉问题猴子和香蕉问题旅行商问题旅行商问题走迷宫走迷宫博弈问题博弈问题规划问题规划问题人工智能初步用搜索解决问题AI培训教案ppt幻灯搜索及其类型搜索及其类型3 3、常用的搜索技术、常用的搜索技术盲目搜索盲目搜索又称无信息又称无信息/穷举式搜索，只能按照预先规定的搜索控制

3、策略进行穷举式搜索，只能按照预先规定的搜索控制策略进行搜索，没有任何中间信息来改变这些控制策略。搜索，没有任何中间信息来改变这些控制策略。具有盲目性，效率不高，不便于复杂问题的求解。具有盲目性，效率不高，不便于复杂问题的求解。具体可以分为宽度优先搜索和深度优先搜索两种。具体可以分为宽度优先搜索和深度优先搜索两种。启发式搜索启发式搜索在搜索求解过程中，根据问题本身的特性或搜索过程中所产生的在搜索求解过程中，根据问题本身的特性或搜索过程中所产生的一些与问题有关的启发性信息，指导搜索朝着最有希望的推理方一些与问题有关的启发性信息，指导搜索朝着最有希望的推理方向前进，加速问题的求解过程并找到最优解。向

4、前进，加速问题的求解过程并找到最优解。人工智能初步用搜索解决问题AI培训教案ppt幻灯盲目搜索宽度优先搜索宽度优先搜索基本思想基本思想从初始节点从初始节点SoSo开始，逐层地对节点进行扩展并考察它是否为目标开始，逐层地对节点进行扩展并考察它是否为目标节点，在第节点，在第n n层的节点没有全部扩展并考察之前，不对第层的节点没有全部扩展并考察之前，不对第n+1n+1层的层的节点进行扩展。它是一种节点进行扩展。它是一种先生成的节点先扩展先生成的节点先扩展的搜索方法。的搜索方法。课件演示课件演示8数码问题的宽度优先搜索过程数码问题的宽度优先搜索过程人工智能初步用搜索解决问题AI培训教案ppt幻灯盲目搜

5、索宽度优先搜索示例宽度优先搜索示例求解八数码问题求解八数码问题人工智能初步用搜索解决问题AI培训教案ppt幻灯宽度优先搜索示例宽度优先搜索示例8数码问题的宽度优先搜索树数码问题的宽度优先搜索树人工智能初步用搜索解决问题AI培训教案ppt幻灯盲目搜索OPENOPEN表表用来存放将要扩展的节点。用来存放将要扩展的节点。CLOSECLOSE表表在进行子节点的扩展时，为了避免同一个节点被重复扩展，可以把扩在进行子节点的扩展时，为了避免同一个节点被重复扩展，可以把扩展过一次的节点，记录到展过一次的节点，记录到CLOSEDCLOSED表中，从而使其不再成为以后扩表中，从而使其不再成为以后扩展时的候选对象。

6、展时的候选对象。人工智能初步用搜索解决问题AI培训教案ppt幻灯宽度优先搜索算法宽度优先搜索算法人工智能初步用搜索解决问题AI培训教案ppt幻灯盲目搜索深度优先搜索深度优先搜索深度优先搜索中，搜索树是从树根开始一枝一枝逐渐生成深度优先搜索中，搜索树是从树根开始一枝一枝逐渐生成的。它是一种的。它是一种后生成的节点先扩展后生成的节点先扩展的搜索方法。的搜索方法。基本思想：基本思想：从初始节点从初始节点SoSo开始，在其子节点中选择一个节点进行考察，若不开始，在其子节点中选择一个节点进行考察，若不是目标节点，则再在该子节点的子节点中选择一个节点进行考察，是目标节点，则再在该子节点的子节点中选择一个节

7、点进行考察，如果该子节点可以扩展，则扩展该子节点，依次向下搜索，在搜如果该子节点可以扩展，则扩展该子节点，依次向下搜索，在搜索树的每一层始终先只扩展一个子节点，如此一直向下搜索，直索树的每一层始终先只扩展一个子节点，如此一直向下搜索，直到某个子节点既不是目标节点又不能继续扩展时，才从当前节点到某个子节点既不是目标节点又不能继续扩展时，才从当前节点返回上一级节点，沿另一方向又继续前进。返回上一级节点，沿另一方向又继续前进。人工智能初步用搜索解决问题AI培训教案ppt幻灯盲目搜索深度优先搜索示例深度优先搜索示例求解八数码问题（课件演示）求解八数码问题（课件演示）人工智能初步用搜索解决问题AI培训教

8、案ppt幻灯深度优先搜索示例深度优先搜索示例8数码问题的数码问题的深度优先搜索树深度优先搜索树人工智能初步用搜索解决问题AI培训教案ppt幻灯深度优先搜索算法深度优先搜索算法人工智能初步用搜索解决问题AI培训教案ppt幻灯盲目搜索有界深度优先搜索有界深度优先搜索在深度优先搜索的基础上，在深度优先搜索的基础上，给出了搜索树深度限制给出了搜索树深度限制，当从，当从初始节点出发沿某一分枝扩展到一限定深度时，就不能再初始节点出发沿某一分枝扩展到一限定深度时，就不能再继续向下扩展，而只能改变方向继续搜索。继续向下扩展，而只能改变方向继续搜索。算法示例算法示例 八数码问题八数码问题(课件演示课件演示)人工

9、智能初步用搜索解决问题AI培训教案ppt幻灯启发式搜索启发式搜索启发式搜索是指在控制性知识中增加关于被解问题和相应任务的某些特性，利是指在控制性知识中增加关于被解问题和相应任务的某些特性，利用启发性信息来确定节点的生成、扩展和搜索顺序，指导搜索朝着用启发性信息来确定节点的生成、扩展和搜索顺序，指导搜索朝着最有希望的方向前进的一类搜索方法。最有希望的方向前进的一类搜索方法。启发式搜索的特点启发式搜索的特点大多是深度优先搜索的改进，即尽量沿着最有希望的路径，向深度大多是深度优先搜索的改进，即尽量沿着最有希望的路径，向深度方向小范围前进；方向小范围前进；在有多条路可走时，会给出该走哪条路径的建议，从

10、而指导搜索过在有多条路可走时，会给出该走哪条路径的建议，从而指导搜索过程朝最有利的方向前进；程朝最有利的方向前进；利用问题求解的先验知识，使之尽快找到问题的解；利用问题求解的先验知识，使之尽快找到问题的解；可采用估值的方法进行搜索指导；可采用估值的方法进行搜索指导；生成的状态空间小、搜索时间短且效率高、控制性好，易于使问题生成的状态空间小、搜索时间短且效率高、控制性好，易于使问题得到解。得到解。人工智能初步用搜索解决问题AI培训教案ppt幻灯启发式搜索启发性信息的类型启发性信息的类型有效地帮助确定扩展节点的信息，即用于决定应先扩展哪一个节点，有效地帮助确定扩展节点的信息，即用于决定应先扩展哪一

11、个节点，以免盲目扩展。以免盲目扩展。有效地帮助决定哪些后继节点应被生成的信息，即用于决定应生成有效地帮助决定哪些后继节点应被生成的信息，即用于决定应生成哪些后继节点，以免盲目地生成过多无用节点。哪些后继节点，以免盲目地生成过多无用节点。能决定在扩展一个节点时哪些节点应从搜索树上删除的信息，即用能决定在扩展一个节点时哪些节点应从搜索树上删除的信息，即用于决定应删除哪些无用节点，以免造成时空浪费。于决定应删除哪些无用节点，以免造成时空浪费。估价函数估价函数用来估价节点重要性的函数用来估价节点重要性的函数 f(n)=g(n)+h(n)g(n)是从初始节点是从初始节点So到节点到节点n的已经实际付出的

12、代价；的已经实际付出的代价；h(n)是从节点是从节点n到目标节点到目标节点Sg的最优路径的估计代价的最优路径的估计代价 人工智能初步用搜索解决问题AI培训教案ppt幻灯启发式搜索的算法启发式搜索算法启发式搜索算法有很多种，如局有很多种，如局部择优搜索、全部择优搜索、全局择优搜索等等局择优搜索等等 。右图表示了全局右图表示了全局择优的启发式搜择优的启发式搜索流程索流程 。人工智能初步用搜索解决问题AI培训教案ppt幻灯启发式搜索示例设估价函数为设估价函数为f(n)=g(n)+h(n)，其中其中g(n)表示节点表示节点n的搜索深度，的搜索深度，h(n)表示节点表示节点n与与目标节点两个棋局目标节点

13、两个棋局之间位置不相同的之间位置不相同的棋子数棋子数。每个节点左边的蓝每个节点左边的蓝色数字表示其估价色数字表示其估价值。值。人工智能初步用搜索解决问题AI培训教案ppt幻灯博弈与启发式搜索博弈博弈诸如下棋、打牌、战争等一类竞争性的智能活动。诸如下棋、打牌、战争等一类竞争性的智能活动。其中最简单的一种称为双方完备博弈。其中最简单的一种称为双方完备博弈。博弈树博弈树当某一方当前有多个行动方案可供选择时，他总是选择对自己最为有当某一方当前有多个行动方案可供选择时，他总是选择对自己最为有利而对对方最为不利的那个行动方案。利而对对方最为不利的那个行动方案。当轮到当轮到A A方走棋时，则可供方走棋时，则

14、可供A A方选择的若干个行动方案之间是方选择的若干个行动方案之间是“或或”的关系。轮到的关系。轮到B B方走棋时，方走棋时，B B方也有若干个可供选择的行动方案，但方也有若干个可供选择的行动方案，但此时这些行动方案对此时这些行动方案对A A方来说它们之间是方来说它们之间是“与与”的关系。的关系。使用与或图（与或树）来表示博弈过程，叫做博弈树。使用与或图（与或树）来表示博弈过程，叫做博弈树。人工智能初步用搜索解决问题AI培训教案ppt幻灯博弈与启发式搜索博弈树的特点博弈树的特点博弈的初始格局是初始节点。博弈的初始格局是初始节点。在博弈树中，在博弈树中，“或或”节点和节点和“与与”节点是逐层交替出

15、现的。自己一方扩展节点是逐层交替出现的。自己一方扩展的节点之间是的节点之间是“或或”关系，对方扩展的节点之间是关系，对方扩展的节点之间是“与与”关系。双方轮流关系。双方轮流扩展节点。扩展节点。人工智能初步用搜索解决问题AI培训教案ppt幻灯博弈与启发式搜索极大极小分析法极大极小分析法设博弈的双方分别为设博弈的双方分别为A A和和B B，然后为其中的一方（如，然后为其中的一方（如A A）寻找一个最优）寻找一个最优行动方案。行动方案。为了找到当前的最优行动方案，需要对各个方案可能产生的结果进行为了找到当前的最优行动方案，需要对各个方案可能产生的结果进行比较，并计算可能的得分。比较，并计算可能的得分

16、。为了计算得分，需要根据问题的特性信息定义一个估价函数，用来估为了计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树端节点的得分。此时估算出来的得分称为静态估值。算当前博弈树端节点的得分。此时估算出来的得分称为静态估值。当端节点的估值计算出来后，再推算父节点的得分。当端节点的估值计算出来后，再推算父节点的得分。如果一个行动方案能获得最大的倒推值，那么它就是当前最好的行动如果一个行动方案能获得最大的倒推值，那么它就是当前最好的行动方案。方案。人工智能初步用搜索解决问题AI培训教案ppt幻灯博弈与启发式搜索一字棋问题的求解一字棋问题的求解课件演示：一字棋课件演示：一字棋人工智能初

17、步用搜索解决问题AI培训教案ppt幻灯博弈与启发式搜索一字棋问题的求解思路一字棋问题的求解思路设设A A的棋子用的棋子用“a”“a”表示，表示，B B的棋子用的棋子用“b”“b”表示。并设棋局为表示。并设棋局为P P，估价函，估价函数为数为e e（P P），其中：），其中：（1 1）若）若P P是是A A获胜的棋局，则获胜的棋局，则e e（P P）=。（2 2）若）若P P是是B B获胜的棋局，则获胜的棋局，则e e（P P）=-=-。（3 3）若）若P P是胜负未定的棋局，则是胜负未定的棋局，则e e（P P）=e=e（+P+P）-e-e（-P-P）。）。其中其中e e（+P+P）表示棋局上有可能使）表示棋局上有可能使a a成一线的数目；成一线的数目；e e（-P-P）则表示棋局）则表示棋局上有可能使上有可能使b b成一线的数目。成一线的数目。人工智能初步用搜索解决问题AI培训教案ppt幻灯博弈与启发式搜索一字棋的极大极小搜索（第一回合）一字棋的极大极小搜索（第一回合）人工智能初步用搜索解决问题AI培训教案ppt幻灯博弈与启发式搜索一字棋的极大极小搜索一字棋的极大极小搜索人工智能初步用搜索解决问题AI培训教案ppt幻灯2022-11-5人工智能初步用搜索解决问题AI培训教案ppt幻灯