3

ウィキペディアの記事でこの疑似から A* 検索アルゴリズムを実装しています。

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

     g_score[start] := 0    // Cost from start along best known path.
     h_score[start] := heuristic_cost_estimate(start, goal)
     f_score[start] := h_score[start]    // Estimated total cost from start to goal through y.

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

         remove x from openset
         add x to closedset
         foreach y in neighbor_nodes(x)
             if y in closedset
                 continue
             tentative_g_score := g_score[x] + dist_between(x,y)

             if y not in openset
                 add y to openset
                 tentative_is_better := true
             else if tentative_g_score < g_score[y]
                 tentative_is_better := true
             else
                 tentative_is_better := false

             if tentative_is_better = true
                 came_from[y] := x
                 g_score[y] := tentative_g_score
                 h_score[y] := heuristic_cost_estimate(y, goal)
                 f_score[y] := g_score[y] + h_score[y]

     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

f 値が最も低い openSet のノードを取得するように求められている行に行き詰まっています。openSet はいつ満たされましたか? ものによって？最初の実行で開始する必要がありますか？

また、再構築パスの擬似も理解していません：

 ArrayList<Point> reconstructPath(Point cameFrom, Point current_node){

        //if came_from[current_node] is set //what does it mean "ïs set"?
        //???
        return null;

    }

その擬似命令はどのように実装する必要がありますか?

 boolean AStar (Point start, Point goal){

        HashSet <Point>closedSet = new HashSet<Point>();
        HashSet <Point>openSet = new HashSet<Point>();
        HashMap <Point,Point> came_from = new HashMap<Point, Point>();

        HashMap <Point, Integer> g_score = new HashMap<Point, Integer>();
        HashMap <Point, Integer> h_score =new HashMap<Point,Integer>();
        HashMap <Point,Integer> f_score =new HashMap<Point,Integer>();

        g_score.put(start, 0);
        h_score.put(start, heuristic_cost_estimate(start,goal));
        f_score.put(start, heuristic_cost_estimate(start,goal));


        openSet.add(start);
        while(!openSet.isEmpty()){

            // x := the node in openset having the lowest f_score[] value
            //????
        }

        return false;

    }

 Integer heuristic_cost_estimate(Point start, Point goal){

        double minusI = (start.I-goal.I);
        int minusIi =(int)Math.pow(minusI,2.0D);

        double minusJ = (start.J-goal.J);
        int minusIj =(int)Math.pow(minusJ,2.0D);

        int ri = minusIj + minusIi;

        Integer result = new Integer(ri); 

        return result;


    }



ArrayList<Point> reconstructPath(Point cameFrom, Point current_node){

        //if came_from[current_node] is set //what does it mean "ïs set"?
        //???
        return null;

    }
4

1 に答える 1

2

オープン セットには、最初に、検索を開始するノード (開始ノード) が含まれています。

openset := set containing the initial node    // The set of tentative nodes to be evaluated.

パスの再構築部分については、ノードを処理Xし、現在のノードからより低いコストで隣接ノードに到達できることがわかるたびに、現在処理しているノードにcame_fromエントリを設定する必要Xがあります。宛先ノードが見つかったら、宛先ノードcame_fromからソース ノードに到達するまでエントリをたどってパスを再構築します。これを実装するには、Pointクラスを変更して、 という追加のフィールドを作成しcame_fromます。

ハッシュ テーブルから最小値を持つノードを抽出する唯一の方法は、ハッシュ テーブルを反復処理することです。別の方法は、最小値を持つ要素をすばやく見つけることができるツリー マップを追加することです (または、ヒープ内の要素の値をさらに減らすことができるバイナリまたはフィボナッチ ヒープなどの特殊なヒープを使用します)。

これは、私が最初に A* を学んだ場所です。

于 2011-05-27T22:39:28.507 に答える