Как я могу использовать двоичную кучу в алгоритме Дейкстры?

Я пишу код алгоритма dijkstra, для той части, где мы должны найти node с минимальным расстоянием от используемого в настоящее время node, я использую массив там и обход его полностью, чтобы выяснить node.

Эта часть может быть заменена двоичной кучей, и мы можем определить node в O (1) раз, но мы также обновляем расстояние node в дальнейших итерациях. Как включить эту кучу?

В случае массива все, что мне нужно сделать, это перейти к индексу (ith -1) и обновить значение этого node, но то же самое не может быть сделано в двоичной куче, мне нужно будет сделать полный поиск, чтобы выяснить положение node, а затем обновить его.

Что такое обход проблемы?

Ответ 1

Это лишь некоторая информация, которую я нашел, когда делаю это в классе, который я поделился с моими одноклассниками. Я думал, что облегчил бы людям найти его, и я оставил это сообщение, чтобы ответить на него, когда нашел решение.

Примечание: Я предполагаю для этого примера, что ваши вершины графа имеют идентификатор, чтобы отслеживать, что есть. Это может быть имя, число и т.д., Просто убедитесь, что вы изменили тип в struct ниже. Если у вас нет таких средств отличия, вы можете использовать указатели на вершины и сравнить их указательные адреса.

Проблема, с которой вы столкнулись здесь, состоит в том, что в алгоритме Дейкстры нам предлагается сохранить вершины графов и их ключи в этой очереди приоритетов, затем обновить ключи оставшихся в очередия > . Но... Структуры данных кучи не имеют возможности получить какой-либо конкретный node, который не является минимальным или последним node!
Самое лучшее, что мы могли бы сделать, - это переместить кучу в O (n) время, чтобы найти ее, а затем обновить ее ключ и размыть пузырь в O (Logn). Это делает обновление всех вершин O (n) для каждого отдельного ребра, что делает нашу реализацию Dijkstra O (mn) хуже, чем оптимальная O (mlogn).

BLEH! Должен быть лучший способ!

Итак, что нам нужно реализовать, это не стандартная очередь приоритетов с мини-кучей. Нам нужна еще одна операция, чем стандартные 4 pq операции:

IsEmpty
Добавить
PopMin
PeekMin
и DecreaseKey

Для DecreaseKey нам нужно:

найдите определенную вершину внутри кучи
понизить значение ключа
"куча" или "пузырь" вершины

По сути, поскольку вы были (я предполагаю, что он был реализован когда-то за последние 4 месяца), вероятно, будет использоваться реализация "кучи" на основе массива, это означает, что мы нуждаемся в куче, чтобы отслеживать каждую вершину и ее индекс в массиве, чтобы эта операция была возможной.

Разработка struct как: (С++)

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) для нахождения любой заданной вершины в p-q. Для пузырьков мы выполняем движения O (Log (n)), для каждого свопа, выполняющего поиск O (Log (n)) на карте индексов массива, в результате чего выполняется операция O (Log ^ 2 (n) для пузырьков -до.
Итак, у нас есть операция Log (n) + Log ^ 2 (n) = O (Log ^ 2 (n)) для обновления значений ключей в куче для одного края. Это заставляет наш Dijkstra alg брать O (mLog ^ 2 (n)). Это довольно близко к теоретическому оптимуму, по крайней мере, как можно ближе к нему. Awesome Possum!
Даунсайд: Мы храним в два раза больше информации в памяти для кучи. Это "современная" проблема? На самом деле, нет; мой desky может хранить более 8 миллиардов целых чисел, а многие современные компьютеры имеют не менее 8 ГБ оперативной памяти; однако, это все еще фактор. Если вы выполнили эту реализацию с графиком из 4 миллиардов вершин, что может произойти намного чаще, чем вы думаете, то это вызывает проблему. Кроме того, все эти дополнительные чтения/записи, которые могут не влиять на сложность анализа, могут по-прежнему занимать некоторое время на некоторых машинах, особенно если информация хранится извне.

Я надеюсь, что это поможет кому-то в будущем, потому что у меня было чертовски время, чтобы найти всю эту информацию, а затем собрать кусочки, которые я получил отсюда, там и везде, чтобы сформировать это. Я обвиняю интернет и недостаток сна.

Ответ 2

Проблема, с которой я столкнулась с использованием любой формы кучи, заключается в том, что вам нужно переупорядочить узлы в куче. Чтобы сделать это, вам нужно будет выталкивать все из кучи, пока не найдет node вам, а затем измените вес и нажмите его обратно (вместе со всем остальным, что вы выскочили). Честно говоря, просто использование массива, вероятно, было бы более эффективным и более легким для кода, чем это.

Как я обошел это, я использовал дерево Red-Black (в С++ это только тип данных set<> для STL). Структура данных содержала элемент pair<>, который имел double (стоимость) и string (node). Из-за древовидной структуры очень эффективно обращаться к минимальному элементу (я считаю, что С++ делает его еще более эффективным, поддерживая указатель на минимальный элемент).

Наряду с деревом я также сохранил массив двойников, который содержал расстояние для данного node. Поэтому, когда мне нужно было изменить порядок node в дереве, я просто использовал старое расстояние от массива dist вместе с именем node, чтобы найти его в наборе. Затем я удаляю этот элемент из дерева и снова вставляю его в дерево с новым расстоянием. Чтобы выполнить поиск node O(log n) и вставить node O (log n), поэтому стоимость изменения порядка node равна O(2 * log n)= O(log n). Для двоичной кучи он также имеет O(log n) для вставки и удаления (и не поддерживает поиск). Таким образом, с учетом стоимости удаления всех узлов до тех пор, пока вы не найдете нужный node, измените его вес, а затем вставьте все узлы обратно. После того, как node будет переупорядочено, я тогда изменил бы расстояние в массиве до отражают новое расстояние.

Я, честно говоря, не могу придумать способ изменить кучу таким образом, чтобы она динамически меняла весы node, потому что вся структура кучи основана на весах, которые поддерживают узлы.

Ответ 3

Этот алгоритм: http://algs4.cs.princeton.edu/44sp/DijkstraSP.java.html работает вокруг этой проблемы, используя "индексированную кучу": http://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html, который по существу поддерживает список сопоставлений от индекса ключа к массиву.

Ответ 4

Я бы сделал это, используя хэш-таблицу в дополнение к массиву Min-Heap.

В хэш-таблице есть ключи, которые являются хеш-кодированными как объекты и значения node, которые являются индексами того, где эти узлы находятся в элементе min-heap.

Тогда в любое время, когда вы перемещаете что-то в мини-куче, вам просто нужно обновить таблицу хешей соответственно. Так как не более 2 элементов будут перемещены за операцию в мини-куче (то есть они обмениваются), и наша стоимость за ход равна O (1), чтобы обновить хеш-таблицу, тогда мы не будем нарушать асимптотическую оценку мин-кучи. Например, minHeapify - O (lgn). Мы только что добавили 2 операции (х) хэш-таблицы на операцию 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, так что он в основном фиксирован, но вам нужен извлеченный ключ, который нужно удалить из хеш-таблицы. Вам также необходимо изменить значение уменьшенияKey для отслеживания этих изменений. После того, как это исправлено, вставка также должна быть исправлена, так как она должна использовать метод reduceKey. Это должно охватывать все ваши базы, и вы не изменили бы асимптотические границы вашего алгоритма, и вам все равно придется использовать кучу для вашей очереди приоритетов.

Обратите внимание, что минимальная куча Фибоначчи на самом деле предпочтительнее стандартной Min Heap в этой реализации, но это совершенно другая возможность червей.

Ответ 5

Я использую следующий подход. Всякий раз, когда я вставляю что-то в кучу, я передаю указатель на целое число (это место памяти принадлежит мне, а не куче), которое должно содержать позицию элемента в массиве, управляемом кучей. Поэтому, если последовательность элементов в куче перестроена, она должна обновлять значения, на которые указывают эти указатели.

Итак, для aljirithm Dijkstra я создаю массив posInHeap sizeN.

Надеюсь, код сделает его более понятным.

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

Ответ 6

Другим решением является "ленивое удаление". Вместо уменьшения операции с ключом вы просто вставляете node еще раз в кучу с новым приоритетом. Итак, в куче будет еще одна копия node. Но, что node будет выше в куче, чем любая предыдущая копия. Затем, когда вы получаете следующий минимум node, вы можете просто проверить, принят ли node. Если это так, просто опустите цикл и продолжайте (ленивое удаление).

Это имеет немного худшее использование производительности/более высокой памяти из-за копий внутри кучи. Но он по-прежнему ограничен (по количеству подключений) и может быть быстрее других реализаций для некоторых размеров проблем.