我曾经问过 A* 的数据结构。我现在解决了这个问题。但是还有另一个问题。我的 A* 很慢，没有按我的预期工作。这意味着我从 Wikipedia Pseudocodes（德语和英语）中用 Java 实现了源代码。下图中的图表是我用于测试目的的图表。例如，该算法从节点 1 开始到目标节点 8。启发式函数将通过使用曼哈顿距离使用节点旁边的方闸中的坐标来计算。封闭列表是从起始节点 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？我必须删除我的开放列表中的节点吗？问题是什么，为什么它会从节点 6 跳回节点 2？我必须删除我的开放列表中的节点吗？问题是什么，为什么它会从节点 6 跳回节点 2？我必须删除我的开放列表中的节点吗？
.
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;
}