单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,2020/3/26,,‹#›,第五章,,状态空间搜索策略,,,,第五章,1,第5章 状态空间搜索策略,5.1 搜索的概念及种类,5.1.1 搜索的概念,5.1.2 搜索的种类,,5.2 盲目搜索策略,5.2.1 状态空间图的搜索策略,5.2.2 宽度优先搜索,5.2.3 深度优先搜索,5.2.4 有界深度优先搜索,5.2.5 代价树的宽度优先搜索,5.2.6 代价树的深度优先搜索,5.3 启发式搜索策略,5.3.1 启发信息与估价函数,5.3.2 最佳优先搜索,5.3.3 A*算法,,,,第5章 状态空间搜索策略5.1 搜索的概念及种类,2,需要重点掌握的问题,用,宽度优先搜索,和,深度优先搜索,求解,八数码问题,；,用,代价树的宽度优先搜索,和,深度优先搜索,求解推销员旅行问题；,用全局最佳优先搜索,八数码问题,需要重点掌握的问题用宽度优先搜索和深度优先搜索求解八数码问题,3,状态空间搜索策略,搜索是人工智能的基本问题，是推理不可分割的一部分,问题求解就是搜索过程,搜索对应的知识表示法,：,状态空间表示法、与/或树表示法,,,状态空间搜索策略搜索是人工智能的基本问题，是推理不可分割的一,4,,,人工智能状态空间搜索策略课件,5,,,人工智能状态空间搜索策略课件,6,,,人工智能状态空间搜索策略课件,7,,,人工智能状态空间搜索策略课件,8,,,人工智能状态空间搜索策略课件,9,,,人工智能状态空间搜索策略课件,10,,,人工智能状态空间搜索策略课件,11,（6）,对节点n进行扩展，将它的所有后继节点放入OPEN表的末端，并为这些后继节点设置指向父节点n的指针，然后转步骤（2）,,,,（6）对节点n进行扩展，将它的所有后继节点放入O,12,宽度优先搜索,1, G:=G0(G0=s), OPEN:=(s), CLOSED:=( );,2, LOOP: IF OPEN=( ) THEN EXIT (FAIL);,3, n:=FIRST(OPEN);,4, IF GOAL(n) THEN EXIT (SUCCESS);,5, REMOVE(n, OPEN), ADD(n, CLOSED);,6, EXPAND(n) →{mi}, G:=ADD(mi, G);,7,,ADD(OPEN, mj),,并标记mj,到n的指针;,8, GO LOOP;,,,宽度优先搜索1, G:=G0(G0=s), OPEN:=(s,13,,,人工智能状态空间搜索策略课件,14,,,人工智能状态空间搜索策略课件,15,,,人工智能状态空间搜索策略课件,16,,,人工智能状态空间搜索策略课件,17,,,人工智能状态空间搜索策略课件,18,深度优先搜索,1, G:=G0(G0=s), OPEN:=(s), CLOSED:=( );,2, LOOP: IF OPEN=( ) THEN EXIT (FAIL);,3, n:=FIRST(OPEN);,4, IF GOAL(n) THEN EXIT (SUCCESS);,5, REMOVE(n, OPEN), ADD(n, CLOSED);,6,,EXPAND(n) →{mi}, G:=ADD(mi, G);,7,,ADD(mj, OPEN),,并标记mj,到n的指针;,8,,GO LOOP;,,,深度优先搜索1, G:=G0(G0=s), OPEN:=(s,19,,,人工智能状态空间搜索策略课件,20,,,人工智能状态空间搜索策略课件,21,,,人工智能状态空间搜索策略课件,22,,,人工智能状态空间搜索策略课件,23,,,人工智能状态空间搜索策略课件,24,,,人工智能状态空间搜索策略课件,25,,,人工智能状态空间搜索策略课件,26,,,人工智能状态空间搜索策略课件,27,,,人工智能状态空间搜索策略课件,28,,,人工智能状态空间搜索策略课件,29,,,人工智能状态空间搜索策略课件,30,,,人工智能状态空间搜索策略课件,31,,,人工智能状态空间搜索策略课件,32,,,人工智能状态空间搜索策略课件,33,,,人工智能状态空间搜索策略课件,34,,,人工智能状态空间搜索策略课件,35,,,人工智能状态空间搜索策略课件,36,,,人工智能状态空间搜索策略课件,37,,,人工智能状态空间搜索策略课件,38,,,人工智能状态空间搜索策略课件,39,,,人工智能状态空间搜索策略课件,40,,,人工智能状态空间搜索策略课件,41,,,人工智能状态空间搜索策略课件,42,,,人工智能状态空间搜索策略课件,43,,,人工智能状态空间搜索策略课件,44,,,人工智能状态空间搜索策略课件,45,,,人工智能状态空间搜索策略课件,46,,,人工智能状态空间搜索策略课件,47,A算法,1, OPEN:=(s), f(s):=g(s)+h(s);,2, LOOP: IF OPEN=( ) THEN EXIT(FAIL);,3, n:=FIRST(OPEN);,4, IF GOAL(n) THEN EXIT(SUCCESS);,5, REMOVE(n, OPEN), ADD(n, CLOSED);,6, EXPAND(n),→{mi},,,计算f(n, mi):=g(n, mi)+h(mi);,7, OPEN,中的节点按f值从小到大排序；,8, GO LOOP；,,,,A算法1, OPEN:=(s), f(s):=g(s)+h(,48,,,人工智能状态空间搜索策略课件,49,,,人工智能状态空间搜索策略课件,50,,,人工智能状态空间搜索策略课件,51,一个A算法的例子,定义评价函数：,f(n) = g(n) + h(n),g(n)为从初始节点到当前节点的代价值,h(n)为当前节点“不在位”的位置数,,2 8 3,1 6 4,7 5,1 2 3,8 4,7 6 5,,,一个A算法的例子定义评价函数：2 8 31,52,h计算举例,h(n) =4,2,,8,3,1,,6,4,7 5,1 2 3,4,5,7 6,8,,,h计算举例 h(n) =4 2 8 31,53,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 3,1 8 4,7 6 5,2 3,1 8 4,7 6 5,1 2 3,8 4,7 6 5,1 2 3,8 4,7 6 5,1 2 3,7 8 4,6 5,s(4),A(6),B(4),C(6),D(5),E(5),F(6),G(6),H(7),I(5),J(7),K(5),L(5),M(7),目标,1,2,3,4,5,6,,,2 8 32 8 32 8 32,54,A*条件举例,8数码问题,h1(n) = “不在位”的将牌数,h2(n) =,将牌“不在位”的距离和,2,,8,3,1,,6,4,7 5,1 2 3,4,5,7 6,8,将牌1：1,将牌2：1,将牌6：1,将牌8：2,,,A*条件举例8数码问题2 8 31 2,55,第五章结束,谢谢您的使用,,,第五章结束谢谢您的使用,56,每一个优秀的人，都有一段沉默的时光。
那一段时光，是付出了很多努力，忍受孤独和寂寞，不抱怨不诉苦，日后说起时，连自己都能被感动日子11月-24,11月-24,Saturday, November 2, 2024,企业的出路在于产品更新换代23:31:30,23:31:30,23:31,11/2/2024 11:31:30 PM,在企业内部，只有成本11月-24,23:31:30,23:31,Nov-24,02-Nov-24,人人是人才，赛马不相马，给每一个愿意干事的人才以发挥才干的舞台23:31:30,23:31:30,23:31,Saturday, November 2, 2024,旁观者的姓名永远爬不到比赛的计分板上11月-24,11月-24,23:31:30,23:31:30,November 2, 2024,我不理解这句话的意思2024年11月2日,11:31 下午,11月-24,11月-24,渐进思想是创新的最大敌人02 十一月 2024,11:31:30 下午,23:31:30,11月-24,无须匆忙，该来的总会来，在对的时间，和对的人，因为对的理由十一月 24,11:31 下午,11月-24,23:31,November 2, 2024,人在得意时须沉得住傲气；失意时则要忍得住火气。
2024/11/2 23:31:30,23:31:30,02 November 2024,学而不厌，诲人不倦—《,论语,》,11:31:30 下午,11:31 下午,23:31:30,11月-24,管理就是把复杂的问题简单化，混乱的事情规划化11月-24,11月-24,23:31,23:31:30,23:31:30,Nov-24,金钱损失了还能挽回，一旦失去信誉就很难挽回2024/11/2 23:31:30,Saturday, November 2, 2024,自知之明是最难得的知识11月-24,2024/11/2 23:31:30,11月-24,谢谢各位！,每一个优秀的人，都有一段沉默的时光那一段时光，是付出了很多,57,。