Java tas binaire ne fonctionne pas sur A * (non classé)

Question

J'utilise cette implémentation de Heap pour un algorithme *:

https://courses.cs.washington.edu/courses/cse373/11wi/homework/5/BinaryHeap.java

je légèrement modifié, mais seulement l'ajout contains méthode et renommer remove à poll, parce que j'ai déjà utilisé PriorityQueue mais cela n'a pas fonctionné.

Voici mon implémentation de l'interface Comparable<Spot>:

@Override 
public int compareTo(Spot o) { 
    Double.compare(getF(), o.getF()); 
} 

getF() rendements à deux ...

mais quand j'imprimer le Heap avec tous les getF() s que je vois ceci:

1. 176.0 
2. 175.0 
3. 180.0 
4. 176.0 
5. 223.0 
6. 182.0 
7. 146.0 
8. 177.0 
9. 87.0 
10. 202.0 
... 

Maintenant, le 175 est faux, car il est inférieur à 176, 87 est également faux ...

La même chose m'est arrivé avec PriorityQueue, qu'est-ce que je fais mal?

EDIT Voici mon A * la mise en œuvre:

public List<Spot> process(GameBodyObject me, Point target, ArrayList<GameBodyObject> others) throws Exception { 

    if(grid == null) { 
     throw new Exception("You have to initialize AStar first."); 
    } 

    grid.unsetObstacleForObject(me); 

    Spot start = grid.getSpotAtPosition(me.getPosition().getX(), me.getPosition().getY()); 
    Spot end = grid.getSpotAtPosition(target.getX(), target.getY()); 

    end = grid.moveSpotSoThatItDoesntCollide(end, me.getRadius()); 

    Heap<Spot> openSet = new Heap<Spot>(grid.getMaxSize()); 
    List<Spot> closedSet = new ArrayList<>(); 
    List<Spot> path = new ArrayList<>(); 

    openSet.add(start); 

    while(openSet.size() > 0) { 

     /*int winner = 0; 
     for(int i = 1; i < openSet.size(); i++) { 
      if(openSet.get(i).getF() < openSet.get(winner).getF()) { 
       winner = i; 
      } 
     }*/ 

     Spot current = openSet.poll(); //openSet.get(winner); 

     int i = 1; 
     for(Spot s : Arrays.asList(openSet.getArray())) { 
      if(s != null) { 
       System.out.println(i + ". " + s.getF()); 
       i++; 
      } 
     } 

     if(current.equals(end)) { 
      // We are done, reconstruct the path... 
      Spot temp = current; 
      path.add(temp); 
      while(temp.getPrevious() != null) { 
       path.add(temp.getPrevious()); 
       temp = temp.getPrevious(); 
      } 

      grid.resetObstacles(); 
      return path; 
     } 

     closedSet.add(current); 

     List<Spot> neighbors = current.getNeighbors(); 

     for(Spot neighbor : neighbors) { 
      if(!closedSet.contains(neighbor) && !grid.isCollidingWithObstacle(neighbor, me.getRadius())) { 
       double tempG = current.getG() + 1; 
       if(openSet.contains(neighbor)) { 
        if(tempG < neighbor.getG()) { 
         neighbor.setG(tempG); 
        } 
       } else { 
        neighbor.setG(tempG); 
        openSet.add(neighbor); 
       } 

       neighbor.setH(heuristic(neighbor, end)); 
       neighbor.setF(neighbor.getG() + neighbor.getH()); 
       neighbor.setPrevious(current); 
      } 
     } 

    } 

    grid.resetObstacles(); 
    return new ArrayList<>(); 
} 

Answer 1

Un problème commun lors de l'utilisation PriorityQueue Java ou implémentations tas similaires à mettre en œuvre Dijkstra ou des algorithmes * est le manque d'une méthode decreaseKey. Dijkstra ou A * ont parfois besoin de changer la priorité d'un élément inséré dans le tas. La seule façon de contourner la fonctionnalité manquante est de supprimer l'élément (qui est lent dans l'implémentation PriorityQueue de Java), puis de le réinsérer.

Mais il y a un problème avec ceci: En retirant l'objet du PQ/Heap, il doit toujours contenir la "vieille" priorité (getF() doit toujours retourner l'ancienne valeur dans votre cas), sinon l'élément ne peut pas être trouvé. Si l'élément contient déjà la nouvelle valeur, le PQ/Heap le cherchera dans le nouvel emplacement à supprimer, au lieu de l'endroit correspondant à l'ancienne valeur. Ainsi, la séquence doit être: (1) retirer l'élément de PQ, (2) adapter son poids/priorité, (3) le réinsérer dans le PQ.

Dans votre code, vous avez la partie suivante:

  if(openSet.contains(neighbor)) { 
       if(tempG < neighbor.getG()) { 
        neighbor.setG(tempG); // *1 
       } 
      } else { 
       neighbor.setG(tempG); 
       openSet.add(neighbor); 
      } 

      neighbor.setH(heuristic(neighbor, end)); 
      neighbor.setF(neighbor.getG() + neighbor.getH()); // *2 
      neighbor.setPrevious(current); 

Si vous regardez de près, vous modifiez le poids de neighbor à la ligne marquée *2 en raison du changement à la ligne *1. Pour résoudre ce problème, vous pouvez essayer ce qui suit:

  if(openSet.contains(neighbor)) { 
       if(tempG < neighbor.getG()) { 
        openset.remove(neighbor); // *3 
        neighbor.setG(tempG); 
       } 
      } else { 
       neighbor.setG(tempG); 
       // openSet.add(neighbor); // *4 
      } 

      neighbor.setH(heuristic(neighbor, end)); 
      neighbor.setF(neighbor.getG() + neighbor.getH()); 
      openSet.add(neighbor); // *5 
      neighbor.setPrevious(current); 

Cela supprime l'élément du Heap si elle est déjà là (*3) et il insère seulement après est calculé correctement le poids (*4, *5).

Le problème maintenant: Votre implémentation Heap n'offre pas une telle méthode remove(Object). Java PriorityQueue does.Vous devez donc passer à PriorityQueue de Java ou à une autre implémentation de tas qui offre une méthode remove(Object). (Ou même mieux: une méthode decreaseKey, de sorte que l'on n'aurait pas à supprimer un ré-insérer l'élément du tout).

Dans beaucoup de Dijkstra/A * -Implementations j'ai vu en utilisant le PQ de Java, cela a été mal fait dans la première tentative, menant à l'ordre incorrect du tas. Ne modifiez pas le poids/la priorité d'un élément déjà inséré dans un PriorityQueue ou un tas.