盲目搜索启发式搜索

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

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

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

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

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中的节点，确定是否需要修改通向它们后继节点的指针。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

启发式搜索名词解释,每个小标题不低于500字《启发式搜索名词解释》一、定义启发式搜索（Heuristics Search）是一种在计算机科学中广泛使用的搜索算法，它允许计算机使用启发式（如得分函数、近似值或盲目的）信息，以优化给定的搜索空间。

它是有用的在离散搜索空间，如游戏，环境下，因为有效的方法来解决搜索空间。

许多计算机科学领域都使用启发式搜索，例如，机器人控制，分布式搜索，推荐系统和自动计算机解析。

启发式搜索的设计是以当前最佳的情况和最全面的视角结合。

它既可以用于解决困难的问题也可以用于找到最优化的解决方案。

在某些情况下，决策者可能不想等待精确解决方案，只需要有一个基本准确，能够接受的解决方案即可，此时启发式搜索就可以发挥作用。

二、启发式搜索算法启发式搜索算法是搜索过程中一解决问题的有效策略，需要考虑不同路径及其代价，以便在算法运行的过程中不断优化。

他使用的是启发式的提示，即使用一种外部的知识来完成任务，而不是系统地搜索认知空间。

例如搜索过程的启发式准则可以是最小代价原则，即树的深度少的路径比深的优先；最大价值原则，即从树深度里估计到达最终目标容易程度；优先发现原则，即对已知状态下可行解空间里最可靠的解进行搜索；以及回溯法，即回溯，把搜索树搜索过程中当前最优状态保存，以便在最后可以得到最量化的最优解。

三、应用启发式搜索在多个研究领域中有着广泛的应用，从规划和自然语言理解到视觉，启发式搜索已经是一种解决问题的标准技术。

例如，在人工智能领域，启发式搜索可以帮助人类更好地理解其自身有限的能力，并能够有效地利用现有的信息来为给定解决方案找到更佳的解决方案。

此外，启发式搜索也被用于物流优化、交通系统调整、医疗领域的数据分析、推荐系统等，是大数据背后运行的一种数据分析和优化技术。

总之，启发式搜索是一种非常有用的算法，其主要目的是通过搜索问题的空间以找到最优的解决方案，它被广泛用于搜索优化，数据分析，推荐系统等多个领域，不仅有助于在计算上更好地求解问题，也有助于提高最终解决方案的准确率。

启发式搜索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。

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

5.1 ．什么是搜索？有哪两大类不同的搜索方法？二者的区别是什么？根据实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的推理路线的过程，就称为搜索搜索一般分为盲目搜索和启发式搜索。

盲目搜索又称为无信息搜索，即在搜索过程中，只按预先规定的搜索控制策略进行搜索，而没有任何中间信息来改变这些控制策略。

由于这种搜索的控制策略都是预定的，不管什么问题都采用这样的控制策略，这就使得搜索带有盲目性，效率不高。

只适用于解决较简单问题。

启发式搜索又称有信息搜索，它是指在求解过程中，根据问题本身的特性或搜索过程中产生的一些信息来不断地改变或调整搜索的方向，使搜索朝着最有希望的方向前进，加速问题的求解，并找到最优解。

启发式搜索由于考虑到问题本身的特性并利用这些特性，从而使搜索求解的效率更高，更易于求解复杂问题5.2 什么是启发式搜索，什么是启发信息？启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。

为减小搜索范围而需要利用某些已知的，有关具体问题领域的特性信息。

5.3 请阐述状态空间的一般搜索过程。

OPEN表与CLOSED表的作用是什么？有何区别？1) 把初始节点S0 放入OPEN表，并建立只含S0的图，记为G2) 检查OPEN表是否为空，若为空则问题无解，退出3) 把OPEN表的第一个节点取出放入CLOSE表，记该节点为节点n4) 观察节点n 是否为目标节点，若是，则求得问题的解，退出5) 扩展节点n，生成一组子节点。

把其中不是节点n 先辈的那些子节点记作集合M，并把这些节点作为节点n 的子节点加入G中。

6) 针对M中子节点的不同情况，分别进行如下处理对于那些未曾在G 中出现过的M成员设置一个指向父节点( n)的指针，并把它放入OPEN 表对于那些先前已在G中出现过的M成员，确定是否要修改指向父节点的指针对于那些先前已在G中出现，并且已经扩展了的M成员，确定是否需要修改其后继结点指向父节点的指针7) 按某种搜索策略对OPEN表中的节点进行排序8) 转第2 步OPEN表：用于存放刚生成的节点CLOSE表：用于存放将要扩展或已扩展的节点区别：存放节点节点不同，open 表存放未扩展的节点，closed 表存放已经扩展的节点。