为 A* 算法寻找启发式的一些好方法是什么? [英] What are some good methods to finding a heuristic for the A* algorithm?

问题描述

您有一张方形图块的地图，您可以在其中向 8 个方向中的任何一个方向移动.鉴于你有一个名为 cost(tile1, tile2) 的函数，它告诉你从一个相邻的瓷砖移动到另一个的成本，你如何找到一个既可以接受的启发式函数 h(y,goal)并且一致?在给定此设置的情况下，是否可以推广用于查找启发式的方法，还是会根据 cost 函数而有所不同?

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?

推荐答案

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 :

在允许 8 个移动方向的方形网格上，使用对角线距离 (L∞).

On a square grid that allows 8 directions of movement, use Diagonal distance (L∞).

这篇关于为 A* 算法寻找启发式的一些好方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！