一次令人自闭的算法作业




最近一次Data Structure & Algorithm课程的作业是要求实现Dijkstra算法,并且其中的排序部分要使用最小堆来实现。

Dijkstra的基本思路如下

1. 初始时,S只包含起点s;U包含除s外的其他顶点,且U中顶点的距离为”起点s到该顶点的距离”[例如,U中顶点v的距离为(s,v)的长度,然后s和v不相邻,则v的距离为∞]。

2.从U中选出”距离最短的顶点k”,并将顶点k加入到S中;同时,从U中移除顶点。

3.更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离,是由于上一步中确定了k是求出最短路径的顶点,从而可以利用k来更新其它顶点的距离;例如,(s,v)的距离可能大于(s,k)+(k,v)的距离。

4.重复步骤(2)和(3),直到遍历完所有顶点。

我们的作业要求是在步骤2中的“选出距离最短的顶点”要用堆来实现。也就是说,我们需要维护一个最小堆,里面包含有起点到各个尚未访问到的顶点的(目前为止的)最短距离。每一次更新各个顶点到起点的距离时,都要更新堆中所有顶点的值。这样,每次寻找距离最短的顶点时,直接取出堆的根即可,省去了每次都要遍历一遍来寻找最小值。

我们要求的实现逻辑是这样的:维护一个如下的routing table,其中存储了每个节点的id,是否已经访问过,到出发点的最短距离,和该节点在堆中对应的位置。每次访问图中的一个节点时,都要在routing table中更新该节点及其所有后继节点的距离和其他信息。

node012
is_visitedtruetruefalse
cost013
heap_position012

我写完提交之后,被告知我的solution在小用例上部分正确,大用例上报vector越界的运行时错误。

那就开工吧!

我首先尝试了几个相对小的用例,但是无法复现问题。于是我用生成器生成了一个有100条边的图,果然vector越界的问题出现了。经过单步调试之后发现在图没有走完的时候,堆中的元素已经被取干净了。

又经过了长达数十分钟的单步调试,我终于发现问题在于生成的测试样例——其中一些节点只有出度而没有入度,也就是说,有些点是永远无法到达的,而我的逻辑是将所有点走完之后才能结束循环,因此堆中的元素会在循环跳出之前就消耗掉,导致vector越界。

我的解决方法十分粗暴——当堆中元素为空时即跳出循环,这样就不会有越界问题了。

然而事情并没有结束。

修改之后,我发现在小的用例上能够得出正确结果,而在稍大一些的用例上虽然不会有运行时错误,但是答案却是错的。最麻烦的事情是——由于用例过大不可能单步去调,所以完全没法定位问题出在哪。我绞尽脑汁想了一些奇奇怪怪的小型用例,但是还是无法复现问题。

于是我只能把程序拆解成若干部分,依次排查问题。

我仿照单元测试的方法,单独写了一个函数去调用堆的插入,删除,和修改这三个方法,并且通过随机生成巨大的测试样例来验证堆是否合法。经过一通测试还真的发现了问题,我发现从堆中移除和修改元素的方法都存在缺陷,有时会导致堆不合法。经过修改之后,和堆相关的所有方法终于可以确定可用了。

然而事情还是没有结束。当我满心欢喜地再次测试整个程序时,我发现虽然已经修正了一些错误,但是输出的答案依然没变。于是现在又进入到了死胡同。

由于和堆相关的算法都已经确认正确,根据福尔摩斯推理法,问题只能出在Dijkstra算法本身的实现上——即使看起来这里不应该出现问题。然而我把我实现的算法和课上的笔记和网上的资料仔细对比,发现算法实现并没有问题。

到目前为止,我所推测的所有可能性都已经被推翻,所以也只能单步调试了。我选了几个可能出现问题节点打了断点,然而还是没有发现问题。直到无意间,我发现在循环结束时,routing table中的一部分节点还没有被访问到。

经过一番检查发现,由于每次更新堆中节点的值的时候,堆中节点的位置会改变,然而routing table中记录的该节点在堆中的位置却没有改变。导致堆中一些节点的值被错误地更新而被提前取出。解决方法很简单,只要每次查找堆中元素时使用值查找而不是使用索引查找即可。只不过这个做法有些tricky,并且会降低一些性能,不过确实能够解决问题。




Posted

in

by

Comments

2 responses to “一次令人自闭的算法作业”

  1. chen Avatar
    chen

    很棒的总结,加油hhh

发表回复/Leave a Reply

您的电子邮箱地址不会被公开。/Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.