寻找 A* 算法的启发式方法有哪些好方法？
您有一张方形图块地图，您可以在其中向 8 个方向中的任意方向移动。假设你有一个名为 cost(tile1,tile2) 的函数，它告诉你从一个相邻图块移动到另一个图块的成本，你如何找到一个既可接受的启发式函数 h(y, goal)并一致？在给定此设置的情况下，寻找启发式方法的方法是否可以通用，或者它会根据成本函数而有所不同吗？
You have a map of square tiles where you can move in any of the 8 directions. Given that you have function called cost(tile1, tile2) which tells you the cost of moving from one adjacent tile to another, how do you find a heuristic function h(y, goal) that is both admissible and consistent? Can a method for finding the heuristic be generalized given this setting, or would it be vary differently depending on the cost function?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
Amit 的教程是我在 A* 上见过的最好的教程之一 （Amit 的页面） 。您应该在此页面上找到一些关于启发法的非常有用的提示。
这是关于您的问题的引用：
Amit's tutorial is one of the best I've seen on A* (Amit's page). You should find some very useful hint about heuristics on this page .
Here is the quote about your problem :
这取决于成本函数。
有一些常见的启发式方法，例如欧几里得距离（平面上两个图块之间的绝对距离）二维平面）和曼哈顿距离（绝对 x 和 y 增量之和）。但这些假设实际成本永远不会低于一定金额。如果您的智能体可以有效地沿对角线移动（即移动到对角线的成本小于 2），则可以排除曼哈顿距离。如果移动到相邻图块的成本小于该移动的绝对距离（例如，可能如果相邻图块从该图块“下坡”），则排除欧几里德距离。
编辑
无论您的成本函数如何，
h(t1, t2) = -∞中始终具有可接受且一致的启发式。这可不是一件好事。It depends on the cost function.
There are a couple of common heuristics, such as Euclidean distance (the absolute distance between two tiles on a 2d plane) and Manhattan distance (the sum of the absolute x and y deltas). But these assume that the actual cost is never less than a certain amount. Manhattan distance is ruled out if your agent can efficiently move diagonally (i.e. the cost of moving to a diagonal is less than 2). Euclidean distance is ruled out if the cost of moving to a neighbouring tile is less than the absolute distance of that move (e.g. maybe if the adjacent tile was "downhill" from this one).
Edit
Regardless of your cost function, you always have an admissable and consistent heuristic in
h(t1, t2) = -∞. It's just not a good one.是的，启发式在几个方面依赖于成本函数。首先，它必须是相同的单位。其次，您不可能拥有比启发式成本更低的通过实际节点的路径。
在现实世界中，用于道路网络导航等情况时，您的启发式可能是“汽车以 1.5 倍速度限制在直接路径上行驶的时间”。每个路段的成本将使用实际的限速，这将产生更高的成本。
那么，瓷砖之间的成本函数是多少？它是基于物理属性，还是在图表之外定义？
Yes, the heuristic is dependent on the cost function, in a couple of ways. First, it must be in the same units. Second, you can't have a lower-cost path through actual nodes than the cost of the heuristic.
In the real world, used for things like navigation on a road network, your heuristic might be "the time a car would take on a direct path at 1.5x the speed limit." The cost for each road segment would use the actual speed limit, which will give a higher cost.
So, what is your cost function between tiles? Is it based on physical properties, or defined outside of your graph?