ruby – 我的天真最大团队发现算法比Bron-Kerbosch的运行速度更
发布时间:2020-12-16 21:11:39 所属栏目:百科 来源:网络整理
导读:简而言之,我的天真代码(在 Ruby中)看起来像: # $seen is a hash to memoize previously seen sets# $sparse is a hash of usernames to a list of neighboring usernames# $set is the list of output clusters$seen = {}def subgraph(set,adj) hash = (set
简而言之,我的天真代码(在
Ruby中)看起来像:
# $seen is a hash to memoize previously seen sets # $sparse is a hash of usernames to a list of neighboring usernames # $set is the list of output clusters $seen = {} def subgraph(set,adj) hash = (set + adj).sort return if $seen[hash] $sets.push set.sort.join(",") if adj.empty? and set.size > 2 adj.each {|node| subgraph(set + [node],$sparse[node] & adj)} $seen[hash] = true end $sparse.keys.each do |vertex| subgraph([vertex],$sparse[vertex]) end 我的Bron Kerbosch实施: def bron_kerbosch(set,points,exclude) $sets.push set.sort.join(',') if set.size > 2 and exclude.empty? and points.empty? points.each_with_index do |vertex,i| points[i] = nil bron_kerbosch(set + [vertex],points & $sparse[vertex],exclude & $sparse[vertex]) exclude.push vertex end end bron_kerbosch [],$sparse.keys,[] 我还实现了旋转和简并排序,这减少了bron_kerbosch执行时间,但还不足以超越我的初始解决方案.这种情况似乎是错误的;我错过了什么算法见解?如果您需要查看完整的代码,这里有一个更详细的writeup.我已经在伪随机集上测试了这个,其大小达到了一百万左右. 解决方法
我不知道你如何为测试生成随机图,但我想你使用的函数根据均匀分布生成一个数字,从而得到一个非常均匀的图.当在图上测试算法时,这是一个常见问题,创建好的测试用例非常困难(通常和解决原始问题一样困难).
max-clique问题是一个众所周知的NP难题,两种算法(天真的和一个Bron Kerbosch)具有相同的复杂性,所以我们不能指望所有测试用例的全局改进,而只是对某些特定情况的改进.但是因为您使用统一分布来生成图形,所以您没有这种特殊情况. 这就是为什么两种算法的性能在您的数据上非常相似的原因.而且因为Bron Kerbosch算法比天真的算法稍微复杂一点,所以天真的算法更快. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |