Gig*_*egs 5 javascript php algorithm math graph
Drake和Hougardy找到了最大加权匹配问题的简单近似算法.我认为我对学术论文的理解超出了我的能力,所以我正在寻找一个简单的实现,最好在php,c,javascript中？
har*_*ath 10
问题定义和参考
给定一个简单的图形(无向,没有自边,没有多边),匹配 是边的子集,使得它们中没有两个入射到同一个顶点.
一个完美的匹配是一个所有顶点入射到匹配的边缘,如果有奇数个顶点的东西是不可能的.更一般地,我们可以要求最大匹配(匹配中最大可能的边数)或最大匹配(不能添加更多边的匹配).
如果将正实数"权重"分配给边缘,我们可以概括问题以要求最大加权匹配,最大化边缘权重之和.确切的最大加权匹配问题可以在O(nm log(n))时间内求解,其中n是顶点数,m是边数.
请注意,最大加权匹配不一定是完美匹配.例如:
*--1--*--3--*--1--*
只有一个完美匹配,总重量为2,最大加权匹配总重量3.
在这些论文中可以找到关于这些的精确和近似解以及最小加权完美匹配问题的讨论和进一步参考:
"加权匹配问题的简单近似算法" Drake,Doratha E.和Hougardy,Stefan(2002)
O(nm log n)加权匹配的实现数据结构的 力量Melhorn,Kurt和Schäfer,Guido(2000)
计算最小权重完美匹配 Cook,William和Rohe,André(1997)
近线性时间近似最大权重匹配 Duan,Ran和Pettie,Seth(2010)
Drake和Hougardy的简单逼近算法
Drake-Hougardy的第一个近似算法使用了在每个顶点遇到的局部最重边缘生长路径的想法.它具有1/2的"性能比",如贪婪算法,但是边缘数量的线性时间复杂度(贪婪算法使用全局最重的边缘并且导致更大的时间复杂度来找到它).
主要实现任务是识别有效支持其算法步骤的数据结构.
PathGrowing算法的想法:
Given: a simple undirected graph G with weighted edges
(0) Define two sets of edges L and R, initially empty.
(1) While the set of edges of G is not empty, do:
(2) Choose arbitrary vertex v to which an edge is incident.
(3) While v has incident edges, do:
(4) Choose heaviest edge {u,v} incident to v.
(5) Add edge {u,v} to L or R in alternating fashion.
(6) Remove vertex v (and its incident edges) from G.
(7) Let u take the role of v.
(8) Repeat 3.
(9) Repeat 1.
Return L or R, whichever has the greater total weight.
表示图形和输出的数据结构
由于"集合"在任何直接意义上都不是C的数据结构,我们需要确定边缘和顶点的容器类型将适合这种算法.关键操作是以一种允许我们找到是否留下任何边缘的方式去除顶点和入射边缘,并比较入射到给定顶点的剩余边的权重.
边缘需要是可搜索的,但只能查看是否仍有任何边缘.人们首先想到一个简单的边缘链表,没有任何特殊的顺序.但是这个列表也需要通过基本上随机的删除来维护.这表明双链表(反向链接以及每个节点处的前向),因此可以通过修复链接以跳过任何"已删除"节点来完成边缘的删除.边缘权重也可以存储在同一结构中.
此外,我们需要能够扫描入射到给定顶点的所有(剩余)边缘.我们可以通过为事件边缘的(指针)的每个顶点创建链接列表来实现此目的.我将假设顶点已经被预处理为序数值,这些值可以用作指向这些链接列表的指针数组的索引.
最后,我们需要表示边集L和R,其中一个将作为近似最大匹配返回.我们的要求是能够将边缘添加到任一组,并且能够为它们两者总计边缘权重.具有动态分配的节点的链接列表可以用于此目的,可能存储指向原始双向链表中的边节点的指针,因为即使在边缘被链接操纵"移除"之后,权重属性仍将保持在那里.
这样的链接和双链表可以在与边数成比例的时间内创建,因为双链表项可以分配给输入上的特定于顶点的链接.考虑到这样的设计,我们可以分析算法的每个步骤所需的工作量.
(未完待续)