1.概述

在这篇简短的教程中,我们将介绍启发式函数的定义、其优缺点以及一些著名的示例。

2.启发式函数

2.1。定义

启发式函数(算法)或简单的启发式是在没有精确解或获得解的时间太长时解决问题的捷径。

2.2。速度和准确性

从定义中,我们可以得出结论,目标是找到一个更快的解或近似的解,即使它不是最优的。换句话说,当使用启发式方法时,我们用准确度来换取求解的速度。

例如,贪心算法通常产生快速但次优的解决方案。在下面这棵树中寻找最大和的贪心算法会选择红色路径,而最优路径是绿色路径:

2.3。容许启发式

启发式并不总是导致更低的成本。然而,那些没有高估解决方案的真实或可能的最低成本的方法被称为可采启发式。这一特性可以保证解决方案的最优性。通过对原问题的约束条件进行简化,将原问题简化为约束较少的问题,可以找到一个可容许启发式。让我们以8个谜题为例:

我们从左边的状态开始,我们想达到右边的目标状态。作为这个谜题的启发式解决方案,我们可以考虑汉明距离这两个状态之间,就是用绿色突出显示的错位瓷砖的数量。在这里,我们放松了这个问题的限制,假设我们可以拿起一个瓦片,把它放到正确的位置。

由于最优解的步数不能少于这个解,因此这个解是允许的(即它是一个下界)。

3.启发式的例子

有许多问题我们可以提出一个启发式算法来解决。

让我们来讨论其中三个著名的。

3.1。^ *搜索

^ *寻路算法使用启发式查找图中的最短路径。每个节点n是有成本的f (n)计算方法是F (n) = g(n) + h(n)。在这个公式,g (n)实际的开销是从节点的路径开始的,以及h (n)是它达到目标的启发式成本。^ *是可接受的,意味着它总是找到最优的解决方案f (n)

3.2。旅行商问题

给出一个城市列表,在茶匙,我们希望找到访问每个城市一次并返回起始城市的最短路线。这被称为NP-hard问题,这意味着很难找到最优解。所以,我们用一个贪心算法它可能不会给出最短路径但至少能给出一个快速的答案。

贪心算法可以被认为是一种启发式算法,因为尽管它是次最优解,但它工作得相当好。

3.3。网格地图上的距离

在网格地图上搜索路径时,可以考虑几种距离函数作为启发式,这取决于移动方向的约束条件。然后在^ *求最短路径的算法。在下面的图片,我们想要从橙色方块到紫色方块,而有颜色的方块就是搜索空间。如果有任何可能的方向,我们可以使用欧氏距离:

在只有四个方向允许的情况下曼哈顿距离是一个合适的:

4.结论

在本文中,我们学习了启发式函数、它的优点和缺陷,以及一些金宝搏官网188be可以使用启发式函数的示例。

客人
0评论
内联反馈
查看所有评论