人工智能 AI讲稿5(搜索student).ppt

《人工智能 AI讲稿5(搜索student).ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、人工智能（ArtificialIntelligence）基本原理福州大学数学与计算机学院陈昭炯7/28/2021第六章搜索策略基本概念状态空间的搜索策略与/或树的搜索策略搜索的完备性与效率一般图的搜索过程广度优先搜索深度优先搜索有界深度优先搜索代价树的广度优先搜索代价树的深度优先搜索启发式搜索A*算法与/或树的一般搜索过程与/或树的广度优先搜索与/或树的深度优先搜索与/或树的有序搜索博弈树的启发式搜索－剪枝技术搜索的含义状态空间表示法与/或树表示法搜索的含义依问题的实际情况寻找可利用的知识，构造代价较少的推理路径从而解决问题的过程离

2、散的问题通常没有统一的求解方法搜索策略的优劣涉及能否找到最好的解、计算时间、存储空间等搜索分为盲目搜索和启发式搜索盲目搜索：按预定的策略进行搜索，未用问题相关的或中间信息改进搜索。效率不高，难求解复杂问题，但不失可用性启发式搜索：搜索中加入问题相关的信息加速问题求解，效率较高，但启发式函数不易构造讨论的问题有哪些常用的搜索算法?－问题有解时能否找到解?(完备性)找到的解是最佳的吗？(最优性)－什么情况下可以找到最佳解？求解的效率如何?（时间、空间复杂度）基本概念状态空间表示法状态：描述问题求解中任一时刻的状况；变量的有序组合算符：一个状

3、态→另一状态的操作状态空间：{状态，算符}表示,描述形式＋算符问题求解过程：初始状态：描述问题求解中的初始状况算符：一个状态→另一状态的操作目标测试：确定给定的状态是否为目标状态路径耗散函数：设定每一步算符操作的耗散值问题的解：从初始状态到目标状态的路径最优解：所有解中耗散值最小的解例：二阶梵塔问题状态描述：（SA,SB）可能状态：S0=(1,1),S=(1,2),S=(1,3),S=(2,1),Sg=(2,2),S=(2,3)S=(3,1),S=(3,2),Sg=(3,3)算符：A(i,j)—将A从i轴移至j轴;B(i,j)—将B从i

4、轴移至j轴可能算符：A(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2)B(1,2),B(1,3),B(2,1),B(2,3),B(3,1),B(3,2)猴子摘香蕉问题abc操作符：Goto(u):猴子走到u处(w,t,x,y,0)→(u,t,x,y,0)Push(v):猴子推箱到v处(w,t,w,0,0)→(v,t,v,0,0)Climb:猴子爬上箱子(w,t,w,0,0)→(w,t,w,1,0)Grasp:猴子拿到香蕉(a,a,a,1,0)→(a,a,a,1,1)状态：(w,t,x,y,z)w:猴子的水

5、平位置{a,b,c}t:天花板上香蕉对应的地面位置{a,b,c}x:箱子的水平位置{a,b,c}y:猴子是否在箱子上{0,1}z:猴子是否拿到香蕉{0,1}初始状态：(c,a,b,0,0)目标状态：(a,a,a,1,1)可能状态：(b,a,b,0,0)(c,a,c,1,0)(c,a,c,1,1)……例：修道士与野人问题(1968)S0：河左岸有3个Missionaries和3个Cannibals,1条boat条件：1）M和C都会划船，船一次只能载2人2）在任一岸上，M人数不得少于C的人数，否则被吃目标：安全抵达对岸左岸：(m,c,b)：

6、0≤m,c≤3，b∈{0,1}S0：(3,3,1)Sg：(0,0,0)状态总数：4×4×2＝32种，但合法状态16种(3,3,1)(3,1,0)(2,2,0)(3,2,0)(3,2,1)(3,0,0)(3,1,1)(1,1,0)(2,2,1)(0,2,0)(0,3,1)(0,1,0)(0,2,1)(0,0,0)0

7、耗散值1将4个皇后放到棋盘中，使得彼此不会攻击到（不同行、不同列、不同对角线）返回8皇后，92种解找到一般n皇后问题复杂度为O(n)的算法(1989)QQQQ2831647512384765例：八数码游戏8-Puzzle（九宫重排问题）sliding-blockpuzzle初始状态：任一状态都可为初始状态算符：将空位移向四个方向目标测试：确定当前状态是否为目标状态路径耗散函数：每一步耗散值1其状态可以划分为两个不相交的集合。(证明)8数码，9！/2＝181440；15数码，1.3万亿；24数码,1025一般n×n数码是NP完全问题（19

8、86）例：TSP问题TravelingSalesmanProblem从某城市出发遍历所有n个城市一遍且仅一遍再回到出发地，求最短路径初始状态：在某一城市算符：移向下一个未访问过的城市目标测试：是否处于出发地