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*いません。ヒューリスティックは、実際に解決しようとしている問題に適している必要があり、特定のルールに従う必要があります (Zhihao がリンクしている回答は、それらをすべて説明しているようです)。

つまり、基本的には、実際の問題に使用する意味のあるヒューリスティックを決定し、それを関数に実装する必要があります。一つだけではありません。

ヒューリスティックが真のコストに近づくほど、検索が高速になることに注意してください。

于 2012-06-29T18:34:31.690 に答える
2

この投稿では、A* 検索のコンテキストで、適切なヒューリスティック関数について非常によく説明されています。

私が理解していることから、現在検討しているノードを通過しながら、開始ノードから終了ノードまでのコスト (コストを定義するものは何でも) を見積もる迅速な方法を提供する必要があります。これは、エンド ノードに到達するための最適なパスを決定するために使用されます。

ヒューリスティック関数の詳細については、次を参照してください。

于 2012-06-29T18:29:02.023 に答える
0

A * のヒューリスティック関数は、使用しているグラフの種類とグラフ内の移動に適用される規則によって異なります。私が知っている最も単純な関数の 1 つは、基本グリッド内の 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 に答える