下载文档原格式
第三章搜索推理技术3-1什么是图搜索过程?其中，重排OPEN表意味着什么，重排的原则是什么?图搜索的一般过程如下：(1) 建立一个搜索图G(初始只含有起始节点S)，把S放到未扩展节点表中（OPEN表）中。
(2) 建立一个已扩展节点表（CLOSED表），其初始为空表。
(3) LOOP：若OPEN表是空表，则失败退出。
(4) 选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。
称此节点为节点n，它是CLOSED表中节点的编号(5) 若n为一目标节点，则有解并成功退出。
此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)(6) 扩展节点n，生成不是n的祖先的那些后继节点的集合M。
将M添入图G中。
(7) 对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针，并将它们加进OPEN表。
对已经在OPEN或CLOSED表上的每个M成员，确定是否需要更改通到n的指针方向。
对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。
(8) 按某一任意方式或按某个探试值，重排OPEN表。
(9) GO LOOP。
重排OPEN表意味着，在第(6)步中，将优先扩展哪个节点，不同的排序标准对应着不同的搜索策略。
重排的原则当视具体需求而定，不同的原则对应着不同的搜索策略，如果想尽快地找到一个解，则应当将最有可能达到目标节点的那些节点排在OPEN表的前面部分，如果想找到代价最小的解，则应当按代价从小到大的顺序重排OPEN表。
3-2 试举例比较各种搜索方法的效率。
宽度优先搜索(1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。
(2) 如果OPEN是个空表，则没有解，失败退出；否则继续。
(3) 把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED扩展节点表中。
(4) 扩展节点n。
1． 在回溯法求解径时，当前状态的所有可用规则按某种固定原则排序，而不是对各可用规则进行评价，将可用规则按到达目标状态的可能性排序。
（√×）2． 在2阶梵塔问题中，若小盘和大盘分别表示为A 和B ，初始状态为（AB, —, —），即第1个柱上有两个盘，其他两个柱上无盘，另外，目标状态为（—, AB, —），请画出回溯算法的搜索树。
3． 深度优先和宽度优先是两个特别的图搜索法，即待扩展结点插入OPEN 表的位置按某种固定原则确定。
如果新扩展出的结点不在OPEN 或CLOSED 中，深度优先法将其放在OPEN 表的______，宽度优先法将其放在OPEN 表的______。
4． 在A 算法中，评价函数f(n)一般表示为g(n) + h(n)。
g(n)是g*(n)的估计，g*(n)的含义是________，g(n)一般按_______计算。
h(n)是h*(n)的估计，h*(n)的含义是_________，h(n)根据________计算。
5． 在A 算法中，有两个辅助的表，即OPEN 和CLOSED 表。
OPEN 表存放___________，且结点按_________排序，即优先扩展________结点，CLOSED 表存放___________。
6． A 算法中，如果新扩展出的结点已在CLOSED 表，通常将此结点放回OPEN 表，而不是考虑修改其子结点的指针。
（√×）7． 在分支界限法中，f(n) = g(n)，即h(n) = 0，故分支界限法也是一种A*算法。
（√×）8． 在分支界限法中，将初始结点到各叶子结点的所有路径存入一个队列，且队列按路径耗散非递减排序，若八城市间距如教材图1.11，起始结点为s 、目标结点为t ，请画出采用分支界限法的搜索（图）树。
9． 动态规划法是对分支界限法的一种改进，即只保留到叶子结点的最短路径。
若八城市间距如教材图1.11，起始结点为s 、目标结点为t ，请画出采用动态规划法的搜索（图）树。
1，AI:AI是人工智能英文单词Artificial Intelligence的缩写。
2，人工智能:人工智能是研究如何制造出人造的智能机器或智能系统，来模拟人类智能活动的能力，以延伸人们智能的科学。
3，产生式系统:产生式系统是Post于1943年提出的一种计算形式体系里所使用的术语，主要是使用类似于文法的规则，对符号串作替换运算。
到了60年代产生式系统成为认知心理学研究人类心理活动中信息加工过程的基础，并用它来建立人类认识的模型。
到现在产生式系统已发展成为人工智能系统中最典型最普遍的一种结构，例如目前大多数的专家系统都采用产生式系统的结构来建造。
产生式系统由综合数据库、一组产生式规则（规则集）和一个控制系统（控制策略）三部分组成，称为产生式系统的三要素。
4，产生式系统的三要素:产生式系统的三要素是综合数据库、一组产生式规则（规则集）和一个控制系统（控制策略）。
5，产生式规则:产生式规则是知识表示的一种形式，其形式如下： IF <前件> THEN <后件> 其中规则的<前件>表达的是该条规则所要满足的条件，规则的<后件>表示的是该规则所得出的结论，或者动作。
规则表达的可以是与待求解的问题有关的客观规律方面的知识，也可以是对求解问题有帮助的策略方面的知识。
6，八数码游戏（八数码问题）:八数码游戏（八数码问题）描述为：在3×3组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1-8八个数码中的某一个数码。
棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。
这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。
7，传教士和野人问题（M-C问题）:传教士和野人问题描述为：有N个传教士和N个野人来到河边准备渡河，河岸有一条船，每次至多可供k人乘渡。
只有一个孤独的影子，她，倚在栏杆上；她有眼，才从青春之梦里醒过来的眼还带着些朦胧睡意，望着这发狂似的世界，茫然地像不解这人生的谜。
她是时代的落伍者了，在青年的温馨的世界中，她在无形中已被摈弃了。
她再没有这资格，心情，来追随那些站立时代前面的人们了！在甜梦初醒的时候，她所有的惟有空虚，怅惘；怅惘自己的黄金时代的遗失。
咳！苍苍者天，既已给与人们的生命，赋与人们创造社会的青红，怎么又吝啬地只给我们仅仅十余年最可贵的稍纵即逝的创造时代呢？。
授课人：目录01提出问题02预备知识任务2——利用训练好的模型来辨识照片030405任务1——训练目标人脸识别模型解决方案随时人民生活水平的提高和手机照相功能的日趋完美，我们不经意中拍摄了很多值得回忆的时刻，一场说走就走的旅行途中也记录下许多令人心动的瞬间，不知不觉之中，我们身边保存了大量的生活相片。
然而，每当你想重温你或者他的系列照片时，或者想分享一张你特别满意的靓照，从众多的照片中一遍遍翻找这些照片的确是一件费时费力的事情。
这时，你可能会问：既然AI无时不在我们身边，能否借助AI的人脸识别技术来帮助我自动整理出我想要的照片，实现照片的智能搜索呢？答案无疑是肯定的。
下面，我们就利用人脸识别技术和OpenCV工具，对相册中的照片进行自动挑选以解决上述问题。
帮人从相册中找出指定人物的系列照片，对于人工操作而言，并不是一件困难的事情，但整理的效率可能不尽人意，毕竟手动翻阅每张照片是个耗时费力的事。
让计算机替代人来完成这个事，难点在于如何从被检照片中识别与目标人脸高度相似的人脸，如果被检照片中有此人，说明该照片就是你想要的那一张，否则，该照片被忽视。
因此，一种可行的方案是：首先训练计算机认识不同式样的同一系列人脸，让它知道其实这些照片上的人物是同为一个人，从而得到目标人脸训练模型；其次，遍历相册中的每张照片，检测出该照片上所有的人脸，提取人脸特征值，然后用目标人脸训练模型依次对人脸特征值进行预测比对，如果两者之间只要有一次高度匹配，就保留该照片，立即进入下一张照片的搜索，如果均不匹配，则忽视该照片，进行下一张搜索，直至搜索完所有的照片；最后得到的所有保留照片就是智能搜索的结果，至此，整个智能搜索照片过程结束。
问题的解决方案如下图所示。
解决方案利用OpenCV来智能搜索相片，有两个重要的环节，一是人脸区域的检测，这要用到前面提到的人脸检测器；二是基于人脸区域数据的人脸识别，这要用到人脸识别模型，下面分别来了解OpenCV中人类检测器和人脸识别模型的使用。
