盲目搜索与探索

第五章状态空间搜索策略搜索是人工智能的一个基本问题，是推理不可分割的一部分。

搜索是求解问题的一种方法，是根据问题的实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的推理路线的过程。

搜索包含两层含义：一层含义是要找到从初始事实到问题最终答案的一条推理路线；另一层含义是找到的这条路线是时间和空间复杂度最小的求解路线。

搜索可分为盲目搜索和启发式搜索两种。

1．1 盲目搜索策略1．状态空间图的搜索策略为了利用搜索的方法求解问题，首先必须将被求解的问题用某种形式表示出来。

一般情况下，不同的知识表示对应着不同的求解方法。

状态空间表示法是一种用“状态”和“算符”表示问题的方法。

状态空间可由一个三元组表示(S，F，Sg)。

利用搜索方法求解问题的基本思想是：首先将问题的初始状态(即状态空间图中的初始节点)当作当前状态，选择一适当的算符作用于当前状态，生成一组后继状态(或称后继节点)，然后检查这组后继状态中有没有目标状态。

如果有，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解；若没有，则按照某种控制策略从已生成的状态中再选一个状态作为当前状态，重复上述过程，直到目标状态出现或不再有可供操作的状态及算符时为止。

算法5．1 状态空间图的一般搜索算法①建立一个只含有初始节点S0的搜索图G，把S放入OPEN表中。

②建立CLOSED表，且置为空表。

③判断OPEN表是否为空表，若为空，则问题无解，退出。

④选择OPEN表中的第一个节点，把它从OPEN表移出，并放入CLOSED表中，将此节点记为节点n。

⑤考察节点n是否为目标节点，若是，则问题有解，并成功退出。

问题的解的这条路径得到。

即可从图G中沿着指针从n到S⑥扩展节点n生成一组不是n的祖先的后继节点，并将它们记作集合M，将M中的这些节点作为n的后继节点加入图G中。

⑦对那些未曾在G中出现过的(即未曾在OPEN表上或CLOSED表上出现过的)M中的节点，设置一个指向父节点(即节点n)的指针，并把这些节点加入OPEN 表中；对于已在G中出现过的M中的那些节点，确定是否需要修改指向父节点(n 节点)的指针；对于那些先前已在G中出现并且已在COLSED表中的M中的节点，确定是否需要修改通向它们后继节点的指针。

盲目搜索搜索的含义依问题的实际情况寻找可利用的知识，构造代价较少的推理路径从而解决问题的过程离散的问题通常没有统一的求解方法搜索策略的优劣涉及能否找到最好的解、计算时间、存储空间等搜索分为盲目搜索和启发式搜索盲目搜索：按预定的策略进行搜索，未用问题相关的或中间信息改进搜索。

效率不高，难求解复杂问题，但不失可用性启发式搜索：搜索中加入问题相关的信息加速问题求解，效率较高，但启发式函数不易构造盲目搜索也叫无信息搜索，只适合用于求解比较简单的问题。

我们没有指定问题的任何推理信息，例如要搜索这一部分而不是另一部分，就像到目前为止的只要发现一条到目标的路径即可。

这种过程被称为是盲目的。

盲目搜索过程只把算子应用到节点，它没有使用问题领域的任何特殊知识（除了关于什么动作是合法的知识外）。

最简单的盲目搜索过程就是广度优先搜索。

该过程把所有的算子应用到开始节点以产生一个显式的状态空间图，再把所有可能的算子应用到开始节点的所有直接后继，再到后继的后继，等等。

搜索过程一律从开始节点向外扩展。

由于每一步将所有可能的算子应用到一个节点，因此可把它们组成一个叫后继函数的函数。

当把后继函数应用到一个节点时，产生一个节点集，该节点集就是把所有能应用到那个节点的算子应用到该节点而产生的。

一个节点的后继函数的每一次应用称为节点的扩展相同代价搜索是广度优先搜索的一种变体，在该方法中，节点从开始节点顺着代价等高点向外扩展，而不是顺着相同深度等高线。

如果图中所有弧的代价相同，那么相同代价搜索就和广度优先搜索一致。

反过来，相同代价搜索可以看作是下一章要讲的启发式搜索的一个特殊情况。

广度优先和相同代价搜索方法的简要描述只给出了它们的主要思想，但是要解决其他复杂的情况则需要技术改进深度优先搜索一次对节点应用一个算子以产生该节点的一个后继。

每一个节点都留下一个标记，用来指示如果需要时所必需的附加算子。

对每一个节点，必须有一个决策来决定哪个算子先用，哪个次之等等。

实验二搜索问题形式化和无信息搜索（2学时）一实验目的熟悉和掌握搜索问题形式化方法与步骤，使用Python语言实现搜索问题形式化；掌握基本无信息搜索算法，实现算法并验证。

二实验原理搜索问题形式化即把要解决的问题描述为搜索问题，主要包括确定状态空间，初始状态，后继函数，目标测试及耗散等5方面内容；对于搜索问题可以应用通用的搜索算法求解，主要包括无信息(盲目)搜索和有信息搜索两大类，基本的无信息搜索有广度优先搜索和深度优先搜索。

三实验条件1 Python解释器，及IDLE等程序开发调试环境。

2 本实验所提供的几个Python文件，包括:mazeworld.py 用于构造、编辑、显示迷宫问题，以及对迷宫进行简单搜索；search.py 编写搜索算法代码。

实验要求的所有搜索Agent将通过改写本文件中类SearchAgent的solve方法来实现；util.py 实现搜索算法可能使用到的一些数据结构；eightpuzzle.py 用于构造、编辑、显示8数码问题；maze1.txt maze2.txt maze3.txt 迷宫文本文件。

四实验内容1 搜索问题形式化2 广度优先搜索3 深度优先搜索五实验步骤1 建立文件夹，将实验提供的4个Python文件和3个文本文件拷到文件夹中，注意整个文件夹路径不能有中文字符2 构造、编辑、显示迷宫问题运行Python IDLE，在>>>提示符下输入import mazeworld此时会出现错误提示，分析为什么出错#之所以会出现错误，是因为在sys的导入路径（path）中没有mazeworld.py文件的路径，这是用户自定#义的的路径，需要手工导入，即使用下面的方法import syssys.path['D:\\Python27\\Lib\\idlelib', 'C:\\WINDOWS\\SYSTEM32\\python27.zip','D:\\Python27\\DLLs', 'D:\\Python27\\lib', 'D:\\Python27\\lib\\plat-win','D:\\Python27\\lib\\lib-tk','D:\\Python27','D:\\Python27\\lib\\site-packages']#这里是你sys初始导入路径>>> sys.path.append('D:\QQPCmgr\Desktop\BlindSearchProject')#这里是你sys新增的导入路径>>> sys.path['D:\\Python27\\Lib\\idlelib', 'C:\\WINDOWS\\SYSTEM32\\python27.zip','D:\\Python27\\DLLs', 'D:\\Python27\\lib', 'D:\\Python27\\lib\\plat-win','D:\\Python27\\lib\\lib-tk', 'D:\\Python27','D:\\Python27\\lib\\site-packages', 'D:\\QQPCmgr\\Desktop\\BlindSearchProject']#新增导入路径后确认路径导入成功>>> import mazeworld此时，不再有出错提示，成功,分析成功原因#由于此时系统具有了mazeworld.py文件所在文件夹的路径，故当使用import命令时，系统会自动来到#这个文件夹进查找，当然就可找到而不会出错了#同时还有可能是因为版本问题出现报错，因为python2和python3要求的输出语言的代码不同#python2系列可以支持 print “xxxx”，python系列需要使用print("xxx") simpleMaze = mazeworld.Maze([['#', ' ', ' ', ' '], ['~', 'S', ' ', 'E']])print simpleMaze理解迷宫的表现形式#输出的迷宫为- - - -|# ||~ S E|- - - -#迷宫最典型的表现形式便是矩阵，而此处的迷宫也同样如此。

人工智能搜索技术初探【摘要】本文简要概述了人工智能搜索技术，分别对盲目搜索和启发式搜索做了阐述，并且用深度优先搜索初步分析了野人和牧师过河问题，用A*算法初步分析了九宫图问题。

【关键词】搜索技术；盲目搜索；启发式搜索；宽度优先搜索；深度优先搜索；野人与牧师；A*算法；九宫图；搜索技术是人工智能的基本技术之一，在人工智能各应用领域中被广泛地使用。

早期的人工智能程序与搜索技术联系更为密切，几乎所有早期的人工智能程序都是以搜索技术为基础的。

例如，A.Newell和H.A.Simon等人编写的LT（Logic Theorist）程序。

现在，搜索技术渗透在各种人工智能系统中，可以说没有哪一种人工智能系统应用不到搜索方法。

在专家系统、自然语言理解、自动程序设计、模式识别、机器人学、信息检索和博弈等领域都广泛使用搜索技术。

人工智能问题，广义地说都可以看作是一个问题求解过程，因此问题求解是人工智能的核心问题，通常是通过在某个可能的解答空间中寻找一个解来进行的。

在问题求解过程中，人们所面临的大多数显示问题往往没有确定性的算法，通常需要用搜索算法来解决。

目标和达到目标的一组方法称为问题，搜索就是探究这些方法能够做什么的过程。

问题求解一般需要考虑两个基本问题：首先是使用合适的状态空间表示问题，其次是测试该状态空间中目标状态是否出现。

一般搜索可以根据是否使用启发式信息分为盲目搜索和启发式搜索。

一：盲目搜索盲目搜索又叫非启发式搜索，是一种无信息搜索，一般只使用求解比较简单的问题。

宽度优先搜索、深度优先搜索、分支有限搜索、迭代加深搜索都是盲目搜索。

1.宽度优先搜索宽度优先搜索算法（又称广度优先搜索算法）是最简单的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。

Dijksta单源最短路径算法和Prim 最小生成树算法都采用了与宽度优先搜索类似的思想。

宽度优先搜索的核心思想是：从初始结点开始，应用算符生成第一层结点，检查目标结点是否在这些后继结点中，若没有，再用产生式规则将所有第一层的结点逐一扩展，得到第二层结点，并逐一检查第二层结点中是否包含目标结点。

一、实训背景随着互联网的普及和信息技术的发展，搜索引擎已成为人们获取信息的重要工具。

然而，在信息爆炸的时代，如何在海量信息中快速、准确地找到所需信息，成为了一个亟待解决的问题。

为了提高信息检索的效率，我们开展了盲目搜索实训，通过模拟实际搜索过程，探索有效的搜索策略。

二、实训目的1. 熟悉搜索引擎的基本操作和功能；2. 掌握信息检索的基本原则和技巧；3. 提高在海量信息中快速、准确地找到所需信息的能力；4. 培养批判性思维和信息素养。

三、实训内容1. 搜索引擎的选择与使用实训过程中，我们选择了百度、谷歌、搜狗等国内外主流搜索引擎进行实践。

通过对比分析，我们发现百度在中国市场占有率较高，且具有强大的中文搜索能力；谷歌则在全球范围内具有较高的搜索精度；搜狗则具有独特的语音搜索功能。

在实际操作中，我们根据需求选择合适的搜索引擎，并熟悉其操作界面和功能。

2. 信息检索的基本原则（1）相关性：搜索结果应与用户需求具有较高的相关性，避免无关信息的干扰；（2）准确性：搜索结果应准确反映用户需求，避免误导；（3）全面性：搜索结果应涵盖用户需求的相关领域，避免遗漏；（4）时效性：搜索结果应关注最新动态，避免过时信息的影响。

3. 信息检索的技巧（1）关键词优化：选择合适的关键词，提高搜索精度；（2）逻辑运算符：使用逻辑运算符（如AND、OR、NOT）进行组合搜索，提高搜索效果；（3）高级搜索：利用搜索引擎的高级搜索功能，如筛选时间、网站类型等，提高搜索效果；（4）搜索结果分析：对搜索结果进行筛选、排序和去重，提高信息质量。

四、实训过程1. 阶段一：搜索实践在实训过程中，我们针对不同的主题进行搜索，如科技、教育、娱乐等。

通过实践，我们发现：（1）关键词优化对于提高搜索精度至关重要；（2）逻辑运算符在组合搜索中具有重要作用；（3）高级搜索功能可以帮助我们更精确地找到所需信息。

2. 阶段二：案例分析我们选取了几个具有代表性的案例进行分析，如“人工智能”、“区块链”等。

人工智能的搜索方式什么是搜索搜索是人工智能领域的一个重要问题。

它类似于传统计算机程序中的查找，但远比查找复杂得多。

传统程序一般解决的问题都是结构化的，结构良好的问题算法简单而容易实现。

但人工智能所要解决的问题绝大部分是非结构化或结构不良的问题，对这样的问题很难找到成熟的求解算法，而只能是一步步地摸索前进。

就像是甲、乙两个不同的网络，甲网络中的某一台计算机A要想找到乙网络中的数据。

乙网络位于广域网中，A的目标就是要找到乙网络（实际上就是找到甲主路由器的IP），但是A不知道目标的具体位置，只能试探着去找。

像这样摸索着前进，持续搜索前进方向的过程称为搜索。

从理论上讲，只要乙不犯规(不会关闭设备)，A终究是会找到乙的（当然这必须是在甲、乙本来是能够互通的基础上）。

当然，A找到乙所需的时间是无法预测的。

如果A以前就访问过乙网络上的某台主机，在找的过程中，能够得到路由器中更新的路由表的支持，很快会找对了方向，可能花费的时间就会少些。

相反，也有可能A找遍了所有的地方，最后才找到乙(极端情况)。

搜索，通常可分为盲目搜索和启发式搜索。

盲目搜索是按预定的控制策略实行，在搜索过程中获得的中间信息不用来改进控制策略。

这在复杂网络中的路由选择会经常用到。

广域网中的动态路由协议，为了学习相邻路由器的路由，为了确定最短路径，总是主动地去搜索相邻的路由设备。

因为路由选择总是按预先规定的方式实行，未能考虑到环形结构或不可到达情况，所以效率不高，具有盲目性，往往会所以占去很多的网络带宽。

启发式搜索是在搜索过程中根据问题的特点，加入一些具有启发性的信息，如从上一级路由器中找到相对应的路由表来确定下一步搜索的路线，加速问题的求解过程。

显然，启发式搜索的效率比盲目搜索要高，但因为启发式搜索需要与网络本身特性相关的信息，而这对非常复杂的网络是比较困难的，所以盲目搜索在当前的应用中仍然占据着统治地位。

而盲目搜索中最行之有效、应用最广泛的搜索策略就是：宽度优先搜索和深度优先搜索。

1．什么是智能？智能有什么特征？答：智能可以理解为知识与智力的总和。

其中，知识是一切智能行为的基础，而智力是获取知识并运用知识求解问题的能力，即在任意给定的环境和目标的条件下，正确制订决策和实现目标的能力，它来自于人脑的思维活动。

智能具有下述特征：（1）具有感知能力（系统输入）。

（2）具有记忆与思维的能力。

（3）具有学习及自适应能力。

（4）具有行为能力（系统输出）。

2．人工智能有哪些学派？他们各自核心的观点有哪些？答：根据研究的理论、方法及侧重点的不同，目前人工智能主要有符号主义、联结主义和行为主义三个学派。

符号主义认为知识可用逻辑符号表达，认知过程是符号运算过程。

人和计算机都是物理符号系统，且可以用计算机的符号来模拟人的认知过程。

他们认为人工智能的核心问题是知识表示和知识推理，都可用符号来实现，所有认知活动都基于一个统一的体系结构。

联结主义原理主要是神经网络及神经网络间的连接机制与学习算法。

他们认为人的思维基元是神经元，而不是符号运算。

认为人脑不同于电脑，不能用符号运算来模拟大脑的工作模式。

行为主义原理为控制论及“感知—动作”型控制系统。

该学派认为智能取决于感知和行动，提出智能行为的“感知—动作”模式，他们认为知识不需要表示，不需要推理。

智能研究采用一种可增长的方式，它依赖于通过感知和行动来与外部世界联系和作用。

3．人工智能研究的近期目标和远期目标是什么？它们之间有什么样的关系？答：人工智能的近期目标是实现机器智能，即主要研究如何使现有的计算机更聪明，使它能够运用知识去处理问题，能够模拟人类的智能行为。

人工智能的远期目标是要制造智能机器。

即揭示人类智能的根本机理，用智能机器去模拟、延伸和扩展人类的智能。

人工智能的近期目标与远期目标之间并无严格的界限，二者相辅相成。

远期目标为近期目标指明了方向，近期目标则为远期目标奠定了理论和技术基础。

4．人工智能的研究途径有哪些？答：人工智能的研究途径主要有：（１）心理模拟，符号推演；（２）生理模拟，神经计算；（３）行为模拟，控制进化论。

启发式搜索A和A*搜索算法首先什么是启发式搜索？启发式搜索就是利用当前问题有关的信息作为启发式信息，这些信息是能够提升查找效率、减少搜索时间和减少查询次数的。

为了利用这些信息，我们定义了一个估价函数h(x)，h(x)是对当前状态x的一个估计，它表示x状态到目标点的距离。

那么由它表示的意义我们可以知道，当h(x)等于0时，说明到达了目标点。

一、A和A*搜搜算法介绍A搜索算法就是使用了估价函数的搜索算法，估价函数的一般形式是f(x)=g(x)+h(x)。

其任务就是估计待搜索有希望程度，赢一次给它们排定次序。

其中g(x)代表从初始结点到x结点的实际代价，h(x)是从当前结点到目标结点的代价，这个代价是估计出来的。

A*搜索算法是估价函数满足一定条件的算法，其限制条件是f(x)=g(x)+h(x)，代价函数g(x)大于0，h(x)的值不大于x到目标结点的实际代价h*(x)。

二、A和A*搜索算法运用搜索算法如下：①将初始节点S0放入Open表中。

②如Open表为空，则搜索失败，退出。

③把Open表的第一个节点取出，放入到Closed表中，并把该节点记为节点n。

④如果节点n是目标节点，则搜索成功，求得一个解，退出。

⑤扩展节点n，生成一组子节点，对既不在Open表中也不在Closed表中的子节点，计算出相应的估价函数值。

⑥把节点n的子节点放到Open表中。

⑦对Open表中的各节点按估价函数值从小到大排列；。

⑧转到②。

启发式通常用于资讯充份的搜寻算法，例如最好优先贪婪算法与A*。

最好优先贪婪算法会为启发式函数选择最低代价的节点；A*则会为g(n) + h(n)选择最低代价的节点，此g(n)是从起始节点到目前节点的路径的确实代价。

如果h(n)是可接受的（admissible）意即h(n)未曾付出超过达到目标的代价，则A*一定会找出最佳解。

最能感受到启发式算法好处的经典问题是n-puzzle。

此问题在计算错误的拼图图形，与计算任两块拼图的曼哈顿距离的总和以及它距离目的有多远时，使用了本算法。

人工智能的搜索方式什么是搜索搜索是人工智能领域的一个重要问题。

它类似于传统计算机程序中的查找，但远比查找复杂得多。

传统程序一般解决的问题都是结构化的，结构良好的问题算法简单而容易实现。

但人工智能所要解决的问题大部分是非结构化或结构不良的问题，对这样的问题很难找到成熟的求解算法，而只能是一步步地摸索前进。

就像是甲、乙两个不同的网络，甲网络中的某一台计算机A要想找到乙网络中的数据。

乙网络位于广域网中，A的目标就是要找到乙网络（实际上就是找到甲主路由器的IP），但是A不知道目标的具体位置，只能试探着去找。

像这样摸索着前进，不断搜索前进方向的过程称为搜索。

从理论上讲，只要乙不犯规(不会关闭设备)，A终究是会找到乙的（当然这必须是在甲、乙本来是可以互通的基础上）。

当然，A找到乙所需的时间是无法预测的。

如果A以前就访问过乙网络上的某台主机，在找的过程中，可以得到路由器中更新的路由表的支持，很快会找对了方向，可能花费的时间就会少些。

相反，也有可能A找遍了所有的地方，最后才找到乙(极端情况)。

搜索，通常可分为盲目搜索和启发式搜索。

盲目搜索是按预定的控制策略进行，在搜索过程中获得的中间信息不用来改进控制策略。

这在复杂网络中的路由选择会经常用到。

广域网中的动态路由协议，为了学习相邻路由器的路由，为了确定最短路径，总是主动地去搜索相邻的路由设备。

由于路由选择总是按预先规定的方式进行，未能考虑到环形结构或不可到达情况，因此效率不高，具有盲目性，往往会因此占去不少的网络带宽。

启发式搜索是在搜索过程中根据问题的特点，加入一些具有启发性的信息，如从上一级路由器中找到相应的路由表来确定下一步搜索的路线，加速问题的求解过程。

显然，启发式搜索的效率比盲目搜索要高，但由于启发式搜索需要与网络本身特性有关的信息，而这对非常复杂的网络是比较困难的，因此盲目搜索在目前的应用中仍然占据着统治地位。

而盲目搜索中最行之有效、应用最广泛的搜索策略就是：宽度优先搜索和深度优先搜索。