盲目搜索启发式搜索讲解学习

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

启发式搜索启发式搜索1. 相关概念在宽度优先和深度优先搜索⾥⾯，我们都是根据搜索的顺序依次进⾏搜索，可以称为盲⽬搜索，搜索效率⾮常低。

⽽启发式搜索则⼤⼤提⾼了搜索效率，由这两张图可以看出它们的差别：什么是启发式搜索（heuristic search）⽤当前与问题有关的信息作为启发式信息，这些信息是能够提升查找效率以及减少查找次数的。

我们定义了⼀个估价函数h(x)。

h(x)是对当前状态x的⼀个估计，表⽰x状态到⽬标状态的距离。

1. h(x) >= 0；2. h(x)越⼩表⽰x越接近⽬标状态；3. 如果h(x) ==0，说明达到⽬标状态。

有了启发式信息还不⾏，还需要起始状态到x状态所花的代价，我们称为g(x)。

g(x)就是我们实际要求解的问题。

⽐如在⾛迷宫问题、⼋数码问题，我们的g(x)就是从起点到 x位置花的步数，h(x)就是与⽬标状态的曼哈顿距离或者相差的数⽬；在最短路径中，我们的g(x)就是起点到x点的最短距离，h(x)就是x点到⽬标结点的最短路或直线距离。

令F(x)=g(x)+h(x)，作为我们的搜索依据。

当F(x) = g(x)的时候就是⼀个等代价搜索，完全是按照花了多少代价去搜索。

⽐如bfs，我们每次都是从离得近的层开始搜索，⼀层⼀层搜；以及dijkstra算法，也是依据每条边的代价开始选择搜索⽅向。

当F(x) = h(x)的时候就相当于⼀个贪婪优先搜索。

每次都是向最靠近⽬标的状态靠近。

⼈们发现，等代价搜索虽然具有完备性，能找到最优解，但是效率太低。

贪婪优先搜索不具有完备性，不⼀定能找到解，最坏的情况下类似于dfs。

这时候，有⼈提出了A算法。

令F(x) = g(x) + h(x)。

（这⾥的h(x)没有限制）。

虽然提⾼了算法效率，但是不能保证找到最优解，不适合的h(x)定义会导致算法找不到解。

不具有完备性和最优性。

⼏年后有⼈提出了A*算法。

该算法仅仅对A算法进⾏了⼩⼩的修改。

并证明了当估价函数满⾜⼀定条件，算法⼀定能找到最优解。

启发式搜索算法心得体会启发式搜索算法是一种通过推测来指导搜索方向的方法，它根据问题的特点和先前的知识进行启发式的搜索，以找到问题的最优解。

在实际应用中，启发式搜索算法被广泛应用于解决各种问题，如求解迷宫、规划路径等。

通过学习和理解启发式搜索算法，我获得了以下几点体会。

首先，启发式搜索算法的核心是启发函数的设计。

启发函数用于评估搜索节点的优劣，以决定搜索的方向。

好的启发函数能够明确指导搜索过程，减少不必要的搜索节点，提高搜索的效率。

在设计启发函数时，我们需要考虑问题的特点和约束条件，合理选择启发函数的评估指标，并通过启发函数的计算方法来优化搜索过程。

其次，启发式搜索算法在问题求解中的表现受到启发函数的影响。

不同的启发函数会导致不同的搜索策略和结果。

因此，在实际应用中，我们需要根据问题的不同特点和求解要求，设计适合的启发函数。

例如，在解决迷宫问题时，可以根据迷宫的布局和目标位置，设计一种启发函数来估计当前节点到目标的距离，以此指导搜索前进的方向。

再次，启发式搜索算法是一种权衡准确性和效率的方法。

通常情况下，启发式搜索算法能够在较短的时间内找到较优解，但并不能保证找到问题的最优解。

这是因为启发式搜索算法通过启发函数进行估计，存在一定的不确定性。

因此，在实际应用中，我们需要根据问题的实际需求，平衡准确性和效率的关系，选择适合的搜索算法和启发函数。

最后，启发式搜索算法是一个不断迭代的过程。

通过不断优化启发函数和搜索策略，我们可以不断改进算法的性能和效果。

在实际应用中，我们可以通过实验和反馈来不断改进启发函数和搜索策略，以逐步提高算法的性能和效果。

此外，启发式搜索算法也可以与其他算法结合使用，形成更加强大和高效的问题求解方法。

总之，通过学习和理解启发式搜索算法，我认识到它在问题求解中的重要性和广泛应用。

通过合理设计启发函数，我们能够明确指导搜索过程，提高搜索效率。

然而，启发式搜索算法也存在一定的局限性，需要在准确性和效率之间进行权衡。