javascript - 星算法在javascript中的实现

Question

我正在尝试用 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

Answer 1

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

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

这里有一些关于 heuristic functions 的更多信息.