PriorityQueue, wo ich Probleme mit der Dyxtra-Methode unter Verwendung einer benachbarten Liste (Java) hatte.

Wettbewerbsfähiges Programmieren, an das ich zu denken begann, wird zu einer regelmäßigen Praxis.

Was ich gelernt habe

Verwendung der Prioritätswarteschlange
Verwendung der Comparator-Schnittstelle
Verwendung der klonbaren Schnittstelle

Probleme mit den oben genannten und deren Lösungen.

Was ich machen wollte

Ich habe versucht, [ALDS Minimum Route Tree Problem C] zu lösen (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_C). Dyxtra-Methode unter Verwendung der nebenstehenden Liste.

Bei einem Testfall wie dem im Bild unten gibt jeder Knoten beispielsweise die kürzeste Entfernung aus, die vom Knoten 0 zu erreichen ist. 0 ist der Abstand 0, 1 ist der Abstand 1, 3 ist der Abstand 5 und so weiter.

Verfahren

Initialisieren Sie 0 als gesuchten Knoten in einem Abstand von 0. Eine Schleife, die aus den gesuchten Knoten nach dem nächsten nicht gesuchten Knoten sucht. Wenn bereits ein nicht durchsuchter Knoten durchsucht wurde, kann sich der kürzeste Abstand des benachbarten Knotens ändern. Daher wird die Suche durchgeführt, während die Entfernung jedes Knotens aktualisiert wird. Im Falle eines Bildes wird es in der Reihenfolge 0 → 1 → 2 → 5 → 4 → 3 → 6 → 7 → 8 gesucht, zum Beispiel wird 3 als Abstand 13 (nach 0 Suche) → 5 (nach 4 Suche) aktualisiert. ..

Definieren Sie die Node-Klasse mit den folgenden Eigenschaften

class Node{ int id; //Knotennummer int d=INFTY; //Kürzeste Entfernung vom Knoten 0 ← Suchen, während dies aktualisiert wird int color=0; //Anfangswert 0,Wenn bereits gesucht 1 TreeMap<Integer,Integer> child =new TreeMap<>(); //{id:Seitengewicht}Liste benachbarter Knoten im Format }

 1. Definieren Sie die folgenden Variablen in der main () -Methode
 --`queue`: Prioritätswarteschlange, in der Knotenobjekte in der Reihenfolge d gespeichert werden ** (Problem 1) **
 --`nodes [] `: Ein Array, das jeden Knoten im neuesten Status speichert
 1. Stellen Sie den Abstand von 0 auf 0 ein (`node [0] .d = 0;`) und stellen Sie ihn in die Prioritätswarteschlange. Derzeit enthält "Warteschlange" nur 0 Knoten.



 1. Wählen Sie mit `u = queue.poll ()`. Lassen Sie sich suchen und aktualisieren, wenn das `d` des benachbarten Knotens aktualisiert werden kann. ** (Problem 2) **
 Im Fall des Bildes ist das erste Update wie folgt.

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

Stellen Sie einen benachbarten Knoten (nicht durchsucht) in die Prioritätswarteschlange. Zu diesem Zeitpunkt werden zum ersten Mal die Verweise auf "Knoten [i](i = 1,3)" in aufsteigender Reihenfolge von "d" in der "Warteschlange" angeordnet.
Extrahieren Sie den Knoten mit dem kleineren "d" aus der "Warteschlange" und wählen Sie ihn aus. Wiederholen Sie danach die Schritte 4 bis 6. ** (Problem 3) **

Warum bist du in Schwierigkeiten geraten?

(Problem 1) Ich war nicht gut darin, Objekte in PriorityQueue einzufügen, und erhielt eine Warnung (es funktionierte lokal, aber ein Online-Richter hat einen Kompilierungsfehler erhalten).
(Problem 2) Die Prioritätswarteschlange kann mehrere Daten enthalten, die sich auf dasselbe Objekt beziehen
** (Problem 3) PriorityQueue rekonstruiert die Bestellung nicht, selbst wenn das Referenzziel aktualisiert wird (= die Bestellung ist nicht in Ordnung) **

↓ Details

Ich konnte keine Objekte in die PriorityQueue einfügen und erhielt eine Warnung (es funktionierte lokal, aber ich bekam einen Kompilierungsfehler bei einem Online-Richter).

Folgendes ist richtig. Dadurch wird "Knoten" am Anfang der Warteschlange in aufsteigender Reihenfolge von "d" gesetzt.

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;
        }
    }
}
//Unten main()In der Methode
Queue<Node> queue = new PriorityQueue<>(new MyComparator());

Ich kannte den Lambda-Ausdruck erst vor einiger Zeit. Als ich nach einer herkömmlichen Schnittstellenimplementierung suchte, schlug ich fehl, weil es viele Websites gab, die keine Generika verwendeten, wie unten gezeigt.

class MyComparator implements Comparator {
    public int compare (Object o1, Object o2){//wird bearbeitet}
}//Unten main()In der Methode
Queue<Node> queue = new PriorityQueue<>(new MyComparator());

/*Lokale Warnung, dass die Konvertierung von Objekt → Knotentyp nicht sicher ist
    Type safety: The expression of type PriorityQueue needs unchecked conversion to conform to Queue<Node>
Fester Kompilierungsfehler in AOJ
    rep/Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
*/

openjdk version "11.0.3" 2019-04-16

Die Prioritätswarteschlange kann mehrere Daten enthalten, die sich auf dasselbe Objekt beziehen

Es ist nicht überraschend, dass eine große Anzahl derselben Objekte in die Warteschlange gestellt wurde. Mitten drin

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

Es wird jedoch danach als node [3] .d = 5; aktualisiert. Ich habe dies auch in die Warteschlange gestellt und versucht, zwei Datentypen in die Warteschlange zu stellen: {id = 3, d = 5}, {id = 3, d = 13}. Da sich die beiden Daten in der Warteschlange jedoch auf dasselbe Objekt "Knoten [3]" beziehen, werden nur zwei Daten mit der ID3 und einem Abstand von 5 eingegeben. Die Lösung selbst ist einfach. Wenn ein Knoten mit derselben ID in der Warteschlange vorhanden ist, sollte er nicht neu hinzugefügt werden. Aber es ist schmutzig (ich habe die ID der Warteschlange in der for-Anweisung nachgeschlagen). Aber es gab das folgende Problem und das war doch nicht gut. Was kann ich tun, wenn eine Eigenschaft, die nicht zum Sortieren verwendet wird, in die Warteschlange gestellt wird?

PriorityQueue rekonstruiert die Bestellung nicht, selbst wenn das Referenzziel aktualisiert wird (= die Bestellung ist nicht in Ordnung)

Selbst wenn (Problem 2) behoben ist, ist dies aus diesem Grund eine falsche Antwort.

nodes[2].d=2;
nodes[3].d=3;
queue.add(nodes[2]);
queue.add(nodes[3]);
queue.peek();       //Wenn Sie nach oben schauen, ohne es herauszunehmen, Knoten[2]
nodes[3].d=1;
queue.peek();       //Dies ist auch Knoten[2]

(Da die Position von Knoten 3 (derzeit d = 5) in der Warteschlange die nach d = 13 sortierte Position ist, beträgt die Knotenauswahl nach Auswahl von Knoten 4 2 von 3 und 7 (Position von d = 8). 7 wird durch Auswahl aus der Warteschlange genommen) ** Mit anderen Worten, die Standardprioritätswarteschlange kann beim Aktualisieren der darin enthaltenen Eigenschaften nicht behandelt werden. ** ** **

Wie folgt gelöst.

node [] verwaltet nur die neueste Version (letzte Entfernung) und speichert sie in der Warteschlange als Objekt selbst, nicht als Referenz.
Da mehrere Versionen der Knotenverwaltung (Löschen von {id = 3, d = 5} und {id = 3, d = 13}) realisiert werden, die in (Trouble 2) nicht realisiert werden konnten. , Wenn ud> node [id] als u aus der Warteschlange ausgewählt ist, wird es ignoriert.

Zu dieser Zeit habe ich versucht, "Object.clone ()" zu verwenden, also einen Hinweis dazu Objekte können in Klassen dupliziert werden, die die Cloneable-Schnittstelle implementieren und die clone () -Methode überschreiben. clone () hat eine tiefe Kopie (die Objektelemente in dem zu kopierenden Objekt werden ebenfalls kopiert) und eine flache Kopie (die Objektelemente in dem zu kopierenden Objekt sind die gleichen wie das Original), und das Folgende ist eine flache Kopie (diesmal ist tief erforderlich). Da gibt es keine). Das TreeMap-Objekt bezieht sich auf dasselbe Objekt, wird jedoch dieses Mal nicht aktualisiert, sodass kein Problem vorliegt.

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

    @Override
    protected Node clone() throws CloneNotSupportedException {
    Node  node = (Node)super.clone();
    return node;
}//Unten main()In der Methode
try{
    queue.add(nodes[0].clone());
} catch (CloneNotSupportedException e){//Fehlerbehandlung}

Fügen Sie für eine tiefe Kopie "node.child = this.child.clone ()" hinzu, wenn Sie "clone ()" überschreiben.

Zusammenfassung

Der Java-Standard PriorityQueue ist im Allgemeinen nicht in Ordnung, wenn der Inhalt aktualisiert wird. Wenn Sie dichstra möchten, duplizieren Sie das Objekt mit clone () und stellen Sie alle Objekte vor der Aktualisierung mit Priorität in die Warteschlange. Überspringen Sie den Vorgang, wenn Sie etwas anderes als den neuesten Status entfernen.