Как я могу использовать двоичную кучу в алгоритме Дейкстры?
Я пишу код алгоритма dijkstra, для части, где мы должны найти узел с минимальным расстоянием от используемого в данный момент узла, я использую массив и перебираю его полностью, чтобы вычислить узел.
Эта часть может быть заменена двоичной кучей, и мы можем вычислить узел за O(1) времени, но мы также обновим расстояние до узла в дальнейших итерациях. Как я включу эту кучу?
В случае массива все, что мне нужно сделать, это перейти к индексу (ith -1) и обновить значение этого узла, но то же самое нельзя сделать в двоичной куче, мне придется выполнить полный поиск, чтобы вычислить из позиции узла, а затем обновить его.
Как обойти эту проблему?
8 ответов
Это всего лишь некоторая информация, которую я нашел во время занятий в классе, которой я поделился со своими одноклассниками. Я думал, что мне будет проще найти его, и я оставил этот пост, чтобы я мог ответить на него, когда нашел решение.
Примечание. В этом примере я предполагаю, что вершины вашего графа имеют идентификатор, чтобы отслеживать, какой есть какой. Это может быть имя, число, что угодно, просто убедитесь, что вы изменили тип в struct ниже. Если у вас нет таких средств различения, вы можете использовать указатели на вершины и сравнивать их указываемые адреса.
Проблема, с которой вы здесь столкнулись, заключается в том, что в алгоритме Дейкстры нас просят сохранить вершины графов и их ключи в этой приоритетной очереди, а затем обновить ключи тех, которые остались в очереди. Но... Структуры данных кучи не могут попасть ни в один конкретный узел, который не является минимальным или последним узлом!
Лучшее, что мы могли бы сделать, - это пройти через кучу за O(n) время, чтобы найти его, затем обновить его ключ и всплыть в O(Logn). Это делает обновление всех вершин O(n) для каждого отдельного ребра, что делает нашу реализацию Dijkstra O(mn) намного хуже, чем оптимальное O (mLogn).
BLEH! Там должен быть лучший путь!
Итак, нам нужно реализовать не совсем стандартную очередь приоритетов на основе минимальной кучи. Нам нужна еще одна операция, чем стандартные операции 4 pq:
- Пустой
- добавлять
- PopMin
- PeekMin
- и DecreaseKey
Для того, чтобы уменьшить ключ, нам нужно:
- найти конкретную вершину внутри кучи
- снизить значение ключа
- "куча" или "пузырек" вершина
По сути, поскольку вы (я предполагаю, что это было реализовано где-то за последние 4 месяца), вероятно, собираетесь использовать реализацию кучи на основе массива, это означает, что нам нужна куча, чтобы отслеживать каждую вершину и ее индекс в массиве для того, чтобы эта операция была возможной.
Разработка struct как:(C++)
struct VertLocInHeap
{
int vertex_id;
int index_in_heap;
};
позволит вам отследить это, но сохранение этих данных в массиве все равно даст вам O(n) время для поиска вершины в куче. Нет улучшения сложности, и это сложнее, чем раньше. >.<
Мое предложение(если целью является оптимизация):
- Сохраните эту информацию в бинарном дереве поиска, ключевым значением которого является `vertex_id`
- выполнить бинарный поиск, чтобы найти местоположение вершины в куче в O (Logn)
- используйте индекс, чтобы получить доступ к вершине и обновить ее ключ в O(1)
- раздувать вершину в O (Logn)
Я на самом деле использовалstd::map объявлен как:
std::map m_locations; в куче вместо использования структуры. Первый параметр (Key) - это vertex_id, а второй параметр (Value) - это индекс в массиве кучи. поскольку std::map гарантирует поиск O (Logn), это прекрасно работает "из коробки". Затем, когда вы вставляете или всплываете, вы просто m_locations[vertexID] = newLocationInHeap;
Шальные деньги.
Анализ:
Вверху: теперь у нас есть O (Logn) для нахождения любой данной вершины в pq. Для всплытия мы делаем O(Log(n)) движений, для каждого свопа делаем O(Log(n)) поиск в карте индексов массива, что приводит к O(Log^2(n) операции для пузыря -до.
Итак, у нас есть операция Log (n) + Log ^ 2 (n) = O(Log^2(n)) для обновления значений ключей в куче для одного ребра. Это заставляет наш Дейкстра Алг взять O(mLog^2(n)). Это довольно близко к теоретическому оптимуму, по крайней мере, так близко, как я могу его получить. Потрясающий опоссум!
Недостаток: мы храним буквально вдвое больше информации в памяти для кучи. Это "современная" проблема? На самом деле, нет; мой дески может хранить более 8 миллиардов целых чисел, и многие современные компьютеры имеют как минимум 8 ГБ ОЗУ; Тем не менее, это все еще фактор. Если вы выполнили эту реализацию с графиком из 4 миллиардов вершин, что может случиться гораздо чаще, чем вы думаете, то это вызовет проблему. Кроме того, все эти дополнительные операции чтения / записи, которые могут не повлиять на сложность анализа, могут все еще занимать время на некоторых машинах, особенно если информация хранится извне.
Я надеюсь, что это поможет кому-то в будущем, потому что у меня был черт времени, чтобы найти всю эту информацию, а затем сложить кусочки, которые я получил здесь, там и повсюду вместе, чтобы сформировать это. Я обвиняю интернет и недостаток сна.
Другое решение - "отложенное удаление". Вместо операции "уменьшить клавишу" вы просто вставляете узел еще раз в кучу с новым приоритетом. Итак, в куче будет еще одна копия узла. Но этот узел будет выше в куче, чем любая предыдущая копия. Затем при получении следующего минимального узла вы можете просто проверить, принят ли узел уже. Если это так, то просто пропустите цикл и продолжайте (отложенное удаление).
Это немного хуже производительность / более высокое использование памяти из-за копий внутри кучи. Но он все еще ограничен (числом соединений) и может быть быстрее, чем другие реализации для некоторых размеров проблем.
Я бы сделал это, используя хеш-таблицу в дополнение к массиву Min-Heap.
Хеш-таблица имеет ключи, которые хеш-кодируются, чтобы быть объектами узлов, и значения, которые являются индексами того, где эти узлы находятся в массиве минимальной кучи.
Затем каждый раз, когда вы перемещаете что-то в мини-кучу, вам просто нужно соответствующим образом обновить хэш-таблицу. Поскольку не более 2 элементов будут перемещаться за одну операцию в минимальной куче (то есть они обмениваются), а наша цена за ход составляет O(1) для обновления хеш-таблицы, то мы не повредим асимптотическую границу операции мини-кучи. Например, minHeapify - это O(lgn). Мы просто добавили 2 операции O(1) хеш-таблицы на операцию minHeapify. Следовательно, общая сложность все еще составляет O(lgn).
Имейте в виду, что для отслеживания необходимо изменить любой метод, который перемещает ваши узлы в минимальной куче! Например, minHeapify() требует модификации, которая выглядит следующим образом с использованием Java:
Nodes[] nodes;
Map<Node, int> indexMap = new HashMap<>();
private minHeapify(Node[] nodes,int i) {
int smallest;
l = 2*i; // left child index
r = 2*i + 1; // right child index
if(l <= heapSize && nodes[l].getTime() < nodes[i].getTime()) {
smallest = l;
}
else {
smallest = i;
}
if(r <= heapSize && nodes[r].getTime() < nodes[smallest].getTime()) {
smallest = r;
}
if(smallest != i) {
temp = nodes[smallest];
nodes[smallest] = nodes[i];
nodes[i] = temp;
indexMap.put(nodes[smallest],i); // Added index tracking in O(1)
indexMap.put(nodes[i], smallest); // Added index tracking in O(1)
minHeapify(nodes,smallest);
}
}
buildMinHeap, heapExtract должен зависеть от minHeapify, чтобы он был в основном фиксированным, но вам также необходимо удалить извлеченный ключ из хеш-таблицы. Вам также нужно будет изменить lowerKey, чтобы отслеживать эти изменения. Как только это исправлено, вставка также должна быть исправлена, так как она должна использовать метод lowerKey. Это должно охватывать все ваши базы, и вы не будете изменять асимптотические границы вашего алгоритма, и вы все равно сможете продолжать использовать кучу для своей приоритетной очереди.
Обратите внимание, что минимальная куча Фибоначчи на самом деле предпочтительнее стандартной минимальной кучи в этой реализации, но это совершенно иная червь.
Проблема, с которой я столкнулся при использовании любой формы кучи, заключается в том, что вам нужно изменить порядок узлов в куче. Чтобы сделать это, вы должны будете выталкивать все из кучи, пока не найдете нужный вам узел, затем изменить вес и подтолкнуть его обратно (вместе со всем остальным, что вы вытолкнули). Честно говоря, простое использование массива, вероятно, будет более эффективным и проще в написании кода.
То, как я обошел это, я использовал красно-черное дерево (в C++ это просто set<> тип данных STL). Структура данных содержала pair<> элемент, который имел double (стоимость) и string (узел). Из-за древовидной структуры очень эффективен доступ к минимальному элементу (я считаю, что C++ делает его еще более эффективным, поддерживая указатель на минимальный элемент).
Наряду с деревом я также сохранил массив значений типа double, содержащий расстояние для данного узла. Поэтому, когда мне нужно было переупорядочить узел в дереве, я просто использовал старое расстояние от массива dist вместе с именем узла, чтобы найти его в наборе. Затем я удалил бы этот элемент из дерева и снова вставил бы его в дерево с новым расстоянием. Для поиска узла O(log n) и вставить узел O(log n), поэтому стоимость переупорядочения узла составляет O(2 * log n) знак равно O(log n), Для двоичной кучи он также имеет O(log n) для вставки и удаления (и не поддерживает поиск). Таким образом, при стоимости удаления всех узлов до тех пор, пока вы не найдете нужный узел, измените его вес, а затем вставите все узлы обратно. После переупорядочения узла я бы изменил расстояние в массиве, чтобы отразить новое расстояние,
Я, честно говоря, не могу придумать способ изменить кучу таким образом, чтобы позволить ей динамически изменять веса узла, потому что вся структура кучи основана на весах, которые поддерживают узлы.
Этот алгоритм: http://algs4.cs.princeton.edu/44sp/DijkstraSP.java.html решает эту проблему с помощью "индексированной кучи": http://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html который по существу поддерживает список сопоставлений от ключа к индексу массива.
Я считаю, что основная трудность заключается в том, чтобы достичь временной сложности O(log n), когда нам нужно обновить расстояние между вершинами. Вот как это сделать:
- Для реализации кучи вы можете использовать массив.
- Для индексации используйте хеш-карту с номером вершины в качестве ключа и ее индексом в куче в качестве значения.
- Когда мы хотим обновить вершину, ищем ее индекс в Hash Map за время O (1).
- Уменьшите расстояние до вершины в куче, а затем продолжайте движение вверх (проверьте его новое расстояние относительно его корня, если значение корня больше, поменяйте местами корень и текущую вершину). Этот шаг также займет O(log n).
- Обновляйте индекс вершины в Hash Map по мере внесения изменений при обходе кучи.
Я думаю, что это должно сработать, и общая временная сложность будет O((E+V)*log V), как и предполагает теория.
Вы также можете использовать кучи Фибоначчи или Pairing, которые поддерживают ключ уменьшения в O(1). Boost обеспечивает реализацию для обоих
Я использую следующий подход. Всякий раз, когда я вставляю что-то в кучу, я передаю указатель на целое число (это место в памяти принадлежит мне, а не куче), которое должно содержать позицию элемента в массиве, управляемом кучей. Таким образом, если последовательность элементов в куче переставлена, предполагается обновить значения, на которые указывают эти указатели.
Так что для алгоритма Дейкстры я создаю posInHeap массив размера N.
Надеюсь, код сделает это более понятным.
template <typename T, class Comparison = std::less<T>> class cTrackingHeap
{
public:
cTrackingHeap(Comparison c) : m_c(c), m_v() {}
cTrackingHeap(const cTrackingHeap&) = delete;
cTrackingHeap& operator=(const cTrackingHeap&) = delete;
void DecreaseVal(size_t pos, const T& newValue)
{
m_v[pos].first = newValue;
while (pos > 0)
{
size_t iPar = (pos - 1) / 2;
if (newValue < m_v[iPar].first)
{
swap(m_v[pos], m_v[iPar]);
*m_v[pos].second = pos;
*m_v[iPar].second = iPar;
pos = iPar;
}
else
break;
}
}
void Delete(size_t pos)
{
*(m_v[pos].second) = numeric_limits<size_t>::max();// indicate that the element is no longer in the heap
m_v[pos] = m_v.back();
m_v.resize(m_v.size() - 1);
if (pos == m_v.size())
return;
*(m_v[pos].second) = pos;
bool makingProgress = true;
while (makingProgress)
{
makingProgress = false;
size_t exchangeWith = pos;
if (2 * pos + 1 < m_v.size() && m_c(m_v[2 * pos + 1].first, m_v[pos].first))
exchangeWith = 2 * pos + 1;
if (2 * pos + 2 < m_v.size() && m_c(m_v[2 * pos + 2].first, m_v[exchangeWith].first))
exchangeWith = 2 * pos + 2;
if (pos > 0 && m_c(m_v[pos].first, m_v[(pos - 1) / 2].first))
exchangeWith = (pos - 1) / 2;
if (exchangeWith != pos)
{
makingProgress = true;
swap(m_v[pos], m_v[exchangeWith]);
*m_v[pos].second = pos;
*m_v[exchangeWith].second = exchangeWith;
pos = exchangeWith;
}
}
}
void Insert(const T& value, size_t* posTracker)
{
m_v.push_back(make_pair(value, posTracker));
*posTracker = m_v.size() - 1;
size_t pos = m_v.size() - 1;
bool makingProgress = true;
while (makingProgress)
{
makingProgress = false;
if (pos > 0 && m_c(m_v[pos].first, m_v[(pos - 1) / 2].first))
{
makingProgress = true;
swap(m_v[pos], m_v[(pos - 1) / 2]);
*m_v[pos].second = pos;
*m_v[(pos - 1) / 2].second = (pos - 1) / 2;
pos = (pos - 1) / 2;
}
}
}
const T& GetMin() const
{
return m_v[0].first;
}
const T& Get(size_t i) const
{
return m_v[i].first;
}
size_t GetSize() const
{
return m_v.size();
}
private:
Comparison m_c;
vector< pair<T, size_t*> > m_v;
};