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中的星型算法實現

回答

相關問題