heap - recorrido - dijkstra c++

¿Cómo puedo usar el montón binario en el algoritmo Dijkstra?

Question

Estoy escribiendo el código del algoritmo de dijkstra, para la parte en la que se supone que debemos encontrar el nodo con la distancia mínima desde el nodo que se está utilizando actualmente, estoy usando una matriz de allí y lo estoy recorriendo completamente para descubrir el nodo.

Esta parte se puede reemplazar por un montón binario y podemos calcular el nodo en O (1), pero también actualizamos la distancia del nodo en otras iteraciones. ¿Cómo incorporaré ese montón?

En el caso de la matriz, todo lo que tengo que hacer es ir al índice (ith -1) y actualizar el valor de ese nodo, pero no se puede hacer lo mismo en el montón binario, tendré que hacer la búsqueda completa para calcular fuera de la posición del nodo y luego actualizarlo.

¿Cuál es la solución de este problema?

Answer 1

El problema que encontré con el uso de cualquier forma de almacenamiento dinámico es que, es necesario reordenar los nodos en el almacenamiento dinámico. Para hacer eso, tendría que seguir haciendo estallar todo desde el montón hasta que encuentre el nodo que necesita, luego cambie el peso y vuelva a insertarlo (junto con todo lo demás que abrió). Honestamente, usar una matriz probablemente sería más eficiente y más fácil de codificar que eso.

La forma en que resolví esto fue que usé un árbol Rojo-Negro (en C ++ es solo el tipo de datos set<> de la STL). La estructura de datos contenía un elemento pair<> que tenía un double (costo) y una string (nodo). Debido a la estructura del árbol, es muy eficiente acceder al elemento mínimo (creo que C ++ lo hace aún más eficiente al mantener un puntero al elemento mínimo).

Junto con el árbol, también conservé una serie de dobles que contenían la distancia para un nodo determinado. Entonces, cuando necesitaba reordenar un nodo en el árbol, simplemente usé la distancia anterior de la matriz dist junto con el nombre del nodo para encontrarlo en el conjunto. Luego eliminaría ese elemento del árbol y lo reinsertaría en el árbol con la nueva distancia. Para buscar un nodo O(log n) e insertar un nodo O (log n), el costo para reordenar un nodo es O(2 * log n) = O(log n) . Para un montón binario, también tiene una O(log n) tanto para insertar como para eliminar (y no admite la búsqueda). Entonces, con el costo de eliminar todos los nodos hasta que encuentre el nodo que desea, cambie su peso, luego inserte todos los nodos nuevamente. Una vez que el nodo haya sido reordenado, cambiaría la distancia en la matriz para reflejar la nueva distancia .

Honestamente, no puedo pensar en una manera de modificar un montón de tal manera que le permita cambiar dinámicamente los pesos de un nodo, porque toda la estructura del montón se basa en los pesos que mantienen los nodos.

Answer 2

Esta es solo información que encontré al hacer esto en una clase, que compartí con mis compañeros. Pensé que sería más fácil para la gente encontrarlo, y había dejado esta publicación para poder responderla cuando encontré una solución.

Nota: Supongo que para este ejemplo, los vértices de su gráfico tienen una ID para realizar un seguimiento de cuál es cuál. Esto podría ser un nombre, un número, lo que sea, solo asegúrese de cambiar el tipo en la struct continuación. Si no dispone de tales medios de distinción, puede usar punteros a los vértices y comparar sus direcciones apuntadas a.

El problema al que se enfrenta aquí es el hecho de que, en el algoritmo de Dijkstra, se nos pide que almacenemos los vértices de los gráficos y sus claves en esta cola de prioridad, y luego actualicemos las claves de las que quedan en la cola . Pero ... ¡ las estructuras de datos del montón no tienen forma de llegar a ningún nodo en particular que no sea el mínimo o el último nodo!
Lo mejor que podríamos hacer es atravesar el montón en O (n) tiempo para encontrarlo, luego actualizar su clave y hacer una burbuja, en O (Logn). Eso hace que la actualización de todos los vértices O (n) para cada borde individual, haciendo que nuestra implementación de Dijkstra O (mn), sea mucho peor que la O óptima (mLogn).

Bleh! ¡Tiene que haber una mejor manera!

Entonces, lo que necesitamos implementar no es exactamente una cola de prioridad estándar basada en min-heap. Necesitamos una operación más que las operaciones estándar de 4 pq:

1. Esta vacio
2. Añadir
3. PopMin
4. Peekmin
5. y DecreaseKey

Con el fin de DecreaseKey , tenemos que:

• encontrar un vértice particular dentro del montón
• bajar su valor-clave
• "apilar" o "burbujear" el vértice

Esencialmente, dado que usted (supongo que se ha implementado en algún momento de los últimos 4 meses) probablemente va a utilizar una implementación de pila "basada en matrices", esto significa que necesitamos la pila para realizar un seguimiento de cada vértice y su índice en la matriz para que esta operación sea posible.

Diseñando una struct como: (c ++)

struct VertLocInHeap
{
    int vertex_id;
    int index_in_heap;
};

le permitiría realizar un seguimiento de eso, pero almacenarlos en una matriz aún le daría tiempo O (n) para encontrar el vértice en el montón. No mejora la complejidad, y es más complicado que antes. >. <
Mi sugerencia (si la optimización es el objetivo aquí) :

1. Almacene esta información en un árbol de búsqueda binario cuyo valor clave es el `vertex_id`
2. hacer una búsqueda binaria para encontrar la ubicación del vértice en el montón en O (Logn)
3. usar el índice para acceder al vértice y actualizar su clave en O (1)
4. burbujear el vértice en O (Logn)

De hecho, utilicé un std::map declarado como: std :: map m_locations; en el montón en lugar de usar la estructura. El primer parámetro (Clave) es el vertex_id, y el segundo parámetro (Valor) es el índice en la matriz del montón. Dado que std::map garantiza búsquedas O (Logn), esto funciona muy bien fuera de la caja. Luego, cada vez que inserte o m_locations[vertexID] = newLocationInHeap; burbuja, simplemente m_locations[vertexID] = newLocationInHeap;
Dinero fácil.

Análisis:
Al revés: ahora tenemos O (Logn) para encontrar cualquier vértice dado en pq. Para la burbuja, hacemos movimientos O (Log (n)), para cada swap que realiza una búsqueda O (Log (n)) en el mapa de índices de matriz, lo que da como resultado una operación O (Log ^ 2 (n) para bubble -arriba.
Por lo tanto, tenemos una operación de registro (n) + registro ^ 2 (n) = O (registro ^ 2 (n)) para actualizar los valores clave en el montón para un solo borde. Eso hace que nuestra Dijkstra alg tome O (mLog ^ 2 (n)). Eso está bastante cerca del óptimo teórico, al menos lo más cerca que puedo conseguirlo. ¡Increíble zarigüeya!
Desventaja: estamos almacenando literalmente el doble de información en memoria para el montón. ¿Es un problema "moderno"? Realmente no; mi dispositivo puede almacenar más de 8 mil millones de enteros, y muchas computadoras modernas vienen con al menos 8 GB de RAM; Sin embargo, sigue siendo un factor. Si hiciste esta implementación con un gráfico de 4 mil millones de vértices, lo que puede suceder con mucha más frecuencia de lo que crees, eso causa un problema. Además, todas esas lecturas / escrituras adicionales, que pueden no afectar la complejidad del análisis, aún pueden tomar tiempo en algunas máquinas, especialmente si la información se almacena externamente.

Espero que esto ayude a alguien en el futuro, porque me costó mucho encontrar toda esta información, luego juntar los bits que obtuve de aquí, allá y en todas partes para formar esto. Estoy culpando a internet y la falta de sueño.

Answer 3

Este algoritmo: http://algs4.cs.princeton.edu/44sp/DijkstraSP.java.html resuelve este problema utilizando "montón indexado": http://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html que esencialmente mantiene la lista de asignaciones de clave a índice de matriz.

Answer 4

Estoy usando el siguiente enfoque. Cada vez que inserto algo en el montón, paso un puntero a un entero (esta ubicación de memoria es propiedad de mí, no del montón) que debe contener la posición del elemento en la matriz administrada por el montón. Entonces, si la secuencia de elementos en el montón se reorganiza, se supone que actualiza los valores apuntados por estos punteros.

Así que para el algoritmo de Dijkstra estoy creando una matriz posInHeap de tamañoN.

Con suerte, el código lo hará más claro.

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

Answer 5

Lo haría usando una tabla hash además de la matriz Min-Heap.

La tabla hash tiene claves que están codificadas para ser los objetos de nodo y los valores que son los índices de dónde están esos nodos en la arrray min-heap.

Luego, cada vez que mueva algo en el min-heap solo necesita actualizar la tabla hash en consecuencia. Dado que, como máximo, se moverán 2 elementos por operación en el montón mínimo (es decir, se intercambian), y nuestro costo por movimiento es O (1) para actualizar la tabla hash, entonces no habremos dañado el límite asintótico del operaciones min-heap. Por ejemplo, minHeapify es O (lgn). Acabamos de agregar 2 O (1) operaciones de tabla hash por operación minHeapify. Por lo tanto, la complejidad general sigue siendo O (lgn).

¡Tenga en cuenta que necesitaría modificar cualquier método que mueva sus nodos en el min-heap para hacer este seguimiento! Por ejemplo, minHeapify () requiere una modificación que se parece a esto usando 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 debería depender de minHeapify, de modo que la mayoría esté fija, pero también es necesario que la clave extraída se elimine de la tabla hash. También deberías modificar la tecla de reducción para rastrear estos cambios también. Una vez que se haya corregido, entonces la inserción también debería ser fija, ya que debería estar usando el método de disminución de clave. Eso debería cubrir todas sus bases y no habrá alterado los límites asintóticos de su algoritmo y aún podrá seguir usando un montón para su cola de prioridad.

Tenga en cuenta que en esta implementación es preferible utilizar Fibonacci Min Heap en lugar de Min Heap estándar, pero es una lata de gusanos totalmente diferente.

Answer 6

Otra solución es la "eliminación perezosa". En lugar de disminuir la operación clave, simplemente inserte el nodo una vez más para acumular con nueva prioridad. Entonces, en el montón habrá otra copia del nodo. Pero, ese nodo será más alto en el montón que cualquier copia anterior. Luego, al obtener el siguiente nodo mínimo, simplemente puede verificar si el nodo ya está siendo aceptado. Si es así, simplemente omita el bucle y continúe (eliminación lenta).

Esto tiene un rendimiento un poco peor / mayor uso de memoria debido a las copias dentro del montón. Sin embargo, aún es limitado (al número de conexiones) y puede ser más rápido que otras implementaciones para algunos tamaños de problemas.