- xml - AJAX/Jquery XML 解析
- 具有多重继承的 XML 模式
- .net - 枚举序列化 Json 与 XML
- XML 简单类型、简单内容、复杂类型、复杂内容
简而言之,我的原始代码(用 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 算法比朴素算法稍微复杂一点,所以朴素算法更快。
关于ruby - 我天真的最大团发现算法比 Bron-Kerbosch 的运行得更快。怎么了?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5149477/
Bron–Kerbosch algorithm是一种列出图的所有最大派系的方法。我最近成功地实现了这个算法只是为了好玩。缺点是该算法是递归的,因此只能在小图上运行,直到堆栈溢出。 应该可以使算法完全迭
我正在尝试理解 Bron-Kerbosch 的算法(带旋转)以在无向图。我有一些问题: 选择枢轴顶点有什么标准吗?我已经看到一些实现选择具有最多邻居的顶点进行优化,而其他实现则简单地选择预期顶点中的第
我在实现 Bron-Kerbosch 算法的 C 版本时遇到了一些问题: 1- 我完全不了解该算法的工作原理。我试图在 Internet 上找到引用资料,但所有这些引用资料都很糟糕,算法示例实现糟糕透
任何人都可以告诉我,我可以在网络上的哪个位置找到有关 Bron-Kerbosch 算法的解释以查找派系或在此处解释其工作原理? 我知道它发表在“算法 457:查找无向图的所有团”一书中,但我找不到描述
我目前正在尝试在 Bron-Kerbosch 算法的 Clojure 实现中正确有效地使用集合和 clojure.set 命名空间,但遇到了困难。 我正在尝试重构我当前的实现 (defn BK [r
我一直在练习我的 C++ 算法知识,并卡在了标准 BK 实现上。该算法输出了太多派系,我似乎不明白为什么。我将图形表示为邻接表: vector > adjacency_list; 我的 BK 函数如下
简而言之,我的原始代码(用 Ruby 编写)如下所示: # $seen is a hash to memoize previously seen sets # $sparse is a hash of
对于一个大学项目,我正在尝试实现 Bron–Kerbosch algorithm ,即列出给定图中的所有最大团。 我正在尝试实现第一个算法(不旋转),但我的代码在 Wikipedia's exampl
我正在寻找 Bron-Kerbosch algorithm 的 Javascript 实现或 Girvan-Newman algorithm . 基本上,我想在无向图中为最大集团/社区着色。 遗憾的是
我一直在尝试实现 Bron-Kerbosch algorithm在 Rust 中为我的硕士论文。到目前为止一切正常,但是当我尝试从 BTreeSet 更改时到 HashSet出于性能比较的目的,行为变
我是一名优秀的程序员,十分优秀!