Java A*算法实现性能

Question

我已经编写了一个A*算法的工作实现，但是它不符合我的性能预期--它探索了太多的节点，并且比我预期的要花费更长的时间来找到路由。

private Vertex dijkstra(Vertex startLocation, Vertex endLocation, int routetype) 
{
    Long startTime = System.nanoTime();
    Vertex vertexNeighbour;        
    startLocation.setTentativeDistance(0);
    startLocation.setH(heuristic(endLocation, startLocation));
    startLocation.setF(startLocation.getH() + startLocation.getTentativeDistance());
    startLocation.from = startLocation;
    pqOpen.AddItem(startLocation);

    while (!(pqOpen.IsEmpty())) 
    {
        tempVertex = pqOpen.GetNextItem();
        if (tempVertex == null || tempVertex.getTentativeDistance() == Double.POSITIVE_INFINITY) 
        {
            //System.out.println("Route calculation time: " + ((System.nanoTime() - startTime)/1000000) + " ms");
            return null;
        } 
        else if (tempVertex.city == endLocation.city) 
        {
            for (int i = 0; i < pqClosed.queueSize; i++)
            {
                for (int z = 0; z < pqClosed.QueueArray[i].neighbors.GetNoOfItems(); z++)
                {
                    pqClosed.QueueArray[i].neighbors.GetItem(z).visited = false;
                }
            }
            //System.out.println("Route calculation time: " + ((System.nanoTime() - startTime)/1000000) + " ms");
            return tempVertex;
        } 
        else 
        {
            pqClosed.AddItem(tempVertex);               
            for (int i = 0; i < tempVertex.neighbors.GetNoOfItems() && tempVertex.neighbors.GetItem(i).visited == false; i++) //for each neighbor of tempVertex
            {
                tempEdge = tempVertex.neighbors.GetItem(i);
                tempVertex.neighbors.GetItem(i).visited = true;

                vertexNeighbour = allVertices.GetItem(binarySearch(allVertices, 0, allVertices.GetNoOfItems(), tempEdge.toid));
                nodesVisited++;

                boolean boolClosed = false;
                //if the neighbor is in closed set, move to next neighbor
                for (int z = 0; z < pqClosed.GetQueueSize(); z++) 
                {
                    if (pqClosed.QueueArray[z].city == vertexNeighbour.city) 
                    {
                        boolClosed = true;
                    }
                }
                if (boolClosed) 
                {
                    continue;
                }

                double temp_g_score = (tempVertex.getTentativeDistance() + tempEdge.distance);
                //checks if neighbor is in open set
                boolean foundNeighbor = false;

                for (int z = 0; z < pqOpen.GetQueueSize() && foundNeighbor == false; z++) 
                {
                    if (pqOpen.QueueArray[z].city == vertexNeighbour.city) 
                    {
                        foundNeighbor = true;
                    }
                }

                if (!(foundNeighbor) || temp_g_score < vertexNeighbour.getTentativeDistance()) 
                {
                    vertexNeighbour.from = tempVertex;
                    resultEdges.AddItem(tempEdge);
                    vertexNeighbour.setTentativeDistance(temp_g_score);
                    //calculate H once, store it and then do an if statement to see if it's been used before - if true, grab from memory, else calculate.
                    if (vertexNeighbour.getH() == 0)
                        vertexNeighbour.setH(heuristic(endLocation, vertexNeighbour)); 

                    if (routetype == 2)
                        vertexNeighbour.setF(((vertexNeighbour.getH() + vertexNeighbour.getTentativeDistance())*(0.000621371192) / tempEdge.speedlimit));
                    else
                        vertexNeighbour.setF(vertexNeighbour.getH() + vertexNeighbour.getTentativeDistance());

                    if (!(foundNeighbor)) // if neighbor isn't in open set, add it to open set
                    {
                        pqOpen.AddItem(vertexNeighbour);
                    }
                }
            }
        }
    }
    return null;
}    

private double heuristic(Vertex goal, Vertex next) 
{
    return (Math.sqrt(Math.pow((goal.x - next.x), 2) + Math.pow((goal.y - next.y), 2)))*1.10;
}

这是我的顶点课：

public class Vertex {   
    public int city, x, y;
    public boolean visited = false;
    public EdgeVector neighbors;
    private double f;  // f = tentativeDistance + h 
    private double tentativeDistance;  // tentativeDistance is distance from the source
    private double h;  // h is the heuristic of destination.    
    public Vertex from; 

    public Vertex(int city, int x, int y)
    {
        this.city = city;
        this.x = x;
        this.y = y; 
        this.neighbors = new EdgeVector();
        this.tentativeDistance = Double.POSITIVE_INFINITY;
        this.f = Double.POSITIVE_INFINITY;
    }   

    public void addEdge(Edge city)
    {
       this.neighbors.AddItem(city);       
    }  

    public double getTentativeDistance() 
    {
        return tentativeDistance;
    }

    public void setTentativeDistance(double g) 
    {
        this.tentativeDistance = g;
    }

    public double getF() 
    {
        return f;
    }

    public void setF(double f)
    {
        this.f = f;
    }

    public double getH() 
    {
        return h;
    }

    public void setH(double h) 
    {
        this.h = h;
    }
}

我的边缘班：

public class Edge {
    public String label;
    public int fromid, toid, speedlimit;
    public double distance;
    public boolean visited;

    public Edge(String label, int fromid, int toid, double distance, int speedlimit)
    {
        this.label = label;
        this.fromid = fromid;
        this.toid = toid;
        this.distance = distance; 
        this.speedlimit = speedlimit;
        this.visited = false;
    }    
}

最后，我使用了我自己的向量类：

    public class Vector {
  private static final int MAXDISPLAY=20;

  private int growby;
  private int noofitems;
  private Object[] data;

  private static final int MINGROW=10;

  public Vector()
  {
    Init(10);
  }

  public Vector(int initsize)
  {
    Init(initsize);
  }

  private void Init(int initsize)
  {
    growby=initsize;

    if (growby<MINGROW)
      growby=MINGROW;

    noofitems=0;
    data=new Object[initsize];
  }

  public int GetNoOfItems()
  {
    return noofitems;
  }

  public Object GetItem(int index)
  {
    return (Object)(index>=0 && index<noofitems?data[index]:null);
  }

  public void AddItem(Object item)
  {
    if (noofitems==data.length)
      GrowDataStore();
    data[noofitems++]=item;
  }

  public boolean InsertItem(int index, Object item)
  {
    if (index>=0 && index<=noofitems)
    {
      if (noofitems==data.length)
        GrowDataStore();
      for (int i=noofitems; i>index; i--)
        data[i]=data[i-1];
      data[index]=item;
      ++noofitems;
      return true;
    }
    else
      return false;
  }

  public boolean DeleteItem(int index)
  {
    if (index>=0 && index<noofitems)
    {
      --noofitems;
      for (int i=index; i<noofitems; i++)
        data[i]=data[i+1];
      return true;
    }
    else
      return false;
  }

  public void ResetData(int[] items)
  {
    if (items!=null && items.length==noofitems)
      System.arraycopy(items, 0, data, 0, noofitems);
  }

  public void Swap(int index1, int index2)
  {
    if (index1>=0 && index1<noofitems && index2>=0 && index2<noofitems)
    {
      Object tmp=data[index1];
      data[index1]=data[index2];
      data[index2]=tmp;
    }
  }

  private void GrowDataStore()
  {
    Object[] tmp=new Object[noofitems+growby];
    System.arraycopy(data, 0, tmp, 0, noofitems);
    data=tmp;
  }

  public void Randomise()
  {
    for (int i=0; i<noofitems; i++)
    {
      int pos=(int) (Math.random()*noofitems);
      Swap(i, pos);
    }
  }

  public String toString()
  {
    StringBuilder str=new StringBuilder();
    str.append('[');
    if (noofitems>0)
      str.append(data[0]);

    int max=(noofitems<MAXDISPLAY?noofitems:MAXDISPLAY);
    for (int i=1; i<max; i++)
    {
      str.append(", ");
      str.append(data[i]);
    }
    if (noofitems>MAXDISPLAY)
    {
      str.append(", ...(");
      str.append(noofitems-MAXDISPLAY);
      str.append(')');
    }
    str.append(']');
    return str.toString();
  }

}

请注意，我有EdgeVector和VertexVector类，它们只是对上面向量类的修改(将对象替换为边缘或顶点)--我没有发布它们，因为它们占用了大量的post空间。我这样做是因为它比在算法中将对象转换为顶点或边缘更有效。

我希望有人能快速查看我的代码，看看我可能出了什么问题--代码确实工作并产生了正确的结果，但是它确实探索了比我预期和想要的节点更多的节点，因此大大增加了运行时间。

这看起来是我很长一段时间来编写的，因为我是个新手，我花了一天的大部分时间来看看我做了什么不正确的事情，这导致了问题，但我什么也找不到。

我自己对PQ的执行情况：

public class PriorityQueue 
{
    Vertex[] QueueArray = new Vertex[10]; 
    int queueSize = 0;

  // Default Constructor
  public PriorityQueue()
  {
  }

  // Returns true if the priority queue is empty, else false
  public boolean IsEmpty()
  {
    if (queueSize == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
  }

  // Returns the number of items in the queue
  public int GetQueueSize()
  {
    return queueSize;
  }

  public Vertex removeVertex(int info)
  {
      int i = 0;
      boolean found = false;
      Vertex data = null;
      for (i = 0; i < QueueArray.length && found == false; i++)
      {
          if(QueueArray[i].city == info)
          {
              found = true;
              data = QueueArray[i];
          }          
      }

      if (found == true)
      {
          for (i = i; i < QueueArray.length-1; i++)
          {
              QueueArray[i] = QueueArray[i+1];
          }
          QueueArray[queueSize] = null;
          queueSize--;
      }


      return data;
  }

  public void AddItem(Vertex item)
  {    
      if (queueSize == QueueArray.length)
      {
          Vertex[] QueueArray2 = new Vertex[queueSize*2];          
          System.arraycopy(QueueArray, 0, QueueArray2, 0, queueSize);           
          QueueArray = QueueArray2;         
      }

    if (queueSize == 0)
    {
      QueueArray[queueSize] = item; // insert at 0
      queueSize++;
    }
    else
    {
        int index=queueSize;
        //Vertex newNode = new Vertex(item, priority);
        QueueArray[index] = item;
        queueSize++;

        int parent=(index-1)/2;
        while (index!=0 && QueueArray[index].getF()<QueueArray[parent].getF())
        {
            // swap parent and index items
            Vertex temp = QueueArray[parent];
            QueueArray[parent] = QueueArray[index];
            QueueArray[index] = temp;

            index=parent;
            parent=(index-1)/2;
        } 
    }     
  }


  public Vertex GetNextItem()
  {
      if (queueSize == 0)
      {
          return null;
      }
      Vertex temp = QueueArray[0];
      --queueSize;
      if (queueSize > 0)
      {
         QueueArray[0] = QueueArray[queueSize];
         swapNodes(0);
      }
      QueueArray[queueSize] = null;
      return temp;
   }

   public void swapNodes(int root)
   {
      int child;                        
      if ((2*root+1) >= queueSize)
      {
         child = root;        //no children
      }
      else 
          if ((2*root)+2 == queueSize)
          {
                child = (2*root)+1;     
          }
          else 
            if (QueueArray[(2*root)+1].getF()< QueueArray[(2*root)+2].getF())
            {
                 child = (2*root)+1;   //left child  
            }
            else
            {
                 child = (2*root)+2;     //right child
            }
      //swap the nodes around
      if (QueueArray[root].getF() > QueueArray[child].getF())
      {
         Vertex temp = QueueArray[root];
         QueueArray[root] = QueueArray[child];
         QueueArray[child] = temp;
         swapNodes(child);
      }
   }


   public void siftUp(int root)
   {       
       while (root > 0 && root < queueSize && (QueueArray[root].getF() < QueueArray[(root-1)/2].getF()))
       {
            Vertex temp = QueueArray[root];
            QueueArray[root] = QueueArray[(root-1)/2];
            QueueArray[(root-1)/2] = temp;

            root = (root-1)/2;
        }        
   }


  public String toString()
  {
    return super.toString();
  }

}

该程序是一个卫星导航，有许多顶点，可以有边缘连接它们.每个顶点的邻居都存储在顶点类本身的VortexVector中。如果我可以上传我的程序的压缩，可能会更容易一些，因为我通过从两个.bat文件中读取边缘和顶点数据来测试我的程序(每个文件包含25万个数据)，但是我认为有一些规则是针对用户安全的吗？

Answer 1

当您更新顶点的估计距离时，您应该向openQueue发出信号，以更新它在后备数组中的位置。

if (!(foundNeighbor)) // if neighbor isn't in open set, add it to open set
{
    pqOpen.AddItem(vertexNeighbour);
}
else
{
    pqOpen.UpdateItem(vertexNeighbour);
}

这意味着您需要在优先级队列中再次找到它，并在需要时将其移开。

因此，您可以删除for循环并将名称更改为AddOrUpdateItem。

这可以是更有效的，首先收集所有变化的邻居以外的环对所有邻居。然后提交更改顶点的集合。

这为您节省了打开集中所有顶点的循环，使其每个pqOpen.GetNextItem()只运行一次。

甚至可以通过使用辅助索引(如HashMap)来保存该循环，该索引将允许您在恒定时间内找到每个更改的顶点的索引。

Answer 2

我不知道这是否是你问题的主要原因，但这部分肯定会跳出我的心扉：

//if the neighbor is in closed set, move to next neighbor
for (int z = 0; z < pqClosed.GetQueueSize(); z++) 
{
    if (pqClosed.QueueArray[z].city == vertexNeighbour.city) 
    {
        boolClosed = true;
    }
}

由于pqClosed在遍历图时增长，这个循环将变得越来越昂贵。考虑使用Set或Map而不是任何pqClosed。

Answer 3

这段代码有几个问题(对我来说很难理解)：

1. 当SetF更新估计优先级队列并不总是更新(特别是如果节点已经存在的话)，这可能会使更多的节点遍历然后需要。
2. 我可以保证代码并不总是产生正确的结果，因为用户特性可能比实际路径长度更大。
3. F型== 2(？)说不通就行。

以上问题可能导致更多节点被遍历或结果不正确。但是，还有更多的问题需要考虑来解决：

1. 编写自己的容器是浪费时间(除非您有一个数据结构类，这显然不是这里的情况)。为此使用标准Java类，它们是泛型的，因此可以为不同元素提供列表和列表，而不是相同代码的副本。
2. 一些命名的问题。特别是，dijkstra不是dijkstra和pqOpen，前缀为wierd，揭示了实现细节。
3. 考虑将dijkstra函数(重命名后)拆分为几个更简洁的函数。现在是一团糟。
4. 看来你做了更多的搜索，然后需要，虽然我没有完全的知识，你的领域。考虑把顶点引用到边。并考虑向顶点添加bool字段(比如访问的字段)，这样您就可以询问顶点是已被放入封闭的还是已打开的。