PriorityQueue, où j'avais des problèmes avec la méthode Dyxtra en utilisant la liste de contiguïté (java)

La programmation compétitive, à laquelle j'ai commencé à penser à pratiquer la programmation, devient une pratique régulière.

Ce que j'ai appris

• Comment utiliser la file d'attente prioritaire
• Comment utiliser l'interface du comparateur
• Comment utiliser l'interface clonable

Problèmes avec ce qui précède et leurs solutions.

Ce que je voulais faire

J'ai essayé de résoudre le problème d'arborescence de routes minimales ALDS C. Méthode Dyxtra utilisant la liste adjacente.

Par exemple, étant donné un cas de test comme celui de l'image ci-dessous, chaque nœud affiche la distance la plus courte à atteindre à partir du nœud 0. 0 est la distance 0, 1 est la distance 1, 3 est la distance 5, et ainsi de suite.

procédure

Initialisez 0 en tant que nœud recherché à une distance de 0. Une boucle qui recherche le nœud non recherché le plus proche parmi les nœuds recherchés. Si un nœud non recherché est déjà recherché, la distance la plus courte du nœud adjacent peut changer. Par conséquent, la recherche est effectuée lors de la mise à jour de la distance de chaque nœud. Dans le cas d'une image, elle sera recherchée dans l'ordre de 0 → 1 → 2 → 5 → 4 → 3 → 6 → 7 → 8, par exemple, 3 sera mis à jour en tant que distance 13 (après 0 recherche) → 5 (après 4 recherches). ..

1. Définissez la classe Node avec les propriétés suivantes

class Node{ int id; //Numéro de nœud int d=INFTY; //Distance la plus courte du nœud 0 ← Rechercher lors de la mise à jour int color=0; //Valeur initiale 0,Si déjà recherché 1 TreeMap<Integer,Integer> child =new TreeMap<>(); //{id:Poids latéral}Liste des nœuds adjacents au format }

 1. Définissez les variables suivantes dans la méthode main ()
 --`queue`: file d'attente prioritaire qui stocke les objets Node dans l'ordre d ** (Problème 1) **
 --`nodes [] `: Un tableau qui stocke chaque nœud dans le dernier état
 1. Définissez la distance de 0 à 0 (`nodes [0] .d = 0;`) et placez-la dans la file d'attente prioritaire. Actuellement, «queue» ne contient que 0 nœuds.



 1. Sélectionnez par ʻu = queue.poll () `. Faites une recherche et mettez à jour si le `d` du nœud adjacent peut être mis à jour. ** (Problème 2) **
 Dans le cas de l'image, la première mise à jour est la suivante.

    ```
nodes[1].d=1;
nodes[3].d=13;

1. Placez un nœud adjacent (non recherché) dans la file d'attente prioritaire. À ce stade, la première fois, les références aux «nœuds [i](i = 1,3)» sont disposées dans la «file d'attente» par ordre croissant de «d».
2. Extrayez le nœud avec le plus petit «d» de la «file d'attente» et sélectionnez-le. Après cela, répétez les étapes 4 à 6. ** (Problème 3) **

Pourquoi avez-vous eu des ennuis?

• (Problème 1) Je n'étais pas doué pour mettre des objets dans PriorityQueue et j'ai reçu un avertissement (cela fonctionnait localement, mais un juge en ligne a eu une erreur de compilation)
• (Problème 2) La file d'attente prioritaire peut contenir plusieurs données faisant référence au même objet
• ** (Trouble 3) PriorityQueue ne reconstruit pas la commande même si la destination de référence est mise à jour (= la commande est dans le désordre) **

↓ Détails

Je n'étais pas doué pour mettre des objets dans PriorityQueue et j'ai reçu un avertissement (cela fonctionnait localement mais j'ai eu une erreur de compilation avec un juge en ligne)

Ce qui suit est correct. Cela placera Node au début de la file d'attente dans l'ordre croissant de d.

class MyComparator implements Comparator<Node>{
    @Override
    public int compare (Node n1, Node n2) {
        int d1 = n1.d;
        int d2 = n2.d;

        if (d1 > d2) {
            return 1;
        } else if (d1 < d2) {
            return -1;
        } else{
            return 0;
        }
    }
}
//Ci-dessous principal()Dans la méthode
Queue<Node> queue = new PriorityQueue<>(new MyComparator());

Je ne connaissais pas l'expression lambda il y a quelque temps, donc lorsque j'ai recherché une implémentation d'interface traditionnelle, j'ai échoué car de nombreux sites n'utilisaient pas de génériques comme indiqué ci-dessous.

class MyComparator implements Comparator {
    public int compare (Object o1, Object o2){//En traitement}
}//Ci-dessous principal()Dans la méthode
Queue<Node> queue = new PriorityQueue<>(new MyComparator());

/*Avertissement local indiquant que la conversion de type Objet → Nœud n'est pas sûre
    Type safety: The expression of type PriorityQueue needs unchecked conversion to conform to Queue<Node>
Erreur de compilation ferme dans AOJ
    rep/Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
*/

openjdk version "11.0.3" 2019-04-16

La file d'attente prioritaire peut contenir plusieurs données faisant référence au même objet

Sans surprise, cela a provoqué la mise en file d'attente d'un grand nombre des mêmes objets. Au milieu

nodes[1].d=1
nodes[3].d=13;
queue.add(nodes[1]);
queue.add(nodes[3]);

Cependant, il est mis à jour en tant que nodes [3] .d = 5; après cela. J'ai également mis cela en file d'attente et essayé de mettre en file d'attente deux types de données: {id = 3, d = 5}, {id = 3, d = 13}. Cependant, comme les deux données de la file d'attente se réfèrent au même objet «nœuds [3]», seules deux données avec id3 et une distance de 5 sont entrées. La solution elle-même est simple, et si un nœud avec le même identifiant existe dans la file d'attente, il ne doit pas être nouvellement ajouté. Mais c'est sale (j'ai recherché l'identifiant de la file d'attente dans l'instruction for). Mais il y avait le problème suivant et ce n'était pas bon après tout. Que dois-je faire si une propriété qui n'est pas utilisée pour le tri est mise en file d'attente?

PriorityQueue ne reconstruit pas la commande même si la destination de référence est mise à jour (= la commande est dans le désordre)

Même si (Problème 2) est résolu, ce sera une mauvaise réponse à cause de cela.

nodes[2].d=2;
nodes[3].d=3;
queue.add(nodes[2]);
queue.add(nodes[3]);
queue.peek();       //Si vous regardez en haut sans le retirer, les nœuds[2]
nodes[3].d=1;
queue.peek();       //C'est aussi des nœuds[2]

(Puisque la position du nœud 3 (actuellement d = 5) dans la file d'attente est la position triée par d = 13, la sélection du nœud après sélection du nœud 4 est 2 sur 3 et 7 (position de d = 8). 7 est sorti de la file d'attente par sélection) ** En d'autres termes, la file d'attente prioritaire standard ne peut pas être gérée lors de la mise à jour des propriétés à l'intérieur. ** **

Résolu comme suit.

1. nodes [] ne gère que la dernière version (dernière distance), et stocke dans la file d'attente comme objet lui-même, pas comme référence.
2. Puisque plusieurs versions de la gestion des nœuds (désactivation à la fois {id = 3, d = 5}, {id = 3, d = 13}) qui n'ont pas pu être réalisées dans (Trouble 2) sont réalisées. , Si ʻud> nodes [id] ʻest sélectionné comme u dans la file d'attente, il sera ignoré.

À ce moment-là, j'ai essayé d'utiliser ʻObject.clone () , donc une note à ce sujet Les objets peuvent être dupliqués dans des classes qui implémentent l'interface Cloneable et remplacent la méthode clone (). clone ()a une copie complète (les membres de l'objet dans l'objet à copier sont également copiés) et une copie superficielle (les membres de l'objet dans l'objet à copier sont les mêmes que l'original), et ce qui suit est une copie superficielle (cette fois, profonde est requise) Puisqu'il n'y en a pas). L'objetTreeMap` fait référence au même objet, mais cette fois il n'est pas mis à jour, il n'y a donc pas de problème.

class Node implements Cloneable{
    int id;
    int d;
    int color=0;
    TreeMap<Integer,Integer> child = new TreeMap<>();  //{id:poids}Liste adjacente de

    @Override
    protected Node clone() throws CloneNotSupportedException {
    Node  node = (Node)super.clone();
    return node;
}//Ci-dessous principal()Dans la méthode
try{
    queue.add(nodes[0].clone());
} catch (CloneNotSupportedException e){//La gestion des erreurs}

Pour une copie complète, ajoutez node.child = this.child.clone (); lors de la substitution de clone ().

Résumé

Le standard java PriorityQueue est généralement hors service lorsque le contenu est mis à jour. Si vous voulez dichstra, dupliquez l'objet avec clone () et mettez tous les objets avant la mise à jour dans la file d'attente avec priorité, et ignorez le processus lorsque vous retirez autre chose que le dernier état.