PriorityQueue удаляет последний добавленный элемент (действует как lifo)

Question

Мне нужна еще одна пара глаз, чтобы посмотреть на эту проблему. Я реализовал как первый поиск, так и поиск по пятам первого уровня для проблемы, которую я пытаюсь решить. В очереди/стеке, используемой на основе поиска, используются объекты Node.

Проблема заключается в том, что оба алгоритма поиска возвращают одну и ту же последовательность. Изучив его больше, кажется, что очередь приоритетов в алгоритме BFS делает новый элемент, который добавляет HEAD очереди.

Примечание Я также попытался изменить структуру данных, как следует, поскольку она по-прежнему дает тот же результат.

PriorityQueue <Node> fifo = new PriorityQueue <Node>(); 

Я следую стандартным методам добавления и удаления/опроса, предоставляемых интерфейсом. Ниже приведен код для алгоритма BFS.

public static void BFS(Node initial, char [][] grid){ 
    Queue <Node> fifo = new LinkedList <Node>(); 
    ArrayList<Node> explored = new ArrayList<Node>(); 
    int l = 0; 
    fifo.add(initial); 
    //Make a method to test if there is any dirt remaining on the grid for THIS node 
    boolean dirtExists = testDirt(initial.dirtCoordinates); 
    //System.out.println("complete boolean value is: " + dirtExists); 
    if(!dirtExists){ 
     //If no dirt, then we are done 
    } 
    else{ 
     while(dirtExists){ 
     //Test whether there are any more elements in the queue. If not, then done 
      if(fifo.isEmpty()){ 
       break; 
      }else{ 
       //Grab the next element in the queue 
       Node nextNode = fifo.poll(); 
       explored.add(nextNode); 
       System.out.println("First element removed " + nextNode.stringBuilder); 
       if(testDirt(nextNode.dirtCoordinates)){ 
        dirtExists = true; 
       }else{ 

        dirtExists = false; 
        break; 
       } 
       //System.out.println(nextNode.stringBuilder); 
       //System.out.println(dirtExists); 
       List<Node> possibleMoves; 
       possibleMoves = successor(nextNode, grid); 
       //System.out.println(possibleMoves.size()); 

       for(int i=0; i<possibleMoves.size(); i++){ 
         Node temp = possibleMoves.get(i); 
         System.out.println("About to enter the queue " + temp.stringBuilder); 

         //Need to make sure this nextNode does not exist in explored OR the fifo already 
         //Dont worry about this, it still adds new unique nodes to the fifo, i just dont know why its adding it to the head 
         if(compareNodes(temp, fifo, explored)){ 
          //Then do not add because it is a duplicate 
         }else{ 
          System.out.println("Just got added to the queue " + temp.stringBuilder); 
          fifo.add(temp); 
         } 
       } 
       System.out.println("Head of the queue is: " + fifo.peek().stringBuilder); 
      } 
     } 
    } 

} 

Как Коди снизу отметил

Все, что я проходил переменную ФИФО в метод, в котором я использовал функцию опроса. Это вызвало проблему.

Так что я избавился от опроса, который я сделал в функции, и просто повторил в очереди.

Проблема решена!

Answer 1

Измените свой метод. Удалить опрос, потому что он удаляется из исходного списка. Вы можете напрямую использовать метод equals, который вы можете сгенерировать в своем классе Node.

private static boolean compareNodes(Node currentNode, Queue<Node> fifo, ArrayList<Node> explored){ 
    boolean exists = false; 
    while(!fifo.isEmpty()){ 
     exists = fifo.contains(currentNode); 
     if(exists){ 
      //System.out.println("Exists in fifo"); 
      break; 
     } 
    } 
    if(exists){ 

    }else{ 
     for(Node n: explored){ 
      if(n.equals(currentNode)){ 
       //System.out.println("Exists in explored"); 
       exists = true; 
       break; 
      }else{ 
       //keep on going 
      } 
     } 
    } 

    return exists; 
}