java - prioridad - ejemplo de colas

Reordenamiento de la cola de prioridad de Java al editar elementos

Question

Estoy intentando implementar el algoritmo de Dijkstra para encontrar rutas más cortas usando una cola de prioridad. En cada paso del algoritmo, elimino el vértice con la distancia más corta de la cola de prioridad y luego actualizo las distancias para cada uno de sus vecinos en la cola de prioridad. Ahora leo que una Cola de prioridad en Java no se reordenará cuando edites los elementos en ella (los elementos que determinan el orden), así que traté de forzarla a reordenar insertando y eliminando un vértice ficticio. Pero esto no parece estar funcionando, y estoy atascado tratando de resolverlo.

Este es el código para el objeto de vértice y el comparador.

class vertex {
    int v, d;
    public vertex(int num, int dis) {
        v=num;
        d=dis;
    }
}

class VertexComparator implements Comparator {
    public int compare (Object a, Object b) {
        vertex v1 = (vertex)a;
        vertex v2 = (vertex)b;
        return v1.d-v2.d;
    }
 }

Aquí es donde ejecuto el algoritmo:

    int[] distances=new int[p];
    Comparator<vertex> comparator = new VertexComparator();
    PriorityQueue<vertex> queue = new PriorityQueue<vertex>(p, comparator);
    for(int i=0; i<p; i++) {
        if(i!=v) {
            distances[i]=MAX;
        }
        else {
            distances[i]=0;
        }
        queue.add(new vertex(i, distances[i]));
    }
    // run dijkstra
    for(int i=0; i<p; i++) {
        vertex cur=queue.poll();
        Iterator itr = queue.iterator();
        while(itr.hasNext()) {
            vertex test = (vertex)(itr.next());
            if(graph[cur.v][test.v]!=-1) {
                test.d=Math.min(test.d, cur.d+graph[cur.v][test.v]);
                distances[test.v]=test.d;
            }
        }
        // force the PQ to resort by adding and then removing a dummy vertex
        vertex resort = new vertex(-1, -1);
        queue.add(resort);
        queue.remove(resort);
    }

He ejecutado varios casos de texto y sé que la cola de prioridad no se reordena correctamente cada vez que paso y actualizo las distancias para los vértices, pero no sé por qué. ¿Cometí un error en alguna parte?

Answer 1

Como descubrió, una cola de prioridad no recurre a todos los elementos cada vez que se agrega o elimina un elemento. Hacer eso sería demasiado costoso (recuerde el n registro n el límite inferior para la ordenación de comparación), mientras que cualquier implementación de cola de prioridad razonable (incluida PriorityQueue ) promete agregar / eliminar nodos en O (log n).

De hecho, no clasifica sus elementos en absoluto (por eso su iterador no puede prometer iterar elementos en orden ordenado).

PriorityQueue no ofrece una api para informarle acerca de un nodo cambiado, ya que eso requeriría que proporcione una búsqueda de nodos eficiente, que su algoritmo subyacente no admite. Implementar una cola de prioridad que lo hace es bastante complicado. El artículo de Wikipedia sobre PriorityQueues podría ser un buen punto de partida para leer sobre eso. Sin embargo, no estoy seguro de que tal implementación fuera más rápida.

Una idea sencilla es eliminar y luego agregar el nodo modificado. No hagas eso ya que remove() toma O (n). En su lugar, inserte otra entrada para el mismo nodo en PriorityQueue e ignore los duplicados al sondear la cola, es decir, haga algo como:

PriorityQueue<Step> queue = new PriorityQueue();

void findShortestPath(Node start) {
    start.distance = 0;
    queue.addAll(start.steps());

    Step step;
    while ((step = queue.poll()) != null) {
        Node node = step.target;
        if (!node.reached) {
            node.reached = true;
            node.distance = step.distance;
            queue.addAll(node.steps());
        }
    }

}

Edición: no es recomendable cambiar las prioridades de los elementos en la PQ, por lo tanto, es necesario insertar los Step s en lugar de los Node .

Answer 2

El problema es que actualiza la matriz de distances , pero no la entrada correspondiente en la queue . Para actualizar los objetos apropiados en la cola, debe eliminar y luego agregar.

Answer 3

La desventaja de PriorityQueue de Java es que remove(Object) requiere O (n) tiempo, lo que resulta en O (n) tiempo si desea actualizar las prioridades al eliminar y agregar elementos nuevamente. Sin embargo, se puede hacer en el tiempo O (log (n)). Como no pude encontrar una implementación operativa a través de Google, intenté implementarla yo mismo (aunque en Kotlin, ya que realmente prefiero ese lenguaje a Java) utilizando TreeSet . Esto parece funcionar, y debería tener O (log (n)) para agregar / actualizar / eliminar (la actualización se realiza mediante add ):

// update priority by adding element again (old occurrence is removed automatically)
class DynamicPriorityQueue<T>(isMaxQueue: Boolean = false) {

    private class MyComparator<A>(val queue: DynamicPriorityQueue<A>, isMaxQueue: Boolean) : Comparator<A> {
        val sign = if (isMaxQueue) -1 else 1

        override fun compare(o1: A, o2: A): Int {
            if (o1 == o2)
                return 0
            if (queue.priorities[o2]!! - queue.priorities[o1]!! < 0)
                return sign
            return -sign
        }

    }

    private val priorities = HashMap<T, Double>()
    private val treeSet = TreeSet<T>(MyComparator(this, isMaxQueue))

    val size: Int
        get() = treeSet.size

    fun isEmpty() = (size == 0)

    fun add(newElement: T, priority: Double) {
        if (newElement in priorities)
            treeSet.remove(newElement)
        priorities[newElement] = priority
        treeSet.add(newElement)
    }

    fun remove(element: T) {
        treeSet.remove(element)
        priorities.remove(element)
    }

    fun getPriorityOf(element: T): Double {
        return priorities[element]!!
    }


    fun first(): T = treeSet.first()
    fun poll(): T {
        val res = treeSet.pollFirst()
        priorities.remove(res)
        return res
    }

    fun pollWithPriority(): Pair<T, Double> {
        val res = treeSet.pollFirst()
        val priority = priorities[res]!!
        priorities.remove(res)
        return Pair(res, priority)
    }

}

Answer 4

Puede evitar actualizar los elementos en la cola simplemente marcando cada nodo como visitado = falso de manera predeterminada y agregando nuevos elementos a la cola a medida que avanza.

Luego saque un nodo de la cola y proceselo solo si no fue visitado antes.

El algoritmo de Dijkstra garantiza que cada nodo se visite solo una vez, por lo que incluso si tiene nodos obsoletos en la cola, nunca los procesará realmente.

También es probable que sea más fácil si separa los elementos internos del algoritmo de la estructura de datos del gráfico.

public void dijkstra(Node source) throws Exception{
    PriorityQueue q = new PriorityQueue();
    source.work.distance = 0;
    q.add(new DijkstraHeapItem(source));

    while(!q.isEmpty()){
        Node n = ((DijkstraHeapItem)q.remove()).node;
        Work w = n.work;

        if(!w.visited){
            w.visited = true;

            Iterator<Edge> adiacents = n.getEdgesIterator();
            while(adiacents.hasNext()){
                Edge e = adiacents.next();
                if(e.weight<0) throw new Exception("Negative weight!!");
                Integer relaxed = e.weight + w.distance;

                Node t = e.to;
                if (t.work.previous == null || t.work.distance > relaxed){
                    t.work.distance = relaxed;
                    t.work.previous = n;
                    q.add(new DijkstraHeapItem(t));
                }
            }
        }
    }
}

Answer 5

Resuelvo este problema al dividir mi proceso en timeSlots (Un programador de tiempo estará bien) y extender la PriorityQueue nativa. Entonces implemento un método de notificación donde la clave de este método es el siguiente código:

// If queue has one or less elements, then it shouldn''t need an ordering
// procedure
if (size() > 1)
{
    // holds the current size, as during this process the size will
    // be vary
    int tmpSize = size();
    for (int i = 1; i < tmpSize; i++)
    {
        add(poll());
    }
}

Espero que haya ayudado.

Answer 6

Tendrá que eliminar y volver a insertar cada elemento editado. (el elemento real, y no uno ficticio!). por lo tanto, cada vez que actualice distances , deberá eliminar y agregar los elementos que fueron afectados por la entrada modificada.

Por lo que sé, esto no es exclusivo de Java, pero todas las colas de prioridad que se ejecutan en O (logn) para todas las operaciones, tienen que funcionar de esta manera.