Pytanie Kolejność priorytetów Java kolejki podczas edycji elementów


Próbuję zaimplementować algorytm Dijkstry do znajdowania najkrótszych ścieżek za pomocą kolejki priorytetowej. W każdym kroku algorytmu usuwam wierzchołek o najkrótszej odległości od kolejki priorytetów, a następnie aktualizuję odległości dla każdego z jego sąsiadów w kolejce priorytetów. Teraz czytam, że Kolejka Priorytetów w Javie nie zmieni kolejności po edycji elementów w niej (elementy określające kolejność), więc starałem się wymusić zmianę kolejności poprzez wstawienie i usunięcie fałszywego wierzchołka. Ale wydaje się, że to nie działa i utknąłem, próbując to rozgryźć.

Jest to kod dla obiektu wierzchołka i komparatora

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;
    }
 }

Oto gdzie uruchamiam algorytm:

    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);
    }

Uruchomiłem kilka przypadków tekstowych i wiem, że kolejka priorytetów nie zmienia kolejności poprawnie za każdym razem, gdy przechodzę i aktualizuję odległości dla wierzchołków, ale nie wiem dlaczego. Czy gdzieś popełniłem błąd?


21
2017-08-05 07:05


pochodzenie


możliwy duplikat Aktualizowanie Java PriorityQueue, gdy jego elementy zmieniają priorytet - Raedwald


Odpowiedzi:


Jak odkryłeś, kolejka priorytetowa nie ucieka się do wszystkich elementów po dodaniu lub usunięciu elementu. Wykonanie tego byłoby zbyt kosztowne (pamiętaj, że n log n dolna granica dla sortowania porównawczego), a każda rozsądna implementacja kolejki priorytetów (w tym PriorityQueue) obiecuje dodać / usunąć węzły w O (log n).

W rzeczywistości nie sortuje ona swoich elementów (dlatego jego iterator nie może obiecać iteracji elementów w uporządkowanej kolejności).

PriorityQueue nie oferuje api do informowania go o zmienionym węźle, ponieważ wymagałoby to zapewnienia wydajnego wyszukiwania węzłów, którego algorytm nie obsługuje. Wdrożenie kolejki priorytetowej, która jest dość zaangażowana. The Artykuł Wikipedii o PriorityQueues może być dobrym punktem wyjścia do czytania o tym. Nie jestem jednak pewien, czy taka implementacja byłaby szybsza.

Prostym pomysłem jest usunięcie, a następnie dodanie zmienionego węzła. Zrobić nie zrób to jako remove() przyjmuje). Zamiast tego wstaw inny wpis dla tego samego węzła do klasy PriorityQueue i zignoruj ​​duplikaty podczas odpytywania kolejki, tj. Wykonaj coś takiego:

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());
        }
    }

}

Edycja: Nie zaleca się zmiany priorytetów elementów w PQ, stąd potrzeba wstawienia Steps zamiast Nodes.


19
2017-08-05 07:50



Świetnie, miałem ten sam pomysł, ale nie zmieniałby to czasu działania algorytmu z O (m log n) na O (m log m). Ponieważ sterta będzie teraz zawierała zduplikowane elementy prawie równe liczbie krawędzi na wykresie O (m). Myślę, że to nie będzie najlepsze rozwiązanie. - Samer Makary
Wykresy odnajdywania trasy są zazwyczaj płaskie i dlatego mają stałą średnią liczbę sąsiadów. Oznacza to, że wielkość PQ wzrośnie o stały współczynnik, a jego wysokość o stałe przesunięcie. Nie powinno to mieć większego wpływu na środowisko uruchomieniowe. Z drugiej strony, wydajna modyfikacja węzłów wymaga, aby wywołujący miał uchwyt do każdego węzła. W języku Java można to zrobić tylko poprzez odwołanie do obiektu, co wymaga od klasy PriorityQueue przechowywania obiektu węzła dla każdego wpisu. To z kolei zajmuje stały czynnik więcej pamięci niż kolejka priorytetowa, która koduje jego strukturę przy użyciu wskaźników tablicowych. - meriton
Dlatego jest naprawdę mroczna, która implementacja byłaby szybsza. - meriton


będziesz musiał usunąć i ponownie wstawić każdy element, który jest edytowany. (rzeczywisty element, a nie fikcyjny!). więc za każdym razem, gdy aktualizujesz distances, musisz usunąć i dodać elementy, na które wpłynęło zmienione hasło.

O ile mi wiadomo, nie jest to unikalne dla Javy, ale każda kolejka priorytetowa, która działa w O (logn) dla wszystkich operacji, musi działać w ten sposób.


4
2017-08-05 07:09



remove przyjmuje O (n) ... - meriton
remove(Object o) nie musi być O (n). To tylko biblioteka Java używa naiwnej metody O (n) do zlokalizowania elementu do usunięcia. Jeśli zamiast tego użyjesz struktury indeksującej, takiej jak mapa do przechowywania pozycji elementu w stercie, możesz to zrobić remove w O (log (n)). - lcn
remove (Object) weź O (n), ale remove () i dodaj take O (log (N)) docs.oracle.com/javase/7/docs/api/java/util/... - Shrey


Wada Java PriorityQueue czy to remove(Object) Wymaga czasu O (n), powodującego czas O (n), jeśli chcesz zaktualizować priorytety, usuwając i dodając elementy ponownie. Można to zrobić jednak w czasie O (log (n)). Ponieważ nie byłem w stanie znaleźć działającej implementacji za pośrednictwem Google, sam próbowałam ją wdrożyć (w Kotlin jednak, ponieważ ja naprawdę wolę ten język od Javy) TreeSet. To wydaje się działać i powinno mieć O (log (n)) do dodawania / aktualizowania / usuwania (aktualizacja odbywa się za pośrednictwem 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)
    }

}

3
2018-03-23 13:04





Możesz uniknąć aktualizacji elementów w kolejce, zaznaczając każdy węzeł jako visited = false domyślnie i dodawanie nowych elementów do kolejki.

Następnie poprowadź węzeł z kolejki i przetwórz go, tylko jeśli wcześniej nie był odwiedzany.

Algorytm Dijkstry gwarantuje, że każdy węzeł jest odwiedzany tylko raz, więc nawet jeśli możesz mieć nieaktualne węzły w kolejce, nigdy ich nie przetworzysz.

Łatwiej też będzie, jeśli oddzielisz wewnętrzne algorytmy od struktury danych wykresu.

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));
                }
            }
        }
    }
}

2
2017-08-05 08:19



nie rozumiem - jeśli wyłączysz () węzeł z kolejki, wywołasz zmianę kolejności kolejki, tym samym pokonując cel ustawienia .visited = true? - jasonk


Problem polega na tym, że aktualizujesz distances array, ale nie odpowiadający wpis w queue. Aby zaktualizować odpowiednie obiekty w kolejce, musisz usunąć, a następnie dodać.


0
2017-08-05 07:10



remove przyjmuje O (n) ... - meriton


Rozwiązuję ten problem dzieląc mój proces na timeSlots (Scheduler czasu będzie w porządku) i rozszerzając natywny PriorityQueue. Dlatego zaimplementowałem metodę notify, w której kluczem tej metody jest poniższy kod:

// 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());
    }
}

Mam nadzieję, że pomogło.


0
2018-01-30 13:24