盲目搜索启发式搜索ppt

◦ 以上问题等价于在图中寻找从根节点到某个（或某些）
目标节点的一条（或一组）路径。

1 问题状态空间的构成
状态空间表示法是以“状态空间”的形式对问题 进行表示。 1）状态：是描述问题求解过程中不同时刻状况的 数据结构。一般用一组变量的有序集合表示：Q＝（q1， q2，…，qn） 其中每个元素qi为集合的分量，称为状态 变量，当给每个分量以确定的值时，就得到了一个具体的 状态。
2
3 1 3
2 1
3
2 1 3 1 1
2 3 2 3
2
1
初始棋局
17
目标棋局

产生式系统（production system）
◦ 一个总数据库：它含有与具体任务有关的信息。随着应 用情况的不同，这些数据库可能简单，或许复杂。 ◦ 一套规则：它对数据库进行操作运算。每条规则由左部
鉴别规则的适用性或先决条件以及右部描述规则应用时所 完成的动作。 ◦ 一个控制策略：它确定应该采用哪一条适用规则，而且 当数据库的终止条件满足时，就停止计算。
Q () Q Q
((1,1))
((1,1) (2,3))
((1,1) (2,4))
((1,1) (2,4) (3,2))
Q () Q
((1,1))
((1,1) (2,3))
((1,1) (2,4))
((1,1) (2,4) (3,2))
Q ()
((1,1))
((1,1) (2,3))
((1,1) (2,4))
◦ 系统状态的描述 四个皇后 ((i1,j1), (i2,j2), (i3,j3), (i4,j4))
()
Q ()
((1,1))
Q ()

39、没有不老的誓言，没有不变的承 诺，踏 上旅途 ，义无 反顾。 40、对时间的价值没有没有深切认识 的人， 决不会 坚韧勤 勉。
21、要知道对好事的称颂过于夸大，也会招来人们的反感轻蔑和嫉妒。——培根 22、业精于勤，荒于嬉；行成于思，毁于随。——韩愈
23、一切节省，归根到底都归结为时间的节省。——马克思 24、意志命运往往背道而驰，决心到最后会全部推倒。——莎士比亚
25、学习是劳动，是充Βιβλιοθήκη 思想的劳动。——乌申斯基谢谢！
人工智能第1章盲目搜索
36、“不可能”这个字(法语是一个字 )，只 在愚人 的字典 中找得 到。--拿 破仑。 37、不要生气要争气，不要看破要突 破，不 要嫉妒 要欣赏 ，不要 托延要 积极， 不要心 动要行 动。 38、勤奋，机会，乐观是成功的三要 素。(注 意：传 统观念 认为勤 奋和机 会是成 功的要 素，但 是经过 统计学 和成功 人士的 分析得 出，乐 观是成 功的第 三要素 。

7 283 714 65 15 2 8 3 714 6 5 24 2 8 3 7 4 615
16 1 2 3 84 765 26 25 2 8 3 1 2 3 1 2 3 714 8 4 784 65 765 65
234 234 28 248 1 8 185 143 1 3 765 76 765 765
3.1 盲目搜索
3.1.2 宽度优先搜索
定义3.1 如果搜索是以接近起始节点的程度依次扩展节点的， 那么这种搜索就叫做宽度优先搜索（breadth-first search)
3.1 盲目搜索
3.1.2 宽度优先搜索
宽度优先搜索算法 (1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点， 则求得一个解答)。 (2) 如果OPEN是个空表，则没有解，失败退出；否则继续。 (3) 把第一个节点(节点n)从OPEN表移出，并把它放入 CLOSED的扩展节点表中。 (4) 扩展节点n。如果没有后继节点，则转向上述第(2)步。 (5) 把n的所有后继节点放到OPEN表的末端，并提供从这些后 继节点回到n的指针。 (6) 如果n的任一个后继节点是个目标节点，则找到一个解答， 成功退出；否则转向第(2)步。
9
2 5 1 4 6 7 3 8 2 5 1 4 6 7 3 8 2 4 5 1 6 7 3 8 2 4 5 1 6 7 3 8 2 4 5 1 3 6 7 8 2 4 5 1 6 7 3 8 2 4 5 1 3 6 7 8 2 4 5 1 3 6 72 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 3
4.图搜索方法分析：
图搜索过程的第8步对OPEN表上的节点进行排序，以便能够 从中选出一个“最好”的节点作为第4步扩展用。这种排序可 以是任意的即盲目的(属于盲目搜索)，也可以用以后要讨论的 各种启发思想或其它准则为依据(属于启发式搜索)。每当被选 作扩展的节点为目标节点时，这一过程就宣告成功结束。这时， 能够重现从起始节点到目标节点的这条成功路径，其办法是从 目标节点按指针向S返回追溯。当搜索树不再剩有未被扩展的 端节点时，过程就以失败告终(某些节点最终可能没有后继节 点，所以OPEN表可能最后变成空表)。在失败终止的情况下， 从起始节点出发，一定达不到目标节点。

→(1,1,1,0) →(0,0,1,0)→(1,0,1,1)→(0,0,1,1) →(0,1,0,0)→(1,1,0,1)→(0,1,0,1) →(1,1,1,1)ok →(0,1,1,0)
22.03.2021
.
9
过河问题（con 4）
搜索在“图”中进行，但图不需要事先建立 （“隐式图”）。
搜索过程就是对图的遍历过程，可以得到一 棵“搜索树”。
ACM/ICPC 之 搜索篇
SEARCHING STRATEGIES
搜索概论
搜索被称为“通用解题法”，在算法和人工 智能中占据重要地位。
但由于它巨大的局限性和自身灵活性，也被 认为是最难学难用的算法之一。
本节目标：希望同学们对于任意一个问题， 1.很快建立状态空间 2.提出一个合理算法 3.简单估计时空性能
取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;
} 若循环中找到目标,输出结果; 否则输出无解;
22.03.2021
.
19
v1
0
V1
定义一个队列; 起始点加入队列; while(队列不空){
取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;
起始状态(0,0,0,0)，终止状态(1,1,1,1) 状态转移规则：
(a,b,c,d) →(1-a,1-b,c,d)（当a=b） →(1-a,b,1-c,d)（当a=c） →(1-a,b,c,1-d)（当a=d） →(1-a,b,c,d)
约束：(a,b,c,d)中，当a≠b时b≠c；当a≠c时c≠d
22.03.2021
.
13
BFS思想
1的.从(所图有中未某被顶访点问v的0出)邻发接，顶在点访v问1了.vv20…之后，搜索v0 2.依次从这些邻接顶点出发，广搜图中其它顶点，

①、起 始节点 ( 即根
节点)的深度为0。
②、任何其它节点的
深度等于其父辈
节点深度加上1。
深度优先搜索的基本
思路：
先扩展最深的节点 。
当出现没有后继节点
时，换到旁边的次深
节点
后生成的节点画在左边
含有深度界限的深度优先搜索算法：
① 把起始节点 S 放到未扩展节点的 OPEN 表中。 如果此节点为一目标节点，则得到解 ② 如果 OPEN 为一空表，则无解、失败退出
状态：长度为9的一维数组
（q1 , q2 , … , q9 ）
其中，qi 取 0 , 1 , … , 8 个数，0 表示空格，且取值
互不相同
如果记空格的位置为P，这时空格的移动规则是： 1 4 7 2 5 8 3 6 9 数字表示位置 1 2 3 4 5 6 7 8 9 P-3
P-1
P
P+1
P+3
起始节点的父节点标志和操作符：
不作记录或记录为负
搜索过程（按照程序运行方式）
① 起始节点放到OPEN表
2 8 3 1 0 4
2 8 3 1 4 7 6 5 7 6 5
② OPEN不为空，继续
③ 将第一个节点 n 从 OPEN 表中移出，并放到 CLOSED表中 OPEN表
CLOSED表 1 0 0 2 8
13
14
1
4
2
8
8
3
3
0
1
2
4
1
5
4
7
7
0
6
6
5
1 8
7
2
3 4
14 15 15
16 16
3 2 4

迭代加深搜索是最优的，也是完备的 重复搜索深度较小的节点，是否浪费？
10
例 聪明的打字员
阿兰是某机密部门的打字员，她现在接到一个 任务：需要在一天之内输入几百个长度固定为 6的密码。当然，她希望输入的过程中敲击键 盘的总次数越少越好。
不幸的是，出于保密的需要，该部门用于输入 密码的键盘是特殊设计的，键盘上没有数字键， 而只有以下六个键：Swap0, Swap1, Up, Down, Left, Right，为了说明这6个键的作用，我们先 定义录入区的6个位置的编号，从左至右依次 为1，2，3，4，5，6。
宽度优先搜索（Breadth-first search） 深度优先搜索（Depth-first search）
6
宽度优先搜索
优点
目标节点如果存在，用宽度优先搜索算法总可 以找到该目标节点，而且是最小（即最短路径） 的节点
缺点
当目标节点距离初始节点较远时，会产生许多 无用的节点，搜索效率低
11
例 聪明的打字员
Swap0：按Swap0，光标位置不变，将光标所在位置的数字与录入区的1号位置 的数字（左起第一个数字）交换。如果光标已经处在录入区的1号位置，则按 Swap0键之后，录入区的数字不变
Swap1：按Swap1，光标位置不变，将光标所在位置的数字与录入区的6号位置 的数字（左起第六个数字）交换。如果光标已经处在录入区的6号位置，则按 Swap1键之后，录入区的数字不变
4
搜索问题
搜索问题：在一个空间中寻找目标
搜索什么（目标） 在哪里搜索（状态空间）
在搜索中，如何扩展状态空间是关键性问题 搜索可以根据是否使用启发式信息分成
盲目搜索：只能区分当前状态是否为目标状态 启发式搜索：在搜索过程中加入与问题相关的

(6) 扩展节点n，同时生成不是n的祖先的那些后继节点 的集合M。把M的这些成员作为n的后继节点添入图 G中。
(7) 对那些未曾在G中出现过的(既未曾在OPEN表上或 CLOSED表上出现过的)M成员设置一个通向n的指针。 把 M 的 这 些 成 员 加 进 OPEN 表 。 对 已 经 在 OPEN 或 CLOSED表上的每一个M成员，确定是否需要更改通 到n的指针方向。对已在CLOSED表上的每个M成员， 确定是否需要更改图G中通向它的每个后裔节点的 指针方向。
搜索原理
什么是搜索？ 根据问题的实际情况不断寻找可利用的知识，从而构造 一条代价较少的推理路线，使问题得到圆满解决的过程。
• 盲目搜索 按预定的控制策略进行搜索，在搜索过程中获得的中间 信息不用来改进控制策略。效率低、主要用于简单问 题求解。
• 启发式搜索 在搜索中加入了与问题有关的启发性信息，用以指导搜 索朝着最有希望的方向前进，加速问题的求解过程并 找到最优解。
(3)LOOP：若OPEN表是空表，则失败退出。 (4) 选择OPEN表上的第一个节点，把它从OPEN表移出
并放进CLOSED表中。称此节点为节点n。 (5) 若n为一目标节点，则有解并成功退出，此解是追
踪图G中沿着指针从n到S这条路径而得到的(指针将 在第7步中设置)。
峰谷书屋
10
图搜索的一般过程
峰谷书屋
7
OPEN表变化过程
节点号 父节点号
S0
空
A
S0
B
S0
C
S0
D
S0
E
A
F
A
峰谷书屋
8
CLOSED表变化过程
编号
0 1 2
节点号

或树搜索2盲目搜索
36、如果我们国家的法律中只有某种 神灵， 而不是 殚精竭 虑将神 灵揉进 宪法， 总体上 来说， 法律就 会更好 。—— 马克·吐 温 37、纲纪废弃之日，便是暴政兴起之 时。— —威·皮 物特
38、若是没有公众舆论的支持，法律 是丝毫 没有力 量的。速累 聚，进 而变成 法律。 ——朱 尼厄斯
40、人类法律，事物有规律，这是不 容忽视 的。— —爱献 生
1、最灵繁的人也看不见自己的背脊。——非洲 2、最困难的事情就是认识自己。——希腊 3、有勇气承担命运这才是英雄好汉。——黑塞 4、与肝胆人共事，无字句处读书。——周恩来 5、阅读使人充实，会谈使人敏捷，写作使人精确。——培根