0 Replies - 223 Views - Last Post: 03 April 2015 - 08:01 AM Rate Topic: -----

#1 Craigsup  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 03-April 15

A* PQ Implementation Updating error

Posted 03 April 2015 - 08:01 AM

So I'm using a PQ in my A* Algorithm implementation.
My implementation is created using the wiki page: http://en.wikipedia....earch_algorithm

I think I've figured out that my issue is coming from this section of pseudo-code:

if neighbor not in openset or tentative_g_score < g_score[neighbor] 
    came_from[neighbor] := current
    g_score[neighbor] := tentative_g_score
    f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
    if neighbor not in openset
         add neighbor to openset


Here is my implementation code:

          private Vertex dijkstra (int startLoc, int endLoc)
      {         
          Vertex startLocation = pqTemp.removeVertex(startLoc);      
          int y = 0;
          Vertex endLocation = pqTemp.QueueArray[y];
          while (endLocation.city != endLoc)
          {
              y++;
              endLocation = pqTemp.QueueArray[y];          
          }      
          
          startLocation.setTentativeDistance(0);      
          startLocation.setH(heuristic(endLocation, startLocation)); 
          startLocation.setF(startLocation.getH() + startLocation.getTentativeDistance());
          
          pqOpen.AddItem(startLocation);       
           while (!(pqOpen.IsEmpty()))
           {
                            
                System.out.println("PQ GetNextItem: " + currentNode.getF());
                for (int i = 0; i < pqOpen.GetQueueSize(); i++)
                {
                    System.out.print("Array data: " + pqOpen.QueueArray[i].getF());
                    if (pqOpen.QueueArray[i].getF() < currentNode.getF())
                    {
                        System.out.println("******** HERE *********");
                    }
                    else
                        System.out.println();
                }
                System.out.println();
                
               currentNode = pqOpen.GetNextItem();
               System.out.println();
               System.out.println("Currently at: " + currentNode.city);
               if (currentNode.city == 1937)
               {
                   System.out.println();
               }
              
               if (currentNode == null || currentNode.getTentativeDistance() == Double.POSITIVE_INFINITY)
               {
                   return null;
               }
               else if (currentNode.city == endLoc)
               {
                   return currentNode;
               }           
               else
               {
                  pqClosed.AddItem(currentNode);
                  
                  while (currentNode.neighbors.GetNoOfItems() > 0) //for each neighbor of currentNode
                  {         
                        Edge hold = (Edge)currentNode.neighbors.GetItem(0); 
                        currentNode.neighbors.DeleteItem(0);
                        
                        System.out.println("Visiting road: " + hold.label + " from id: " + hold.fromid + " toid: " + hold.toid);
                        int x = 0;
    
                        //gets the neighbor(Edge) into currentNodeUnvisited(Vertex)
                        Vertex currentNodeUnvisited = pqTemp.QueueArray[x];                    
                        while (x < pqTemp.GetQueueSize()&& hold.toid != currentNodeUnvisited.city)
                        {
                            currentNodeUnvisited = pqTemp.QueueArray[x]; 
                            x++;
                        }
                        
                        
                        //if the neighbor is in closed set, move to next neighbor
                        for(int z = 0; z < pqClosed.GetQueueSize() == false; z++)
                        {
                            if (pqClosed.QueueArray[z].city == currentNodeUnvisited.city)
                            {
                                break;
                            }                         
                        }                                      
                       
                        
                        double temp_g_score = (currentNode.getTentativeDistance() + hold.distance);
                         
                        //checks if neighbor is in open set
                        boolean foundNeighbor = false;
                        int z;
                        for(z = 0; z < pqOpen.GetQueueSize() && foundNeighbor == false; z++)
                        {
                            if (pqOpen.QueueArray[z].city == currentNodeUnvisited.city)
                            {
                                foundNeighbor = true;
                            }  
                        }
                        
                        
                        if (!(foundNeighbor) || temp_g_score < currentNodeUnvisited.getTentativeDistance())                        
                        {                        
                            currentNodeUnvisited.from = currentNode;
                            //data.AddItem(currentNodeUnvisited);
                            edgeResult.AddItem(hold);
                            currentNodeUnvisited.setTentativeDistance(temp_g_score);
                            currentNodeUnvisited.setH(heuristic(endLocation, currentNodeUnvisited));
                            currentNodeUnvisited.setF(currentNodeUnvisited.getH() + currentNodeUnvisited.getTentativeDistance());  
                            pqOpen.siftUp(z);
                            if (!(foundNeighbor)) // if neighbor isn't in open set, add it to open set
                            {
                                pqOpen.AddItem(currentNodeUnvisited);
                            }  
                            else // else it is already in open set (and priority will have changed) so need to sift up
                            {
                                pqOpen.siftUp(z);
                            }
                        }   
                        System.out.println("Temp arrived at: " + currentNodeUnvisited.city + " f = " + currentNodeUnvisited.getF());
                    }            
              }                          
          } 
         return null;
      }



I think the issue is that occasionally there will be a node (currentNodeUnvisited) that is in the pqOpen and therefore foundNeighbor will be true. If currentNodeUnvisited's TentativeDistance is greater than temp_g_score it will update currentNodeUnvisited's TentativeDistance which is already stored in the PQ and will have the wrong priority for it's index.
This means that I need to move currentNodeUnvisited to the correct index in the PQ?

So I did some research and concluded that I need to siftUp to do this, so I implemented this code into my Priority Queue class:
           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;
            }        
       }


I call this once currentNodeUnvisited's F has been updated so it should reorder its self based on the new priority. However I still get problems surrounding the order of my PQ.

I've put in some code so every loop round it will print out the getNextItem of the PQ and the contents of the PQ along with their priority - if the priority should be before the current lowest, it outputs "******* HERE *******" to highlight this. (As the test data is large I've uploaded it to pastebin: http://pastebin.com/FHa1WfHa

Please can you let me know if you require any further details or code. I'm desperately trying to solve this problem and get my code working as I've been working on it for a week now and feel like I've got nowhere!

Is This A Good Question/Topic? 0
  • +

Page 1 of 1