1

我正在尝试在 Javascript 中实现 A 星算法。但我面临的问题在于 heuristic_cost_estimate 函数。我不知道如何实现这一点。至于这个函数的定义在哪里。我不想要整个代码，只想要函数。

 function A*(start,goal)
         closedset := the empty set    // The set of nodes already evaluated.
         openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
         came_from := the empty map    // The map of navigated nodes.

         g_score[start] := 0    // Cost from start along best known path.
         // Estimated total cost from start to goal through y.
    *************************************************** heurisctic function******************  

   f_score[start] := g_score[start] + ***heuristic_cost_estimate(start, goal)***

         while openset is not empty
             current := the node in openset having the lowest f_score[] value
             if current = goal
                 return reconstruct_path(came_from, goal)

             remove current from openset
             add current to closedset
             for each neighbor in neighbor_nodes(current)
                 if neighbor in closedset
                     continue
                 tentative_g_score := g_score[current] + dist_between(current,neighbor)

                 if neighbor not in openset or tentative_g_score < g_score[neighbor] 
                     add neighbor to openset
                     came_from[neighbor] := current
                     g_score[neighbor] := tentative_g_score
                     f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)

         return failure

     function reconstruct_path(came_from, current_node)
         if came_from[current_node] is set
             p := reconstruct_path(came_from, came_from[current_node])
             return (p + current_node)
         else
             return current_node
4

3 回答 3

2

这篇文章在 A* 搜索的上下文中对适当的启发式函数提供了很好的解释。

据我了解，它应该提供一种快速的方法来估算从开始到结束节点的成本（无论您定义的成本是多少），同时通过您当前正在考虑的节点。它用于帮助确定到达终端节点应采取的最佳路径。

这是有关启发式函数的更多信息。

于 2012-06-29T18:29:02.023 回答
2

该功能不是预定义的，因为它会根据您的用途而变化A*。启发式必须适合您实际尝试解决的问题，并且必须遵循某些规则（Zhihao 链接到的答案似乎将它们全部拼写出来）。

所以基本上：你必须决定什么是对你的实际问题有意义的启发式，然后在一个函数中实现它。不止一个。

请注意，您的启发式方法越接近真实成本，您的搜索速度就越快。

于 2012-06-29T18:34:31.690 回答
0

A * 的启发式函数取决于您使用的图形类型以及适用于通过它的移动的规则。我知道的最简单的函数之一适用于基本网格中的 4 方向移动（上、下、左、右），称为曼哈顿距离，可能看起来很简单：

function manhattan (pos0, pos1) {
  var d1 = Math.abs(pos1.x - pos0.x);
  var d2 = Math.abs(pos1.y - pos0.y);
  return d1 + d2;
}

但是，如果您的环境允许对角线移动，那么您需要另一种支持 8 个方向的启发式类型：

function diagonal (pos0, pos1) {
  var D = 1;
  var D2 = Math.sqrt(2);
  var d1 = Math.abs(pos1.x - pos0.x);
  var d2 = Math.abs(pos1.y - pos0.y);
  return (D * (d1 + d2)) + ((D2 - (2 * D)) * Math.min(d1, d2));
}

当然，这些只是示例，其他答案中还指出了许多其他示例。

一般来说，如果解释得当，这个算法可能看起来相当简单。但是编码它是一项不同的任务，对于初学者来说可能是一个相当大的挑战。我建议检查一些用您选择的语言编写的工作库。然后，您可以根据自己的需要调整它或从头开始编写自己的。

更多链接：

Javascript中的好例子

启发式函数理论

于 2020-10-14T18:17:28.177 回答