3搜索问题-启发式搜索

启发式搜索启发式搜索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算法进⾏了⼩⼩的修改。

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

《人工智能》实验大作业实验题目：启发式搜索一、实验目的：熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A算法求解九宫问题，理解求解流程和搜索顺序。

二、实验方法：1.先熟悉启发式搜索算法；2.用C、C++或JA V A 语言编程实现实验内容。

三、实验背景知识：1.估价函数在对问题的状态空间进行搜索时，为提高搜索效率需要和被解问题的解有关的大量控制性知识作为搜索的辅助性策略。

这些控制信息反映在估价函数中。

估价函数的任务就是估计待搜索节点的重要程度，给这些节点排定次序。

估价函数可以是任意一种函数，如有的定义它是节点x处于最佳路径的概率上，或是x节点和目标节点之间的距离等等。

在此，我们把估价函数f(n)定义为从初始节点经过n节点到达目标节点的最小代价路径的代价估计值，它的一般形式是：f(n) = g(n) + h(n)其中g(n)是从初始节点到节点n的实际代价，g(n)可以根据生成的搜索树实际计算出来；h(n)是从n到目标节点的最佳路径的代价估计，h(n)主要体现了搜索的启发信息。

2. 启发式搜索过程的特性（1）可采纳性当一个搜索算法在最短路径存在的时候能保证能找到它，我们就称该算法是可采纳的。

所有A*算法都是可采纳的。

（2）单调性一个启发函数h是单调的，如果a）对所有的状态n i和n j，其中n j是n i的子孙，h(n i )- h(n j )≤cost(n i,n j ),其中cost(n i,n j )是从n i到n j 实际代价。

b）目标状态的启发函数值为0，即h(Goal)=0.具有单调性的启发式搜索算法在对状态进行扩展时能保证所有被扩展的状态的f值是单调递增（不减）。

（3）信息性比较两个启发策略h1和h2，如果对搜索空间中的任何一个状态n都有h1(n) ≤h2(n)，就说h2比h1具有更多的信息性。

一般而言，若搜索策略h2比h1有更多的信息性，则h2比h1考察的状态要少。

但必须注意的是更多信息性需要更多的计算时间，从而有可能抵消减少搜索空间所带来的益处。

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

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

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

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

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

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

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

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

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

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

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

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

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

人工智能技术报告启发式搜索产生背景：何谓启发式搜索算法在说它之前先提提状态空间搜索。

状态空间搜索，如果按专业点的说法就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。

通俗点说，两点之间求一线路，这两点是求解的开始和问题的结果，而这一线路不一定是直线，可以是曲折的。

由于求解问题的过程中分枝有很多，主要是求解过程中求解条件的不确定性，不完备性造成的，使得求解的路径很多这就构成了一个图，我们说这个图就是状态空间。

问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。

这个寻找的过程就是状态空间搜索。

常用的状态空间搜索有深度优先和广度优先。

广度优先是从初始状态一层一层向下找，直到找到目标为止。

深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。

这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。

前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。

这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。

他的效率实在太低，甚至不可完成。

在这里就要用到启发式搜索了。

定义：启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。

这样可以省略大量无谓的搜索路径，可以有不同的效果。

我们先看看估价是如何表示的。

启发中的估价是用估价函数表示的，如：f(n) = g(n) + h(n)其中f(n) 是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是当h(n) >> g(n)时，可以省略g(n)，而提高效率。

这些就深了。

算法举例启发算法有：蚁群算法，遗传算法、模拟退火算法等蚁群算法是一种来自大自然的随机搜索寻优方法，是生物界的群体启发式行为，现己陆续应用到组合优化、人工智能、通讯等多个领域。

蚁群算法的正反馈性和协同性使其可用于分布式系统，隐含的并行性更使之具有极强的发展潜力。