java A*star openlist未按预期工作

10 月，2 周 Questions & Answers 686

我曾经问过一个*的数据结构。我现在解决了这个问题。但还有另一个问题。我的A*速度很慢，没有我预期的效果。这意味着我用Java实现了Wikipedia伪代码（德语和英语）中的源代码。下图是我用于测试目的的图表。例如，该算法从节点1开始到目的地节点8。启发式函数将通过使用节点旁边方形制动器中的坐标计算曼哈顿距离。closedlist是从起始节点1（前置节点）构建到3（1）-6（3）-2（1）-4（1）-3（2）-2（3）-4（3）-8（6）。我认为A*是从1直接到8的，因为它是最短的路径。但它从6跳回到节点2，因为2的f值是列表中最低的。那么这是正确的吗？在示例中，我看到它在访问一个节点后，从未跳转回任何其他节点。我有一个从两个方向与其他节点相连的图。因此，我更改了源代码中的if条件，以证明反向方式是否在相应的列表中。否则它将以一个无休止的循环结束。问题是什么？为什么从节点6跳回到节点2？我必须删除openlist中的节点吗？ enter image description here

public ArrayList<NodeD> executeAstar(ArrayList<Arclistentry> data, NodeD start, NodeD dest)
{
    openlist = new PriorityQueue<NodeD>(1,comp);
    closedlist.clear();
    openlist.offer(start);
    start.setg(0);
    start.seth( manhattendistance(start, dest));
    start.setf(start.getg()+start.geth());
    while(!openlist.isEmpty())
    {
        NodeD currentnode = openlist.poll();
        if(currentnode.getnodenumber() == dest.getpredessor())
        {
            closedlist.add(currentnode);
            return closedlist;
        }
        closedlist.add(currentnode);
        for(int i=0; i< data.size(); i++)
        {
            if(data.get(i).getstart()==currentnode.getnodenumber())
            {
                NodeD successor = new NodeD(data.get(i).getnode(),data.get(i).getstart(), data.get(i).getcoorddest());
                NodeD reversesuccessor = new NodeD(data.get(i).getstart(),data.get(i).getnode(),data.get(i).getcoordstart());
                float tentative_g = currentnode.getg()+data.get(i).getcost();
                if((contains(successor, closedlist)||contains(reversesuccessor, closedlist))&&(tentative_g >=successor.getg()))
                {
                    continue;
                }
                if(!(contains(successor, openlist))|| (tentative_g < successor.getg()))
                {
                    successor.setpredessor(currentnode.getnodenumber());
                    successor.setg(tentative_g);
                    successor.seth(manhattendistance(successor, dest));
                    successor.setf(successor.getg()+manhattendistance(successor, dest));
                    if(!contains(successor, openlist))
                    {
                        openlist.offer(successor);
                    }
                }
            }
        }
    }
    ArrayList<NodeD> ret = null;
    return ret;
}

Python中文网

有 Java 编程相关的问题?

java A*star openlist未按预期工作

共 (1) 个答案

# 1 楼答案