第一部分搜索问题教学课件.ppt
《第一部分搜索问题教学课件.ppt》由会员分享,可在线阅读,更多相关《第一部分搜索问题教学课件.ppt(102页珍藏版)》请在三一文库上搜索。
1、第一章 搜索问题 内容: 状态空间的搜索问题。 搜索方式: 盲目搜索 启发式搜索 关键问题: 如何利用知识,尽可能有效地找到问题 的解(最佳解)。 1 搜索问题(续1) S0 Sg 2 搜索问题(续2) 讨论的问题: 有哪些常用的搜索算法。 问题有解时能否找到解。 找到的解是最佳的吗? 什么情况下可以找到最佳解? 求解的效率如何。 3 1.1 回溯策略 例:皇后问题 4 ( ) 5 ( ) Q (1,1) 6 ( ) Q Q (1,1) (1,1) (2,3) 7 ( ) Q (1,1) (1,1) (2,3) 8 ( ) Q Q (1,1) (1,1) (2,3) (1,1) (2,4) 9
2、 ( ) Q Q (1,1) (1,1) (2,3) (1,1) (2,4) Q (1,1) (2,4) (3.2) 10 ( ) Q Q (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) 11 ( ) Q (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) 12 ( ) (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) 13 ( ) (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) Q (1,2) 14 ( )
3、(1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) Q (1,2) Q (1,2) (2,4) 15 ( ) (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) Q (1,2) Q (1,2) (2,4) Q (1,2) (2,4) (3,1) 16 ( ) (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) Q (1,2) Q (1,2) (2,4) Q (1,2) (2,4) (3,1) Q (1,2) (2,4) (3,1) (4,3) 17 递归的思想 从
4、前有座山 从前有座山 从前有座山 18 递归的思想(续) 当前状态 目标状态g 19 一个递归的例子 int ListLenght(LIST *pList) if (pList = NULL) return 0; else return ListLength(pList-next)+1; NULL pLIST 123 20 回溯搜索算法 BACKTRACK(DATA) DATA:当前状态。 返回值:从当前状态到目标状态的路径 (以规则表的形式表示) 或FAIL。 21 回溯搜索算法 递归过程BACKTRACK(DATA) 1, IF TERM(DATA) RETURN NIL; 2, IF D
5、EADEND(DATA) RETURN FAIL; 3, RULES:=APPRULES(DATA); 4, LOOP: IF NULL(RULES) RETURN FAIL; 5, R:=FIRST(RULES); 6,RULES:=TAIL(RULES); 7,RDATA:=GEN(R, DATA); 8,PATH:=BACKTRACK(RDATA); 9,IF PATH=FAIL GO LOOP; 10,RETURN CONS(R, PATH); 22 存在问题及解决办法 解决办法: 对搜索深度加以限制 记录从初始状态到当前状态的路径 当前状态 l问题: 深度问题 死循环问题 23 回溯
6、搜索算法1 BACKTRACK1(DATALIST) DATALIST:从初始到当前的状态表(逆向 ) 返回值:从当前状态到目标状态的路径 (以规则表的形式表示) 或FAIL。 24 回溯搜索算法1 1, DATA:=FIRST(DATALIST) 2, IF MENBER(DATA, TAIL(DATALIST) RETURN FAIL; 3, IF TERM(DATA) RETURN NIL; 4, IF DEADEND(DATA) RETURN FAIL; 5, IF LENGTH(DATALIST)BOUND RETURN FAIL; 6, RULES:=APPRULES(DATA);
7、 7, LOOP: IF NULL(RULES) RETURN FAIL; 8,R:=FIRST(RULES); 25 回溯搜索算法1(续) 9,RULES:=TAIL(RULES); 10,RDATA:=GEN(R, DATA); 11,RDATALIST:=CONS(RDATA, DATALIST); 12,PATH:=BACKTRCK1(RDATALIST) 13,IF PATH=FAIL GO LOOP; 14,RETURN CONS(R, PATH); 26 一些深入的问题 失败原因分析、多步回溯 Q Q 27 一些深入问题(续) 回溯搜索中知识的利用 基本思想(以皇后问题为例):
8、尽可能选取划去对角线上位置数最少的 。 QQQ Q 3 2 2 3 28 1.2 图搜索策略 问题的引出 回溯搜索:只保留从初始状态到当前状态的 一条路径。 图搜索:保留所有已经搜索过的路径。 29 一些基本概念 节点深度: 根节点深度=0 其它节点深度=父节点深度+1 0 1 2 3 30 一些基本概念(续1) 路径 设一节点序列为(n0, n1,nk),对于i=1,k ,若节点ni-1具有一个后继节点ni,则该序 列称为从n0到nk的路径。 路径的耗散值 一条路径的耗散值等于连接这条路径各节 点间所有耗散值的总和。用C(ni, nj)表示从 ni到nj的路径的耗散值。 31 一些基本概念(
9、续1) 扩展一个节点 生成出该节点的所有后继节点,并给出 它们之间的耗散值。这一过程称为“扩展 一个节点”。 32 一般的图搜索算法 1, G=G0 (G0=s), OPEN:=(s); 2, CLOSED:=( ); 3, LOOP: IF OPEN=( ) THEN EXIT(FAIL); 4, n:=FIRST(OPEN), REMOVE(n, OPEN), ADD(n, CLOSED); 5, IF GOAL(n) THEN EXIT(SUCCESS); 6, EXPAND(n)mi, G:=ADD(mi, G); 33 一般的图搜索算法(续) 7, 标记和修改指针: ADD(mj,
10、OPEN), 并标记mj到n的指针; 计算是否要修改mk、ml到n的指针; 计算是否要修改ml到其后继节点的指针 ; 8, 对OPEN中的节点按某种原则重新排序; 9, GO LOOP; 34 节点类型说明 . . mjmk ml 35 修改指针举例 1 2 3 4 5 6 s 36 修改指针举例(续1) 1 2 3 4 5 6 s 37 1 2 3 4 5 6 修改指针举例(续2) s 38 1 2 3 4 5 6 修改指针举例(续3) s 39 1.3 无信息图搜索过程 深度优先搜索 宽度优先搜索 40 深度优先搜索 1, G:=G0(G0=s), OPEN:=(s), CLOSED:=(
11、 ); 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, IF DEPTH(n)Dm GO LOOP; 7, EXPAND(n) mi, G:=ADD(mi, G); 8, IF 目标在mi中 THEN EXIT(SUCCESS); 9, ADD(mj, OPEN), 并标记mj到n的指针; 10, GO LOOP; 41 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6
12、5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 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 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 1 2 3 7 8 4 6 5 1 2 3 8 4 7 6 5 2 8 3 6 4 1 7 5 2 8 3 1 6 7 5 4 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4
13、5 7 6 1 2 3 4 5 6 78 9 ab c d 1 2 3 8 4 7 6 5 目标 42 深度优先搜索的性质 一般不能保证找到最优解 当深度限制不合理时,可能找不到解, 可以将算法改为可变深度限制 最坏情况时,搜索空间等同于穷举 与回溯法的差别:图搜索 是一个通用的与问题无关的方法 43 宽度优先搜索 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, REMOV
14、E(n, OPEN), ADD(n, CLOSED); 6, EXPAND(n) mi, G:=ADD(mi, G); 7, IF 目标在mi中 THEN EXIT(SUCCESS); 8, ADD(OPEN, mj), 并标记mj到n的指针; 9, GO LOOP; 44 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 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 8 3 7 1 4 6 5 8
15、3 2 1 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 1 2 3 7 8 4 6 5 1 2 3 8 4 7 6 5 1 2 5 67 3 1 2 3 8 4 7 6 5 目标 8 2 3 4 1 8 7 6 5 4 45 宽度优先搜索的性质 当问题有解时,一定能找到解 当问题为单位耗散值,且问题有解时, 一定能找到最优解 方法与问题无关,具有通用性 效率较低 属于图搜索方法 46 渐进式深度优先搜索方法 目的 解决宽度优先方法的空间问题和回溯方法不 能找到最优解的问题。 思想 首先给回溯法一个比较小的深度限制,然后逐 渐增加深度限制,直到找到解或找遍所以
16、分支 为止。 47 1.4 启发式图搜索 利用知识来引导搜索,达到减少搜索范 围,降低问题复杂度的目的。 启发信息的强度 强:降低搜索工作量,但可能导致找不到最 优解 弱:一般导致工作量加大,极限情况下变为 盲目搜索,但可能可以找到最优解 48 希望: 引入启发知识,在保证找到最佳解的情 况下,尽可能减少搜索范围,提高搜索 效率。 49 基本思想 定义一个评价函数f,对当前的搜索状态 进行评估,找出一个最有希望的节点来 扩展。 50 1,启发式搜索算法A(A算法) 评价函数的格式: f(n) = g(n) + h(n) f(n):评价函数 h(n):启发函数 51 符号的意义 g*(n):从s
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第一 部分 搜索 问题 教学 课件
链接地址:https://www.31doc.com/p-3114438.html