星算法不起作用

Question

我根据维基百科页面 link to page 上的 A* 伪代码实现了这个算法，但它没有找到任何路径。当我使用它时，我永远不会达到当前节点等于目标的地步。我认为这可能与我的启发式或我初始化 f 和 g 分数的方式有关，但我似乎无法弄清楚。

我使用的地图大小为 1920 x 1080，像元大小为 30。

private ArrayList<Vector2> aStar(Vector2 start, Vector2 goal) {
    HashSet<Vector2> closedSet = new HashSet<Vector2>();
    ArrayList<Vector2> openSet = new ArrayList<Vector2>();
    openSet.add(start);
    HashMap<Vector2,Vector2> cameFrom = new HashMap<Vector2, Vector2>();
    HashMap<Vector2,Float> gScore = new HashMap<Vector2, Float>();
    HashMap<Vector2,Float> fScore = new HashMap<Vector2, Float>();
    ArrayList<Vector2> neighbors = new ArrayList<Vector2>();
    neighbors.add(new Vector2(0,30));
    neighbors.add(new Vector2(0,-30));
    neighbors.add(new Vector2(30,0));
    neighbors.add(new Vector2(-30,0));
    for(int i = 0; i < 1920; i +=30){
        for(int j = 0; j < 1080; j +=30){
            gScore.put(new Vector2(i,j),Float.MAX_VALUE);
            fScore.put(new Vector2(i,j),Float.MAX_VALUE);
        }
    }
    gScore.put(start,0f);
    fScore.put(start,heuristic(start,goal));

    while(!openSet.isEmpty()){
        int low = 0;
        for(int i = 0; i < openSet.size(); i++){
            if(fScore.get(openSet.get(i))<fScore.get(openSet.get(low))){
                low = i;
            }
        }
        Vector2 current = openSet.get(low);
        if(current.equals(goal)){
            System.out.println("YES!");
            return null;
        }
        openSet.remove(current);
        closedSet.add(current);
        for(Vector2 neighbor:neighbors){
            Vector2 tst = new Vector2(neighbor.x + current.x,neighbor.y + current.y);
            if(tst.x > -30 && tst.x <1920 && tst.y > -30 && tst.y < 1080){
                neighbor.add(current);
                if(closedSet.contains(neighbor)){
                    continue;
                }
                if(!openSet.contains(neighbor)){
                    openSet.add(neighbor);
                }

                float tentative_gScore = gScore.get(current) + heuristic(current,neighbor);
                if(tentative_gScore >= gScore.get(neighbor)){
                    continue;
                }

                cameFrom.put(neighbor,current);
                gScore.put(neighbor,tentative_gScore);
                fScore.put(neighbor,gScore.get(neighbor)+heuristic(neighbor,goal));
            }
        }

    }

    return null;
}

private float heuristic(Vector2 begin, Vector2 end) {
    return  (Math.abs(begin.x - end.x) + Math.abs(begin.y - end.y)) ;
}

Answer 1

行neighbor.add(current);改变了邻居。不仅如此，你还存储了那个邻居，这意味着这个对象引用将被保留，并可能在未来的代码中进一步扭曲。

另一个问题是你的启发式。您使用的是曼哈顿距离，这意味着有大量路径都具有相同的距离（只要您从不离开目标节点，每条路径的距离都相同）。尝试允许对角邻居，并使用欧几里得距离而不是曼哈顿距离。

Answer 2

很难找出所有代码中的错误。我会尝试，但我认为解决此问题的更好方法会对您有所帮助。

考虑制作一个 class 调用，例如 Node，对于每个节点 n，它具有以下项目：

节点路径
f(n)的值，从start到n的路径成本
g(n) 的值，启发式的成本，这是从 n 到目标。
元素或标签。

然后是一个递归求解的伪代码：

search_a_star(frontier)
    if(frontier.isEmpty())
       return false
    //Select node with lower f(n) + g(n)
    node = selectNode(frontier)
    if node is goal then 
       return node //You have in the node the cost and the path
    else
       //Generate the neighbours of your current node. You should calculate the heuristing of each neighbour.
       neighbours = generateNeighbours(node)
       //Add neighbours to reducedFrontier
       reducedFrontier = frontier - node
       newFrontier = add(reducedFrontier, neighbours) 
       search_a_star(newFrontier)

您应该保留一组已访问的节点。另外当你生成邻居时，你应该考虑这种情况进行循环控制：

如果生成的节点还没有被访问过，那么你应该将它添加到邻居集中。
如果生成的节点已经被访问过，但路径的成本比以前低，那么你应该从访问集中删除该节点并将其添加到邻居集中。
否则，不要将节点添加到邻居集中。

星算法不起作用

A star algorithm not working

java

algorithm

a-star