Переориентация очереди приоритетов Java при редактировании элементов
Я пытаюсь реализовать алгоритм Дейкстры для поиска кратчайших путей, используя очередь с приоритетами. На каждом шаге алгоритма я удаляю вершину с наименьшим расстоянием от приоритетной очереди, а затем обновляю расстояния для каждого из ее соседей в приоритетной очереди. Теперь я прочитал, что Приоритетная очередь в Java не будет переупорядочиваться при редактировании элементов в ней (элементов, определяющих порядок), поэтому я попытался изменить порядок, вставив и удалив фиктивную вершину. Но это, похоже, не работает, и я застрял, пытаясь понять это.
Это код для объекта вершины и компаратора
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;
}
}
Вот где я запускаю алгоритм:
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);
}
Я запустил несколько текстовых случаев, и я знаю, что очередь приоритетов не переупорядочивается правильно каждый раз, когда я прохожу и обновляю расстояния для вершин, но я не знаю почему. Я где-то сделал ошибку?
7 ответов
Как вы обнаружили, очередь с приоритетами не обрабатывает все элементы всякий раз, когда элемент добавляется или удаляется. Это было бы слишком дорого (помните, что n log n нижняя граница для сортировки сравнения), в то время как любая реализация очереди с разумным приоритетом (включая PriorityQueue) обещает добавить / удалить узлы в O(log n).
На самом деле, он вообще не сортирует свои элементы (поэтому его итератор не может обещать итерировать элементы в отсортированном порядке).
PriorityQueue не предлагает API для информирования его об измененном узле, поскольку это потребовало бы от него обеспечения эффективного поиска узла, который не поддерживается его базовым алгоритмом. Реализация приоритетной очереди довольно сложна. Статья в Википедии о PriorityQueues может послужить хорошей отправной точкой для прочтения об этом. Я не уверен, что такая реализация будет быстрее, хотя.
Простая идея - удалить, а затем добавить измененный узел. Не делай этого как remove() взять на себя). Вместо этого вставьте другую запись для того же узла в PriorityQueue и игнорируйте дубликаты при опросе очереди, то есть сделайте что-то вроде:
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());
}
}
}
Изменить: не рекомендуется изменять приоритеты элементов в PQ, следовательно, необходимо вставить Step с вместо Node s.
Вам придется удалить и заново вставить каждый элемент, который редактируется. (фактический элемент, а не фиктивный!). поэтому каждый раз, когда вы обновляете distancesнеобходимо удалить и добавить элементы, на которые повлияло измененное блюдо.
Насколько я знаю, это не уникально для Java, но каждая приоритетная очередь, которая выполняется в O(logn) для всех операций, должна работать таким образом.
Недостаток Java PriorityQueue в том, что remove(Object) требуется время O(n), что приводит к времени O(n), если вы хотите обновить приоритеты, удалив и снова добавив элементы. Однако это можно сделать за время O (log (n)). Поскольку я не смог найти работающую реализацию через Google, я попытался реализовать ее самостоятельно (хотя в Kotlin, поскольку я действительно предпочитаю этот язык Java), используя TreeSet, Кажется, это работает, и должен иметь O (log (n)) для добавления / обновления / удаления (обновление выполняется через 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)
}
}
Вы можете избежать обновления элементов в очереди, просто пометив каждый узел как посещенный = false по умолчанию и добавляя новые элементы в очередь по мере продвижения.
Затем извлеките узел из очереди и обработайте его, только если он не был посещен ранее.
Алгоритм Дейкстры гарантирует, что каждый узел посещается только один раз, поэтому, даже если у вас могут быть устаревшие узлы в очереди, вы их никогда не обработаете.
Также, вероятно, будет проще, если вы отделите внутреннюю часть алгоритма от структуры данных графа.
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));
}
}
}
}
}
Проблема в том, что вы обновляете distances массив, но не соответствующая запись в queue, Чтобы обновить соответствующие объекты в очереди, необходимо удалить, а затем добавить.
Я решаю эту проблему, разделив свой процесс на временные интервалы (планировщик времени подойдет) и расширив родной PriorityQueue. Поэтому я реализую метод уведомления, где ключом этого метода является следующий код:
// 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());
}
}
Надеюсь, это помогло.
Я реализовал адаптивный MinHeap, который поддерживает переупорядочивание (O(nlogn)) при обновлении приоритета объектов, написанный на Python.
class Node:
"""
Model an object in Heap.
"""
def __init__(self, key, val, i=-1) -> None:
self.key = key # object ID
self.val = val # object priority
self.i = i # index in heap array
class AdaptiveMinHeap:
"""
Heap for objects. Support reorderining when objects' priority are updated.
"""
def __init__(self) -> None:
self.hp = {0: Node(-1, -1, 0)} # Use dict to simulate list (key as the index) to support efficient reordering.
self.d = dict()
def __len__(self):
return len(self.hp)-1
def _swap(self, anode, bnode):
d = self.d
anode.key, bnode.key = bnode.key, anode.key
anode.val, bnode.val = bnode.val, anode.val
d[anode.key] = anode
d[bnode.key] = bnode
def _swim(self, i):
hp = self.hp
while i//2 > 0 and hp[i].val < hp[i//2].val:
self._swap(hp[i], hp[i//2])
i = i//2
def _sink(self, i):
hp = self.hp
while i*2 < len(hp):
if i*2 + 1 >= len(hp) or hp[i*2+1].val >= hp[i*2].val:
min_child = i*2
else:
min_child = i*2+1
if hp[min_child].val < hp[i].val:
self._swap(hp[min_child], hp[i])
i = min_child
def push(self, key, val):
hp = self.hp
d = self.d
if key in d:
self.remove(key)
node = Node(key, val, len(hp))
d[key] = node
hp[node.i] = node
self._swim(node.i)
def pop(self):
hp = self.hp
if len(hp) > 1:
return self.remove(hp[1].key)
def remove(self, key):
hp = self.hp
d = self.d
node = d[key]
self._swap(hp[node.i], hp[len(hp)-1])
hp.pop(len(hp)-1)
self._sink(node.i)
return d.pop(key)
hp = AdaptiveMinHeap()
hp.push(1, 40)
hp.push(4, 8900)
hp.push(2, 500)
hp.push(3, 1075)
hp.push(1, 1)
for _ in range(len(hp)):
poped = hp.pop()
print(poped.key, poped.val)
# 1
# 500
# 1075
# 8900