java - A-Star 算法像 Dijkstra 一样运行并给出错误的结果

Question

我正在尝试基于 OSM 数据在 Java 中实现 A-Star。我的问题是我的实现无法正常工作。首先，路径不是最短的。其次，closelist 最终包含的节点比 Dijkstra 多 1/3。这实际上不是我所期望的。

这是我的 A-Star 代码，基于 Wikipedia Pseudocode

public Object[] executeAstar(ArrayList<Arclistentry> data, NodeD start, NodeD dest,long[] nodenur)
{
    openlist = new PriorityQueue<NodeD>(1,comp);
    closedlist.clear();
    openlist.offer(start);
    start.setg(0);
    start.seth(calccost(start, dest));
    start.setf(start.getg()+start.geth());
    while(!openlist.isEmpty())
    {
        NodeD currentnode = openlist.poll();
        if(currentnode.getnodenumber() == dest.getpredessor())
        {
            closedlist.add(currentnode);
            return drawway(closedlist, start, dest);
        }
        closedlist.add(currentnode);
        ArrayList<Arclistentry> entries = neighbors.get((int)currentnode.getnodenumber()-1);
        for(Arclistentry aentry:entries)
        {
            NodeD successor = new NodeD(aentry.getnode(),aentry.getstart(), aentry.getcoorddest());
                float tentative_g = currentnode.getg()+calccost(currentnode,successor);//+aentry.getcost();
                if(contains(successor, closedlist))
                {
                    continue;
                }
                if((contains(successor,openlist))&& tentative_g >= aentry.getcost())
                {
                    continue;
                }

                        if(!contains(successor, openlist))
                        {
                            successor.setpredessor(currentnode.getnodenumber());
                            successor.setg(tentative_g);
                            successor.seth(calccost(successor, dest));
                            successor.setf(successor.getg()+successor.geth());
                            openlist.offer(successor);
                        }
                        else
                        {
                            openlist.remove(successor);
                            successor.setpredessor(currentnode.getnodenumber());
                            successor.setg(tentative_g);
                            successor.seth(calccost(successor, dest));
                            successor.setf(successor.getg()+successor.geth());
                            openlist.offer(successor);
                        }
        }
    }
    return drawway(closedlist,start, dest);
}

我的启发式将使用欧几里德距离进行计算。但要考虑节点的成本，成本需乘以启发式结果。我的数据结构包含以下内容:

private long nodenumber;
private long predessor;
private float label;
private float f;
private float g;
private float h;
private double[] coord = new double[2];

public NodeD(long nodenr, long predessor, double[] coor)
{
    this.nodenumber = nodenr;
    this.predessor = predessor;
    this.coord = coor;
}
public NodeD(long nodenr, long predessor, float label)
{
    this.nodenumber = nodenr;
    this.predessor = predessor;
    this.label = label;
}

对于 arclist，我使用以下内容:

private long start;
private long dest_node;
private float cost_;
private double[]coordstart = new double[2];
private double[]coorddest = new double[2];

包含优先级队列功能:

public boolean contains(NodeD o, PriorityQueue<NodeD> al)
 {
     Iterator<NodeD> e = al.iterator();
     if (o==null)
     {
          while (e.hasNext())
          {
             if (e.next()==null)
             {
                 return true;
             }
          }
     }
     else
     {
         while (e.hasNext())
         {
             NodeD t = e.next();
             if(t.equals(null))
             {
                 return false;
             }
             if (((o.getnodenumber()==t.getnodenumber()) & (o.getpredessor()==t.getpredessor()))||(o.getnodenumber()==t.getpredessor() & o.getpredessor()==t.getnodenumber()))
             {
                 return true;
             }
         }
             return false;
     }
     return false;
 }

并且包含 ArrayList(因为它没有使用 ArrayList.contains 函数正确检测

public boolean contains(NodeD o, ArrayList<NodeD> al) {
           return indexOf(o,al) >= 0;
       }

public int indexOf(NodeD o, ArrayList<NodeD> al) {
        if (o == null) {
            for (int i = 0; i < al.size(); i++)
                if (al.get(i)==null)
                    return i;
        } else {
                   for (int i = 0; i < al.size(); i++)
                   {
                      if ((o.getpredessor()==al.get(i).getpredessor())) //(o.getnodenumber()==al.get(i).getnodenumber()) &&
                      {
                           return i;
                      }
                       else if((o.getpredessor()==al.get(i).getnodenumber())&&(o.getnodenumber()==al.get(i).getpredessor()))
                      {
                          return i;
                      }
                   }
               }
        return -1;
}

问题在于该算法正在访问所有节点。另一个问题是排序的 openlist，它会将当前节点的邻居向上推，因为它们的 f 值较低。那么我通过实现这个算法犯了什么错呢？

Answer 1

回顾我们之前的所有答案:

• 确保 A* 估计值较低，否则会错误地跳过部分

• 不要迭代所有节点来确定数组中当前节点边集的边索引

• 创建新对象放入队列/集合时，应检查节点的属性
• 如果您注重速度，请尽快中止不感兴趣的搜索，从而避免尽可能多的工作

我仍然不确定这一行:

if((包含(后继者,openlist))&& tentative_g >= aentry.getcost())

我认为您想要做的是避免在队列中已经有更好的值时将新节点添加到队列中。然而， tentative_g 是从起始节点到当前节点的路径长度，而 aentry.getcost 似乎是您正在放松的边的长度。这对我来说似乎不对...尝试检索正确的(旧)值以与新的暂定标签进行比较。

最后，对于您当前的代码，我还将进行以下更改:

• 使用 HashSet 作为您的关闭列表。每次检查节点是否在其中时，都必须遍历所有节点，这效率不高...尝试通过覆盖 NodeD 对象的哈希函数来使用 HashSet。内置的 contains-function 比您当前的方法快得多。可以为您的 openlist 提出类似的论点。您无法将 PQ 更改为集合，但可以省略包含检查。如果您添加一个优先级较差的节点，您将始终首先轮询正确的优先级(因为它是 PQ)，然后在轮询不良优先级时可以跳过它。这是一个小的优化，将 PQ 的大小与 PQ 查找操作进行权衡

• 通过计算一次并在需要时重用该值来避免重新计算内容(主要是 calccost())(时间增益较小，但代码更好)。

• 尝试通过将相同代码放在正确的行上来避免多行(例如，如果您有 if(..) {doA();doB()}else{doA();doC();} 尝试将 doA() 放在 if 之前以方便阅读)