Page 163 - 《软件学报》2020年第12期

潘敏佳 等:面向时序图数据的快速环枚举算法 3829

法的基础上进行改进,按照比较直接的想法,获取小于某一长度 L 的环的办法可以是:从点 s 开始搜索,发现搜索
长度大于等于 L 之后,就立刻停止搜索,因为继续搜索下去,获得的环路长度一定超过 L.但是我们可以证明,在
2SCENT 的剪枝方法上直接使用这个想法会导致非简单环路的发生.
这个错误发生的原因,是 2SCENT 算法中关闭时间的设置.如图 3 所示:若我们想要所有长度小于 5 的环路,
4
2
1
3
7
5
5
4
当前搜索路径为1⎯⎯→⎯⎯→⎯⎯→⎯⎯→ 时,我们发现路径长度已经为最大值 4,但是仍然没有成环,说明
可以停止对这段路径接下来的搜索.此时,由于搜索停止,节点 4 会加入到节点 5 的阻塞列表中.以此类推,最终节
5
2
1
5
6
9
点 2 加入节点 3 的阻塞列表.当搜索程序回退,当前搜索路径成为1⎯⎯→⎯⎯→⎯⎯→ 时,我们发现了一条长度
为 4 的环路.此时,由于环路成立,节点开始解锁,第 1 个解锁的节点是节点 6.由于节点的解锁是一系列的级联反
应,最终节点 2 的关闭时间被更新为 4.此时,节点 2 的关闭时间就已经开始出现了问题,节点 2 明明在当前道路
中,关闭时间却异常地变大了.这样会导致未来其他节点通往节点 2 时,由于关闭时间的不正常放大,节点 2 可能
会再一次出现在搜索路径中,形成非简单环路.

Fig.3 An example of wrong closing time
图 3 错误的关闭时间举例
根据关闭时间的定义可知,关闭时间是节点无法通往环路起点的最小时间值,即大于等于关闭时间的时间
戳都无法通往环路起点.一个点的关闭时间来自于由该点出发的时序边上的时间戳,而这个时间戳的选择是由
后续的搜索来决定的.对于一个点 i,若有一系列时序边通向 i,则只有时间戳小于点 i 关闭时间的边可以被当作
是合法的前序路径.因此,如果从某个点 j 指向点 i 的所有边的时间戳都大于等于 i 的关闭时间,则点 j 没有必要
向 i 进行搜索.显然,某个点的关闭时间越大,则通往该点的时间戳能通过的值越大.因此,由关闭时间的性质可
知:偏大的关闭时间会导致一部分无效的搜索;而偏小的关闭时间却会导致环路数量的错误,本不应该存在的环
路由于关闭时间的错误而产生.为了防止这样的错误发生,同时尽可能地利用剪枝搜索带来的好处,我们在搜索
过程中这样处理:当搜索到达要求的长度时,不通过完整的搜索我们无法得知最终是否能形成环路,但对于这样
的点,我们都默认可以形成环路,以此防止图 3 中的错误发生,同时尽可能保留剪枝技术.这样的处理会导致一部
分剪枝失效(在较差的情况下甚至起效很少,仅可以防止环路中节点的重复搜索),但是由于长度限制对搜索时
间的减少很大,虽然剪枝的作用有所降低,总体而言仍是一个合适的策略.
2
5
1
8,11
3
6
4
4
如图 4 所示,若要求找到所有长度不超过 5 的约束环.当前搜索路径为1⎯⎯→⎯⎯→⎯⎯→⎯⎯⎯→ ,此时,
点 5 向点 7 进行搜索,发现长度已经为 5,则搜索终止,并将 5 的关闭时间设置为 9,向点 6 进行搜索时同理.由于
并没有从点 6 和点 7 开始进行搜索,因此这两个点的关闭时间值仍然为程序初始化时设置的最大值.下次从点 4
1
3
2
4
6
7
9
4
向点 7 进行搜索,即搜索前缀为1⎯⎯→⎯⎯→⎯⎯→⎯⎯→ 时,搜索可以继续进行,最终获得合法的环路.

Fig.4 An example of constrained search
图 4 限制下的搜索举例