文档介绍：会计学
1
华工人工智能复****重点总结
AI的研究内容
搜索技术
知识表示
规划方法
机器学****br/>认知科学
第1页/共18页
3
第一章 搜索问题
内容：
状态空间的搜索问题。
搜索方式：
盲目搜索
启发式搜索
关键问题：
如何利用知识，尽可能有效地找到问题的解（最佳解）。
第2页/共18页
4
回溯搜索算法
递归过程BACKTRACK(DATA)
1, IF TERM(DATA) RETURN NIL;
2, IF DEADEND(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);
第3页/共18页
5
回溯搜索算法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, LOOP: IF NULL(RULES) RETURN FAIL;
8, R:=FIRST(RULES);
第4页/共18页
6
回溯搜索算法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);
第5页/共18页
7
图搜索策略
问题的引出
回溯搜索：只保留从初始状态到当前状态的一条路径。
图搜索：保留所有已经搜索过的路径。
第6页/共18页
8
一些基本概念
节点深度：
根节点深度=0
其它节点深度=父节点深度+1
0
1
2
3
第7页/共18页
9
一般的图搜索算法
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);
第8页/共18页
10
一般的图搜索算法（续）
7, 标记和修改指针：
ADD(mj, OPEN), 并标记mj到n的指针；
计算是否要修改mk、ml到n的指针；
计算是否要修改ml到其后继节点的指针；
8, 对OPEN中的节点按某种原则重新排序；
9, GO LOOP；
第9页/共18页