我正在编写dijkstra算法的代码,对于我们应该找到与当前正在使用的节点的距离最小的节点的部分,我在那里使用一个数组并完全遍历它以找出节点.
这个部分可以用二进制堆代替,我们可以在O(1)时间内找出节点,但是我们还在更进一步的迭代中更新节点的距离,我将如何合并该堆？
在数组的情况下,我所要做的就是去第(ith -1)索引并更新那个节点的值,但是在二进制堆中不能做同样的事情,我将不得不做完全搜索来计算退出节点的位置,然后更新它.
这个问题的解决方法是什么？
Fir*_*muP 24
这只是我在课堂上发现的一些信息,我和同学分享了这些信息.我以为我会让人们更容易找到它,我已经离开了这篇文章,这样我就可以在找到解决方案时回答它.
注意:我假设在这个例子中你的图形的顶点有一个ID来跟踪哪个是哪个.这可以是名称,数字,等等,只需确保您更改struct下面的类型.如果没有这种区分方法,那么可以使用指向顶点的指针并比较它们的指向地址.
你在这里遇到的问题是,在Dijkstra的算法中,我们被要求将图形顶点及其键存储在该优先级队列中,然后更新队列中剩余的键.但是...... 堆数据结构无法进入任何不是最小节点或最后节点的特定节点!
我们能够做的最好的事情是在O(n)时间内遍历堆以找到它,然后在O(Logn)更新其密钥并冒泡.这使得更新每个边缘的所有顶点O(n),使得我们实现Dijkstra O(mn),比最佳O(mLogn)更差.
的Bleh!一定有更好的方法!
因此,我们需要实现的并不是标准的基于最小堆的优先级队列.我们需要比标准的4 pq操作多一个操作:
为了减少关键,我们需要:
基本上,既然你(我假设它已经在过去4个月的某个时间实现)可能会使用"基于数组"的堆实现,这意味着我们需要堆来跟踪每个顶点及其索引在数组中,以便可以进行此操作.
设计一个struct:(c ++)
struct VertLocInHeap
{
int vertex_id;
int index_in_heap;
};
允许你跟踪它,但是将它们存储在一个数组中仍然会给你O(n)时间来查找堆中的顶点.没有复杂性改进,而且比以前更复杂.>.<
我的建议(如果优化是目标):
我实际上使用了std::map声明为:std :: map m_locations; 在堆中而不是使用struct.第一个参数(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)操作为bubble -up.
因此,我们有一个的log(n)+日志^ 2(N)= O(登录^ 2(n))的用于更新在堆的关键值对的单个边缘的操作.这使得我们的迪杰斯特拉ALG采取ö (mLog ^ 2(n)).这非常接近理论上的最佳值,至少和我能得到的一样接近.真棒Possum!
下行:我们在堆内存中的信息量只有两倍.它是一个"现代"的问题？不是真的;我的桌面可以存储超过80亿的整数,而且许多现代计算机至少有8GB的RAM;但是,它仍然是一个因素.如果你用40亿个顶点的图形执行这个实现,这可能比你想象的更频繁地发生,然后它会导致问题.而且,所有这些额外的读/写,可能不会影响分析的复杂性,可能仍需要一些机器上的时间,特别是如果信息是存储外部 盟友.
我希望这对未来的某个人有所帮助,因为我有一个时间找到所有这些信息的魔鬼,然后拼凑我从这里,那里,到处都是形成这一点.我责怪互联网和睡眠不足.