javascript中的星型算法实现

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

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

来源

2012-06-29 V.V.S Laxman

您是否要求我们将此伪代码翻译成JavaScript？ –

不，不......一点都不......我自己就这样做...我在问启发式功能....我怎么定义它？我没有看到它在算法中的定义。尽管我知道它的用法。但在程序中它让我感到困惑 –

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

从我所了解的情况来看，它应该提供一种快速的方式来估算当前考虑的节点在开始到结束节点期间的成本（无论您如何定义成本）。它用于帮助确定您应该达到最终节点的最佳路径。

以下是关于heuristic functions的更多信息。

来源

2012-06-29 18:29:02 Zhihao

谢谢..我试图通过djkshtras来解决问题，尽管 –

该功能没有预先定义，因为它根据您使用A*所做的更改而变化。启发式必须适合您实际尝试解决的问题，并且必须遵循一定的规则（志豪链接的答案似乎将它们拼出来）。

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

请注意，您的启发式“越好”接近真实成本，您的搜索速度越快。

来源

2012-06-29 18:34:31

是在实际问题中，我将给出一个图表，其中包含代表边界的节点和节点之间的距离。然后我必须计算最短路径。在这种情况下isnt dijkstra更好。我正在做代码..生病发布为sonn，因为我完成它 –

Djikstra的算法与启发式总是返回零的'A *'实现完全相同。 –

javascript中的星型算法实现

回答

相关问题