A*算法和启发式函数。在图上寻找最优路径。

Question

Wiki说，在这种情况下，启发式函数是估计从当前节点到目标的距离。

但是在这个代码中没有关于函数heuristic_cost_estimate的描述：链接到wikiperida。

是我对吗？.，例如，我有三个顶点的图。我必须有三个启发式从每个顶点到目标顶点，我设置了设置顶点？

矩阵(重量)：

0 5 2
1 0 3
1 2 0

每个顶点的启发式函数(值是指从当前顶点到目标的启发式成本，例如从2到目标的成本为3)：

5 3 4

这是个奇怪的假设，不是吗？我不知道哪个顶点是目标。在这一步，我如何建立启发式函数？

还是？.我有3个顶点和9个启发式算法。

图矩阵：

0 5 2
1 0 3
1 2 0

启发式成本：

0 5 10
5 0 10
3 8 0

意思是这个。如果3为目标，则从1到目标的启发式代价为3；如果2为目标，则1至2(目标)的成本为5。

还是我不对？

在我的例子中什么是启发式函数(在图上找到最优路径)？

Answer 1

启发式函数是一个函数h:V->R，其中V是你的顶点，R代表实数。换句话说--启发式函数给出了每个顶点的值，该值估计“它离目标有多近”。

启发式函数不能总是被使用，你需要在你的图表上有一些信息才能使用它们。

例如，如果您正在解决一个迷宫，矩阵中的每个单元(不是墙)都是一个顶点，相邻单元之间可能的移动表示边缘。

在本例中，启发式函数可以是曼哈顿距离 --即给定目标单元格t --启发式是h(v) = |t.x - v.x| + |t.y - v.y|。

如果你不知道你离你的目标有多近--你不能使用任何启发式函数，你就没有任何信息。(事实上，您唯一可以使用的启发式方法是不提供信息的启发，即针对每个h(v) = 0的v --但这是毫无意义的)。

还请注意，为了使A*成为最优的启发式函数(让它是h)，您需要它是可接受的-这意味着对于每个顶点v：h(v) <= d(v,target)，其中d(v,target)是从v到目标的真实距离。

注意，例如，曼哈顿距离启发迷宫是可以接受的。

希望这能解决你的困惑。