logo标签列表

启发式算法的具体例子

algorithmartificial-intelligenceheuristics
6

什么是启发式算法的具体示例（例如Alpha-beta剪枝，例如：井字游戏），以及它们在其中的应用。我已经看到了一个关于启发式算法的解释，但我还是不明白它是如何使用估计值的。你能否给我一个具体的启发式算法示例并说明其工作原理?

你自己有什么想法吗？你觉得呢？ - moooeeeep
我想了解估算是如何准确运作的。由于我计划在人工智能领域选择论文主题，因此我经常看到启发式这个术语。我尝试进行研究，但无济于事，我仍然找不到好的来源来给我提供它的使用示例和工作原理。 - Odine
启发式算法意味着使用计算机模拟人类本能，以判断当前解决方案/状态的优良程度... - phoeagon
@phoeagon 实际上不是。 - xoxox
6个回答
4
最具有代表性的是在启发式搜索算法（如A-Star）中使用启发式。对于现实问题，通常存在大量的搜索空间，使得检查每个部分都变得不可行。为了避免这种情况，即首先尝试搜索空间中最有希望的部分，您可以使用启发式。启发式为您提供了可用后续搜索步骤的好坏估计。您将选择最有前途的下一步，即最佳优先。例如，如果您想搜索两个城市之间的路径（即由道路组成的边缘连接的顶点形成的图），您可能希望选择到目标城市的直线距离作为启发式来确定先访问哪个城市（并查看它是否是目标城市）。
启发式应该具有与搜索空间相关的类似度量的属性，通常应该是乐观的，但这是另一个故事。提供有效且无副作用的启发式的问题是另一个问题...

如果您想了解关于使用不同的启发式算法来寻找给定迷宫路径的应用，也可以查看this answer。

4

Warnsdorff's rule是一种启发式算法，但A*搜索算法不是。正如其名称所示，它是一种搜索算法，不依赖于问题本身。而启发式算法则依赖于具体问题。例如：您可以使用A*（如果正确实现）来解决十五数码难题和找到迷宫的最短路径，但使用的启发式将是不同的。对于十五数码难题，您的启发式可能是有多少个方块没有在正确位置上：解决难题所需的移动次数始终大于或等于启发式。

要走出迷宫，您可以使用曼哈顿距离到您知道在迷宫外的某个点作为启发式。曼哈顿距离在类似游戏的问题中被广泛使用，因为它是水平和垂直方向上到达目标所需的“步数”。

Manhattan distance = abs(x2-x1) + abs(y2-y1)

在最好的情况下（没有墙壁），很容易看出那将是到目标的确切距离，在其他情况下，你需要更多。这很重要：你的启发式必须是乐观的（可采纳启发式），以便你的搜索算法是最优的。它还必须是一致的。然而，在某些应用程序中（例如具有非常大地图的游戏）使用非可采纳启发式，因为次优解已足够。

启发式只是实际成本的近似值（如果是可采纳的，则始终低于实际成本）。近似值越好，搜索算法要探索的状态就越少。但是更好的近似通常意味着更多的计算时间，因此你必须找到一个折衷的解决方案。

1

你的问题引起了我的兴趣，因为在我的学习过程中我也听说过启发式算法，但从未看到过它的应用。我进行了一些谷歌搜索，并找到了这个链接：http://www.predictia.es/blog/aco-search

这段代码模拟了一种“蚁群优化”算法来搜索网站。 “蚂蚁”是工人，他们将通过网站进行搜索，有些将随机搜索，而其他人将遵循先前确定的“最佳路径”。

1
一个具体的例子：我一直在为游戏JT's Block编写求解器，它大致相当于Same Game。该算法对所有可能的命中执行广度优先搜索，存储值，并执行到下一个棋层。问题是可能的命中数量很快就失控了（每个游戏估计有10e30个位置），因此我需要在每次轮换时修剪位置列表并仅选择其中的“最佳”位置。
现在，“最佳”位置的定义非常模糊：它们是预计会导致最佳最终得分的位置，但没有确切的保证。这就是启发式的作用。我尝试了一些启发式方法：
  • 按迄今为止获得的分数对位置进行排序
  • 通过x-depth搜索获得最佳分数来增加分数
  • 基于使用瓷砖数量、颜色和接近性的复杂公式增加分数
  • 通过调整其参数并查看其表现来改进最后一个启发式方法
  • 等等...

这些启发式中的最后一个可能会导致蚂蚁行进优化：有半打参数可以从0调整到1，优化器可以找到这些参数的最佳组合。目前我只是手动改进了其中一些。

这些启发式中的第二个很有趣：它可以通过完整的深度优先搜索实现最优分数，但当然这个目标是不可能的，因为这需要太多时间。一般来说，增加X会导致更好的启发式，但会大大增加计算时间。

所以，这就是启发式的一些例子。只要它能帮助你的算法表现更好，任何东西都可以成为启发式，而这也是使它们如此难以掌握的原因：它们不是确定性的。关于启发式的另一个问题是：它们应该提供快速和肮脏的结果，而真正的东西则需要在执行时间和准确性之间进行权衡。

启发式算法是否适用于类似纸牌这样有一定机会因素的不完美游戏？ - Odine
0

原始问题要求提供启发式算法的具体例子。

其中一些具体例子已经给出。另一个例子是15数码难题中错位方块的数量或其改进版曼哈顿距离，基于错位方块。

之前的回答中还声称启发式算法总是依赖于问题，而算法则是独立于问题的。当然，也有依赖于问题的算法（例如，对于每个问题，你都可以给出一个立即解决该问题的算法，例如任何汉诺塔问题的最优策略已知），但也有独立于问题的启发式算法！

因此，也有不同种类的独立于问题的启发式算法。因此，在某种程度上，每个这样的启发式算法都可以被视为具体的启发式算法示例，而不像15数码难题那样专门针对特定问题。（从规划中取出的独立于问题的启发式算法示例包括FF启发式或Add启发式。）

这些与问题无关的启发式方法基于通用描述语言，然后执行问题放松。也就是说，问题放松仅基于问题描述的语法（当然还有其底层语义），而不“知道”它代表什么。如果您对此感兴趣，应该熟悉“规划”，更具体地说是“启发式搜索规划”。我还想提到，尽管这些启发式方法是与问题无关的，但它们当然依赖于问题描述语言。（例如，我之前提到的启发式方法是针对“规划问题”的，即使对于规划，也有各种不同的子问题类别，具有不同类型的启发式方法。）

0
2
A*是一种使用启发式算法的算法，而不是启发式算法本身。 - seaotternerd
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接