Coda priorità Java con un comparatore anonimo personalizzato

Question

Perdonami se questa è una domanda provata, ma ho qualche difficoltà a capirlo.

Attualmente ho un nodo di classe e ogni "nodo" è un quadrato in un labirinto. Sto cercando di implementare l'algoritmo A *, quindi ognuno di questi nodi avrà un membro di dati f-cost (int) all'interno di esso. Mi stavo chiedendo se c'è un modo per creare una coda di priorità di questi nodi e impostare la variabile f-cost come comparatore?

Ho esaminato esempi online, ma tutto quello che posso trovare sono le code con priorità String. Posso implementare Comparator per la classe Node? Mi permetterebbe di accedere al membro dei dati memorizzato al suo interno?

Grazie mille!

Answer 1

Assolutamente.

È possibile utilizzare un PriorityQueue sulla base di un anonimo Comparator passato al costruttore:

int initCapacity = 10; 
PriorityQueue<Node> pq = new PriorityQueue<Node>(initCapacity, new Comparator<Node>() { 
    public int compare(Node n1, Node n2) { 
     // compare n1 and n2 
    } 
}); 
// use pq as you would use any PriorityQueue 

Se la classe Node implementa già Comparable non c'è nemmeno bisogno di definire un nuovo Comparator, come quella ordine sarà usato di default. Salvo altri metodi, verrà utilizzato l'ordinamento naturale tra gli oggetti.

Answer 2

Dalle Javadocs:

Una coda di priorità illimitata sulla base di un cumulo priorità. Questa coda ordini elementi secondo un ordine specificato al tempo di costruzione, che specificato sia in base al loro ordine naturale (vedi comparabili), o secondo un comparatore

Inoltre, PriorityQueues supportano tipi di dati generici . Pertanto, se si implementa Comparable nella classe Node, è possibile creare un PriorityQueue<Node> e utilizzarlo normalmente.

In alternativa, esiste un costruttore PriorityQueue(int initialCapacity, Comparator<? super E> comparator) che accetta un comparatore come parte del costruttore PriorityQueue. Se si preferisce questo metodo, la classe del nodo non deve contenere il codice aggiuntivo necessario per l'ereditarietà di Comparable.

Answer 3

Esiste una classe PriorityQueue in java.util. È possibile utilizzarlo e utilizzare l'ordinamento naturale (Node implements Comparable) o un comparatore fornito nel costruttore (se non si desidera tale codice all'interno della classe Node). Qualsiasi classe può accedere a qualsiasi dato all'interno di un altro purché lo consenta rendendo un campo non privato (potenzialmente OOP in cattivo stato) o fornendo un metodo di accesso pubblico int getG(), pubblico int getH(), pubblico int getF() .

Answer 4

public class Node implements Comparable<Node>{ 

    public int compareTo(Node o) { 
     // your comparative function 
     return 0; 
    } 

}

se compareTo restituisce un int negativo, significa "minore", 0 significa "uguale", 1 significa "maggiore di"

che una funzione è tutto ciò che serve a essere in grado di utilizzare PriorityQueue.

MODIFICA: il confronto è l'altro modo, l'ho incasinato.-1 < | 0 = | 1> ho letto quelli da destra a sinistra per qualche motivo.