启发式的具体例子
启发式的具体示例是什么（例如 Alpha-beta 剪枝，示例：井字游戏以及它如何应用于那里）。我已经看到一个关于什么是启发式的已回答问题，但我仍然不明白它使用估计的地方。您能给我一个启发式的具体例子及其工作原理吗？
What are concrete examples (e.g. Alpha-beta pruning, example:tic-tac-toe and how is it applicable there) of heuristics. I already saw an answered question about what heuristics is but I still don't get the thing where it uses estimation. Can you give me a concrete example of a heuristic and how it works?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
Warnsdorff 规则 是一种启发式规则，但
A*搜索算法不是。顾名思义，它是一种不依赖于问题的搜索算法。启发式是。举个例子：您可以使用A*（如果正确实现）来解决十五个难题并找到走出迷宫的最短路线，但所使用的启发式方法会有所不同。对于十五个谜题，您的启发式可能是有多少块不合适：解决谜题所需的移动次数将始终大于或等于启发式。要走出迷宫，您可以使用到您知道在迷宫之外的点的曼哈顿距离作为启发法。曼哈顿距离广泛用于类似游戏的问题，因为它是到达目标所需的水平和垂直“步数”。
很容易看出，在最好的情况下（没有墙壁），这将是到目标的精确距离，在其余情况下，您将需要更多距离。这很重要：您的启发式必须乐观（可接受启发式），以便您的搜索算法达到最佳。它还必须一致。然而，在某些应用程序（例如具有非常大地图的游戏）中，您使用不可接受的启发式方法，因为次优解决方案就足够了。
启发式只是实际成本的近似值（如果允许的话，总是低于实际成本）。近似值越好，搜索算法必须探索的状态就越少。但更好的近似通常意味着更多的计算时间，因此您必须找到折衷的解决方案。
Warnsdorff's rule is an heuristic, but the
A*search algorithm isn't. It is, as its name implies, a search algorithm, which is not problem-dependent. The heuristic is. An example: you can use theA*(if correctly implemented) to solve the Fifteen puzzle and to find the shortest way out of a maze, but the heuristics used will be different. With the Fifteen puzzle your heuristic could be how many tiles are out of place: the number of moves needed to solve the puzzle will always be greater or equal to the heuristic.To get out of the maze you could use the Manhattan Distance to a point you know is outside of the maze as your heuristic. Manhattan Distance is widely used in game-like problems as it is the number of "steps" in horizontal and in vertical needed to get to the goal.
It's easy to see that in the best case (there are no walls) that will be the exact distance to the goal, in the rest you will need more. This is important: your heuristic must be optimistic (admissible heuristic) so that your search algorithm is optimal. It must also be consistent. However, in some applications (such as games with very big maps) you use non-admissible heuristics because a suboptimal solution suffices.
A heuristic is just an approximation to the real cost, (always lower than the real cost if admissible). The better the approximation, the fewer states the search algorithm will have to explore. But better approximations usually mean more computing time, so you have to find a compromise solution.
最具有代表性的是在知情搜索算法中使用启发式算法，例如 A-Star。对于现实问题，您通常有很大的搜索空间，因此不可能检查它的每个部分。为了避免这种情况，即首先尝试搜索空间中最有希望的部分，您可以使用启发式方法。启发式方法可以让您估计可用的后续搜索步骤的效果。您将选择最有希望的下一步，即最佳优先。例如，如果您想搜索两个城市之间的路径（即顶点，由一组道路（即边，形成图形连接）连接），您可能需要选择到目标的直线距离作为启发式确定首先访问哪个城市（并查看它是否是目标城市）。
启发式方法应该具有与搜索空间的指标类似的属性，并且通常应该是乐观，但那是另一回事了。提供一种有效且无副作用的启发式方法的问题是另一个问题...
对于用于查找通过给定迷宫的路径的不同启发式方法的应用，还可以查看 这个答案。
Most demonstrative is the usage of heuristics in informed search algorithms, such as A-Star. For realistic problems you usually have large search space, making it infeasible to check every single part of it. To avoid this, i.e. to try the most promising parts of the search space first, you use a heuristic. A heuristic gives you an estimate of how good the available subsequent search steps are. You will choose the most promising next step, i.e. best-first. For example if you'd like to search the path between two cities (i.e. vertices, connected by a set of roads, i.e. edges, that form a graph) you may want to choose the straight-line distance to the goal as a heuristic to determine which city to visit first (and see if it's the target city).
Heuristics should have similar properties as metrics for the search space and they usually should be optimistic, but that's another story. The problem of providing a heuristic that works out to be effective and that is side-effect free is yet another problem...
For an application of different heuristics being used to find the path through a given maze also have a look at this answer.
你的问题让我感兴趣，因为我在学习期间也听说过启发式，但从未见过它的应用程序，我用谷歌搜索了一下，发现了这个：http://www.predictia.es/blog/aco-search
此代码模拟“蚁群优化”算法来通过网站进行搜索。
“蚂蚁”是在站点中进行搜索的工人，有些会随机搜索，有些会遵循先前确定的“最佳路径”。
Your question interests me as I've heard about heuristics too during my studies but never saw an application for it, I googled a bit and found this : http://www.predictia.es/blog/aco-search
This code simulate an "ant colony optimization" algorithm to search trough a website.
The "ants" are workers which will search through the site, some will search randomly, some others will follow the "best path" determined by the previous ones.
一个具体的例子：我一直在为游戏JT's Block做一个求解器，它是大致相当于同一游戏。该算法对所有可能的命中执行广度优先搜索，存储值，然后执行下一层。问题是可能的命中数量很快就会失去控制（每场比赛估计有 10e30 个位置），所以我需要在每个回合修剪位置列表，只选择其中的“最佳”位置。
现在，“最佳”位置的定义相当模糊：它们是预计会获得最佳最终分数的位置，但没有什么是确定的。启发法来了。我已经尝试了其中的一些：
最后一个启发式可能会导致蚂蚁行军优化：有六个参数可以从 0 调整到 1，优化器可以找到最佳组合这些。目前我只是手动改进了其中一些。
这种启发式的第二个很有趣：它可以通过完整的深度优先搜索获得最佳分数，但这样的目标当然是不可能的，因为它会花费太多时间。一般来说，增加 X 会带来更好的启发式，但会大量增加计算时间。
这就是一些启发式的例子。任何东西都可以是启发式的，只要它可以帮助你的算法更好地执行，这就是它们如此难以掌握的原因：它们不是确定性的。启发式的另一点是：它们应该会导致真实结果的快速而肮脏的结果，因此在它们的执行时间和准确性之间需要进行权衡。
A concrete example: I've been doing a solver for the game JT's Block, which is roughly equivalent to the Same Game. The algorithm performs a breadth-first search on all possible hits, store the values, and performs to the next ply. Problem is the number of possible hits quickly grows out of control (10e30 estimated positions per game), so I need to prune the list of positions at each turn and only take the "best" of them.
Now, the definition of the "best" positions is quite fuzzy: they are the positions that are expected to lead to the best final scores, but nothing is sure. And here comes the heuristics. I've tried a few of them:
The last of these heuristic could have lead to an ant-march optimization: there's half a dozen parameters that can be tweaked from 0 to 1, and an optimizer could find the optimal combination of these. For the moment I've just manually improved some of them.
The second of this heuristics is interesting: it could lead to the optimal score through a full depth-first search, but such a goal is impossible of course because it would take too much time. In general, increasing X leads to a better heuristic, but increases the computing time a lot.
So here it is, some examples of heuristics. Anything can be an heuristic as long as it helps your algorithm perform better, and it's what makes them so hard to grasp: they're not deterministic. Another point with heuristics: they're supposed to lead to quick and dirty results of the real stuff, so there's a trade-of between their execution time and their accuracy.
几个具体的例子：为了解决 Knight's Tour 问题，可以使用 Warnsdorff 的规则 - 启发式。或者为了解决十五个谜题，一个可能的启发式是A* 搜索算法。
A couple of concrete examples: for solving the Knight's Tour problem, one can use Warnsdorff's rule - an heuristic. Or for solving the Fifteen puzzle, a possible heuristic is the A* search algorithm.
最初的问题要求提供启发式的具体示例。
其中一些具体例子已经给出。另一个是 15 块拼图中错位瓷砖的数量或其改进，即基于错位瓷砖的曼哈顿距离。
之前的答案之一还声称启发式方法始终依赖于问题，而算法则与问题无关。当然，也存在与问题相关的算法（例如，对于每个问题，您都可以给出一个立即解决该问题的算法，例如，任何汉诺塔问题的最佳策略都是已知的），还有与问题无关的启发式！
因此，也存在不同类型的与问题无关的启发法。因此，在某种程度上，每个这样的启发式都可以被视为具体的启发式示例，而不是针对像 15 谜题这样的特定问题进行定制。 （从规划中获取的与问题无关的启发式示例是 FF 启发式或 Add 启发式。）
这些与问题无关的启发式基于通用描述语言，然后执行问题松弛。也就是说，问题松弛仅基于问题描述的语法（当然还有其底层语义），而不“知道”它代表什么。如果您对此感兴趣，您应该熟悉“规划”，更具体地说，熟悉“规划作为启发式搜索”。我还想提一下，这些启发式方法虽然与问题无关，但当然也依赖于问题描述语言。 （例如，我之前提到的启发法是特定于“规划问题”的，甚至对于规划来说，也有各种不同的子问题类别，具有不同类型的启发法。）
The original question asked for concrete examples for heuristics.
Some of these concrete examples were already given. Another one would be the number of misplaced tiles in the 15-puzzle or its improvement, the Manhattan distance, based on the misplaced tiles.
One of the previous answers also claimed that heuristics are always problem-dependent, whereas algorithms are problem-independent. While there are, of course, also problem-dependent algorithms (for instance, for every problem you can just give an algorithm that immediately solves that very problem, e.g. the optimal strategy for any tower-of-hanoi problem is known) there are also problem-independent heuristics!
Consequently, there are also different kinds of problem-independent heuristics. Thus, in a certain way, every such heuristic can be regarded a concrete heuristic example while not being tailored to a specific problem like 15-puzzle. (Examples for problem-independent heuristics taken from planning are the FF heuristic or the Add heuristic.)
These problem-independent heuristics base on a general description language and then they perform a problem relaxation. That is, the problem relaxation only bases on the syntax (and, of course, its underlying semantics) of the problem description without "knowing" what it represents. If you are interested in this, you should get familiar with "planning" and, more specifically, with "planning as heuristic search". I also want to mention that these heuristics, while being problem-independent, are dependent on the problem description language, of course. (E.g., my before-mentioned heuristics are specific to "planning problems" and even for planning there are various different sub problem classes with differing kinds of heuristics.)