35

我正在编写 dijkstra 算法的代码，对于我们应该找到与当前正在使用的节点的距离最小的节点的部分，我在那里使用一个数组并完全遍历它以找出节点。

这部分可以用二叉堆代替，我们可以在 O(1) 时间内计算出节点，但我们还会在进一步的迭代中更新节点的距离，我将如何合并该堆？

在数组的情况下，我所要做的就是转到（ith -1）索引并更新该节点的值，但是在二进制堆中无法完成同样的事情，我将不得不进行完整搜索才能确定出节点的位置，然后更新它。

这个问题的解决方法是什么？

4

7 回答 7

28

这只是我在课堂上发现的一些信息，我与同学分享。我想我会让人们更容易找到它，所以我留下了这篇文章，以便在找到解决方案时可以回答它。

注意：对于这个例子，我假设你的图的顶点有一个 ID 来跟踪哪个是哪个。这可以是名称、数字等，只要确保更改struct下面的类型即可。如果您没有这样的区分方法，那么您可以使用指向顶点的指针并比较它们指向的地址。

您在这里面临的问题是，在 Dijkstra 算法中，我们被要求将图顶点及其键存储在此优先级队列中，然后更新队列中剩余的键。但是......堆数据结构无法到达任何不是最小或最后一个节点的特定节点！
我们能做的最好的事情是在 O(n) 时间内遍历堆以找到它，然后在 O(Logn) 处更新它的键并冒泡。这使得为​​每条边更新所有顶点O(n)，使我们的 Dijkstra O(mn) 实现比最优 O(mLogn) 差得多。

呸！一定有更好的方法！

所以，我们需要实现的并不是一个标准的基于最小堆的优先级队列。我们需要比标准的 4 个 pq 操作多一个操作：

  1. 是空的
  2. 添加
  3. 流行音乐
  4. 窥视敏
  5. 和减少键

为了DecreaseKey，我们需要：

  • 在堆中找到一个特定的顶点
  • 降低其键值
  • “堆积”或“冒泡”顶点

本质上，由于您（我假设它已在过去 4 个月的某个时间实现）可能会使用“基于数组”的堆实现，这意味着我们需要堆来跟踪每个顶点及其索引在数组中，以使此操作成为可能。

设计一个struct类似的东西：（c ++）

struct VertLocInHeap
{
    int vertex_id;
    int index_in_heap;
};

将允许您跟踪它，但是将它们存储在数组中仍然会给您 O(n) 时间来查找堆中的顶点。没有复杂性改进，而且比以前更复杂。>.<
我的建议（如果优化是这里的目标）：

  1. 将此信息存储在二叉搜索树中，其键值为“vertex_id”
  2. 进行二分搜索以在 O(Logn) 中找到顶点在堆中的位置
  3. 使用索引访问顶点并在 O(1) 中更新其键
  4. 在 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) 操作-up。
所以，我们有一个 Log(n) + Log^2(n) = O(Log^2(n))操作来更新堆中单个边的键值。这使得我们的 Dijkstra 算法取 O (mLog^2(n))。这非常接近于理论上的最优值，至少与我能得到的一样接近。真棒负鼠！
缺点：我们在内存中为堆存储了两倍的信息。这是一个“现代”问题吗？并不真地; 我的办公桌可以存储超过 80 亿个整数，而且许多现代计算机都配备了至少 8GB 的​​ RAM；但是，它仍然是一个因素。如果您使用包含 40 亿个顶点的图执行此实现，这可能比您想象的更频繁地发生，那么它会导致问题。此外，所有这些额外的读/写可能不会影响分析的复杂性，在某些机器上可能仍然需要时间，尤其是在信息存储在外部的情况下。

我希望这对将来的某个人有所帮助，因为我花了很长时间才找到所有这些信息，然后将我从这里、那里和任何地方得到的信息拼凑在一起，形成了这个。我指责互联网和睡眠不足。

于 2013-04-14T16:45:51.153 回答
4

我在使用任何形式的堆时遇到的问题是，您需要重新排序堆中的节点。为此，您必须不断从堆中弹出所有内容，直到找到所需的节点，然后更改权重，并将其推回（连同您弹出的所有其他内容）。老实说，仅使用数组可能会比这更有效且更容易编码。

我解决这个问题的方法是使用红黑树（在 C++ 中，它只是set<>STL 的数据类型）。数据结构包含一个pair<>具有double（成本）和string（节点）的元素。由于树结构，访问最小元素非常有效（我相信 C++ 通过维护指向最小元素的指针使其更加高效）。

除了树，我还保留了一个包含给定节点距离的双精度数组。因此，当我需要对树中的节点重新排序时，我只需使用与 dist 数组的旧距离以及节点名称即可在集合中找到它。然后，我将从树中删除该元素，并将其重新插入到具有新距离的树中。搜索节点O(log n)并插入节点 O(log n)，因此重新排序节点的成本为O(2 * log n)= O(log n)。对于二叉堆，它也有一个O(log n)用于插入和删除的（并且不支持搜索）。因此，在找到所需节点之前删除所有节点的成本，更改其权重，然后将所有节点重新插入。一旦节点重新排序，我将更改数组中的距离以反映新距离.

老实说，我想不出一种方法来修改堆以允许它动态更改节点的权重，因为堆的整个结构是基于节点维护的权重。

于 2013-01-10T17:29:30.617 回答
4

除了 Min-Heap 数组之外，我还会使用哈希表来执行此操作。

哈希表具有被哈希编码为节点对象的键和作为这些节点在最小堆数组中位置的索引的值。

然后，每当您在最小堆中移动某些东西时，您只需要相应地更新哈希表。由于在最小堆中每次操作最多移动 2 个元素（即它们被交换），并且每次移动的成本是 O(1) 来更新哈希表，因此我们不会破坏最小堆操作。例如，minHeapify 是 O(lgn)。我们刚刚为每个 minHeapify 操作添加了 2 O(1) 哈希表操作。因此总体复杂度仍然是 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，所以大部分是固定的，但是您确实需要从哈希表中删除提取的键。您还需要修改 reductionKey 以跟踪这些更改。一旦修复了，那么 insert 也应该被修复，因为它应该使用 reductionKey 方法。这应该涵盖您的所有基础，并且您不会更改算法的渐近边界，并且您仍然可以继续使用堆作为优先级队列。

请注意，在此实现中，Fibonacci Min Heap 实际上优于标准 Min Heap，但这是完全不同的蠕虫罐。

于 2013-07-19T17:11:33.020 回答
2

此算法：http ://algs4.cs.princeton.edu/44sp/DijkstraSP.java.html 通过使用“索引堆”解决此问题：http: //algs4.cs.princeton.edu/24pq/IndexMinPQ.java .html本质上维护从键到数组索引的映射列表。

于 2013-06-23T15:40:18.410 回答
2

另一种解决方案是“延迟删除”。您只需将节点再次插入到具有新优先级的堆中，而不是减少键操作。因此，在堆中将有另一个节点副本。但是，该节点在堆中将高于任何先前的副本。然后在获得下一个最小节点时，您可以简单地检查节点是否已被接受。如果是，则只需省略循环并继续（延迟删除）。

由于堆内的副本，这具有稍差的性能/更高的内存使用率。但是，它仍然受到限制（连接数）并且对于某些问题大小可能比其他实现更快。

于 2017-11-23T20:02:33.177 回答
0

我正在使用以下方法。每当我在堆中插入一些东西时，我都会将一个指针传递给一个整数（这个内存位置是我拥有的，而不是堆），它应该包含堆管理的数组中元素的位置。因此，如果堆中的元素序列被重新排列，则应该更新这些指针指向的值。

所以对于 Dijkstra 算法，我正在创建一个posInHeapsizeN 的数组。

希望代码能让它更清晰。

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;
};
于 2017-04-03T06:49:15.587 回答
0

我相信主要困难是当我们必须更新顶点距离时能够实现 O(log n) 时间复杂度。以下是有关如何执行此操作的步骤：

  1. 对于堆实现，您可以使用数组。
  2. 对于索引，使用 Hash Map，以顶点编号为键，其在堆中的索引为值。
  3. 当我们想要更新一个顶点时，在 O(1) 时间内在 Hash Map 中搜索它的索引。
  4. 减少堆中的顶点距离，然后继续向上遍历（检查其与根的新距离，如果根的值更大，则交换根和当前顶点）。这一步也需要 O(log n)。
  5. 当您在遍历堆时进行更改时，更新 Hash Map 中的顶点索引。

我认为这应该可行，并且正如理论所暗示的那样，整体时间复杂度将为 O((E+V)*log V)。

于 2021-05-26T15:34:15.560 回答