启发式搜索策略

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

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

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

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

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

浅谈人工智能中的启发式搜索策略
一、启发式策略
启发式策略是指在解决复杂问题时，根据人的经验和技巧来寻求最优解的方法。

它是人工智能领域中的一种和规划技术，可以解决形式化的各种问题。

启发式策略广泛应用于机器学习、图形图计算、机器人控制和计算机图形学等多种领域。

启发式策略包括：A*算法、B*树算法、启发式和动态规划等。

A*算法是一种非常有效的启发式方法，它采用了一个启发函数来估计待访问节点的最优价值，从而可以根据最小价值节点而进行，的效果比较好。

B*树算法是一种静态的启发式方法，该算法在每一步都可以通过比较不同节点价值来确定最优路径，从而更有效地出最优路径。

启发式和动态规划都是一种在状态空间中采取其中一种方法或策略以获得最优解的技术，两者最大的不同点在于，启发式依赖于当前状态，动态规划则更倾向于最终目标。

二、应用
启发式策略广泛应用于人工智能领域，它可以用来解决各种形式化问题，如游戏、自然语言处理问题等。

结合穷举法与启发式算法：确定搜索方向的策略与方
法
在穷举法与启发式算法结合时，确定搜索方向是非常重要的。

启发式算法通常基于一些经验或启发式的规则，用于引导搜索过程。

以下是一些常用的确定搜索方向的策略：
1.利用已知最优解：如果已知某问题的最优解，那么可以将其作为搜索的起
点或搜索过程中的一个重要节点。

这样可以大大缩小搜索范围，提高搜索效率。

2.使用启发式函数：启发式函数是一种评估解的质量的函数，可以根据问题
的性质和经验来设计。

在搜索过程中，可以按照启发式函数的值对解进行排序或选择，优先搜索质量较高的解。

3.优先搜索未探索的区域：在搜索过程中，可以优先探索尚未探索过的区域，
或者优先探索解空间中估值较低的区域。

这样可以增加搜索的多样性，提高找到最优解的概率。

4.基于规则的剪枝：根据问题的性质和规则，可以在搜索过程中提前排除一
些不可能的解，减少搜索的范围和深度。

这样可以提高搜索效率，加速求解过程。

5.使用记忆化搜索：记忆化搜索是一种将已经计算过的解存储起来，避免重
复计算的策略。

在搜索过程中，可以不断更新存储的解，并在搜索过程中优先选择已经计算过的解，从而提高搜索效率。

综上所述，确定搜索方向时可以考虑利用已知最优解、使用启发式函数、优先搜索未探索的区域、基于规则的剪枝和使用记忆化搜索等方法。

这些策略可以根据问题的性质和实际情况进行选择和调整，以提高穷举法与启发式算法结合时的性能和效率。

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

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

列举问题解决策略中的启发式策略
1. 模拟退火算法：从初始状态出发，按照一定的规律和机制不断的改变初始状态来改善目标函数的值。

2. 模拟逐渐升温算法：以一定的步长值慢慢加温，增加搜索步数，加快收敛速度，并避免陷入局部极小点。

3. 局部搜索算法：选用一个启发式规则探索当前最优解附近的点，根据不同启发式规则有不同类型，如下溯算法，模拟退火算法，择优算法等。

4. 爬山法：通过比较每一步解的目标值，选择最佳的进入下一步的解，当发现当前解不能提高最终目标值时停止搜索，从而获取最优解。

问题解决的策略问题解决策略包括算法和启发式策略。

首先来看一下概念：(一)算法式策略算法策略就是把所有能解决问题的方法都一一尝试，最终找到解决问题的策略。

(二)启发式策略启发式策略是利用已有的知识和经验，只在问题空间做少量搜索就能解决问题的策略。

它还包括1.手段-目的分析将问题目标状态分成若干个子目标，通过实现一系列子目标，最终达到总目标。

例如：河内塔问题、问题行为图。

2.逆向搜索从问题的目标状态开始搜索，直到找到到初始状态的路径或方法。

例如：几何问题的反证法。

3.爬山法采用一定的方法逐渐缩小初始状态与目标状态之间的距离，以达到解决问题的目的。

这种方法的缺点是容易把较好的方案当成最优方案。

例如：确定新药的药剂量问题。

4.选择性搜索选择性搜索是根据已知的信息和一些相关的规则来选择问题解决的切入点，从切入点获取更多的信息，以便进一步搜索，直到问题解决。

选择性搜索是一种非常有效的解题策略，因为它是一种从已知条件中更接近问题答案的方法，从而消除了大量的盲目尝试。

例如：根据所给条件解决问题。

5.类比-迁移策略类比迁移策略是指运用个体以往解决问题的经验来解决新问题的策略。

这是解决不熟悉问题的策略。

类比迁移策略中有两种事务:基本相似性和目标相似性。

这种方法的缺点是可能会受到固定情境的影响，导致反复尝试解决问题。

例如：把解决“将军问题”的方法用到解决“肿瘤问题上”。

注意：同学们应该注意区分爬山法和手段—目的分析，后者可以暂时远离、扩大目标与初始状态之间的差异，而爬山法则不行。

关于启发式记忆口诀：“守墓逆向爬山选搜雷倩”。

启发式搜索策略讲稿1.引入启发式搜索策略的定义。

通过前面的学习，我们了解可以采用前面的一些搜索策略来解决梵塔问题，当它的阶数较小（如小于6）时，在计算机上求解并不难，但当阶数再增加时，其时空要求将会急剧的增加。

对于那些大状态空间问题，这些搜索策略就不能胜任了。

又如博弈问题，就可能的棋局数讲，国际象棋是10^120，假设每步可以选择一种棋局，用极限并行速度计算，国际象棋的算法也得1亿亿年才可以算完。

因此，为了寻找更有效的搜索方法，人们提出了启发式搜索策略。

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

此种信息叫做启发信息。

利用启发信息的搜索方法叫做启发式搜索方法。

其基本思想是：在搜索路径的控制信息中增加关于被解问题的某些特征，用以指导搜索朝着最有希望到达目标节点的方向前进。

2.启发式搜索策略的主要特点。

由于充分考虑到问题求解所应用到的各种启发信息及知识，包括利用常识性推理和专家经验等信息与知识，启发式搜索能够动态地确定操作排序，优先调用较合适的操作规则，扩展、比较并选择最有希望的节点，使搜索尽可能以最快的速度，最短的距离、最小的代价，朝着最有利于达到目标节点的方向推进。

3.估价函数和启发函数。

估价函数：搜索特性的一种数学表示，是指从问题树根节点到达目标节点所要耗费全部代价的一种估计值。

f（n）=g（n）+h（n）启发函数：在表达式f（n）=g（n）+h（n）中，g（n）部分是已确立的搜索路径基础上已耗费的代价，其轨迹和效率是无法再更改的；唯有h(n)才是可以积极争取按照希望方向来改变的部分，是可以更新的内容。

h（n）4.局部择优搜索和全部择优搜索。

局部择优搜索：它是一种启发式搜索方法，是对深度优先搜索方法的一种改进。

全局择优搜索：按这种方法搜索时，每次总是从OPEN表中的全体节点中选择一个估价值最小的节点。

5.讲解例题：用全局择优搜索解决8数码问题。

f(x)=d(x)+h(x)其中，d(x)表示节点x的深度h(x)表示节点x的格局与目标节点格局不相同的牌数6.回顾内容，课程小结。