tar*_*sch 10 algorithm set packing np-complete hamming-distance
输入:图G输出:几个独立的集合,因此节点对所有独立集的成员资格是唯一的.因此,节点与其自己的集合中的任何节点都没有连接.这是一个示例路径.
由于在这里要求澄清另一个改写:
将给定的图形划分为多个集合
我可以通过集合中的成员资格告诉所有其他节点节点,例如,如果节点i仅存在于集合A中,则集合A中不应存在其他节点
如果节点j出现在集合A和B中,则集合A和B中不应存在其他节点.如果节点的成员资格由位模式编码,则这些位模式的汉明距离至少为1
如果图中有两个节点相邻,则它们不应出现在同一个集合中,因此是一个独立的集合
示例:B没有相邻节点D => A,A => D.
解:
A具有位模式10并且其集合中没有相邻节点.B有位模式11,没有相邻节点,D有01,因此所有节点的汉明距离至少为1,没有相邻节点=>正确
错了,因为D和A连接在一起:
A在其集合中具有位模式10和D,它们是相邻的.B具有位模式11而没有相邻节点,D具有11和B一样,因此在该解决方案中存在两个错误,因此不被接受.
当然,随着图表中节点数量的增加,这应该扩展到更多集合,因为您至少需要log(n)集合.
我已经在MAX-SAT中编写了一个转换,为此使用了一个sat-solver.但条款的数量只是很大.更直接的方法会很好.到目前为止,我有一个近似值,但我想要一个精确的解决方案或至少更好的近似.
我尝试过一种方法,我使用粒子群从任意解决方案优化到更好的解决方案.然而,运行时间非常糟糕,结果远非如此.我正在寻找动态算法或其他东西,但我无法理解如何划分和征服这个问题.
不是一个完整的答案,我不知道它对你有多大用处.但是这里:
海明的距离让我感觉像红鲱鱼.你的问题陈述说它必须至少为1但它可能是1000.只需说每个节点的集合成员资格的位编码是唯一的就足够了.
您的问题陈述没有说明,但上面的解决方案表明每个节点必须是至少一组的成员.即.对于任何节点的集合成员资格,不允许对所有0进行位编码.
暂时忽略连接的节点,不相交的节点很容易:只需使用未使用的位编码顺序编号.保存最后一个.
上面的例子使用了有向边,但同样,这让我感觉像是一只红鲱鱼.如果A不能与D在同一集合中,因为A => D,无论D => A,D都不能与A在同一集合中.
你提到至少需要log(N)集.您最多也有N套.完全连接的图(具有(N ^ 2-N)/ 2个无向边)将需要N个集合,每个集合包含单个节点.
事实上,如果你的图包含一个M维度的完全连通的单形(M in 1..N-1),其中M + 1个顶点和(M ^ 2 + M)/ 2个无向边,你将需要至少M + 1集.
在上面的例子中,你有一个这样的单形(M = 1),有2个顶点{A,D}和1个(无向)边{(A,D)}.
看起来您的问题归结为在图中找到最大的完全连接的单形.换句话说,您有一个路由问题:您需要多少个维度来路由边缘,以便没有交叉？它听起来不是一个非常可扩展的问题.
发现的第一个大单纯形很容易.每个顶点节点都有一个带有自己位的新集合.
不相交的节点很容易.一旦处理了连接的节点,只需对不相交的节点进行编号,顺序跳过任何以前使用的位模式.从上面的例子中,由于A和D取01和10,B的下一个可用位模式是11.
然后,棘手的部分变成如何在创建具有新位的任何新集合之前尽可能地将任何剩余的单一格式折叠到现有范围中.折叠时,每个节点必须使用2位或更多位(集),并且位(集)不得与任何相邻节点的位(集)相交.
考虑一下,如果将另一个节点C添加到示例中,上面的示例会发生什么:
如果C直接连接到A和D,则初始问题变为找到具有3个顶点{A,C,D}的2-simplex和3个边{(A,c),(A,D),(C,D) )}.一旦A,C和D取位模式001,010和100,不相交B的最低可用位模式为011.
另一方面,如果C直接连接A或D而不是两者,则图形具有两个1单形.假设我们找到带有顶点{A,D}的1-simplex,首先给出它们的位模式01和10,那么问题就变成了如何将C折叠到该范围内.至少有2位的唯一位模式是11,但是它与C连接的节点相交,所以我们必须创建一个新的集合并将C放入其中.此时,解决方案类似于上面的解决方案.
如果C是不相交的,则B或C将获得位模式11并且剩余的将需要新的集合并获得位模式100.
假设C连接到B但不连接到A或D.再次,该图有两个1-simplexes,但这次是不相交的.假设首先如上所述找到{A,D},给出A和D位模式10和01.我们可以将B或C折叠到现有范围内.该范围内唯一可用的位模式是11,B或C可以获得该模式,因为它们都不与A或D相邻.一旦使用11,就不会保留2位或更多位的位模式,我们将不得不创建剩余节点的新集合,为其提供位模式100.
假设C连接到所有3 A,B和D.在这种情况下,图形具有2个单形,具有3个顶点{A,C,D}和1个单形,具有2个顶点{B,C}.如上所述,在处理最大单形后,A,C和D将具有位模式001,010,100.为了将B折叠到该范围中,具有2位或更多位的可用位模式是:011,101,110和除101之外的所有这些都与C相交,因此B将得到位模式101.
那么问题就变成:你如何才能找到最大的全连通单形？
如果找到最大的完全连通的单纯形太昂贵,可以通过在连接方面找到最大最小值来对潜在的完全连接的单形进行近似上限:
扫过边缘,使用连接边的计数更新顶点.
对于每个连接的节点,创建一个Cn计数最初为零的数组,其中Cn是连接到节点n的边数.
再次扫过边缘,对于连接的节点n1和n2,增加对应于Cn2的n1中的计数,反之亦然.如果Cn2> Cn1,则更新n1阵列中的最后一个计数,反之亦然.
再次扫描连接的节点,计算每个节点可能是其中一部分的最大单纯形的上限.在扫过节点时,您可以构建一个鸽子洞数组,其中包含每个上限的顶点列表.
通过从最大到最小的提取和折叠节点的鸽笼阵列到独特的组合.
如果您的节点在集合N中并且您的边缘在集合E中,则复杂度将为:O(| N | + | E | + O(步骤5))
如果上述近似值足够,那么问题就变成了:在给定要求的情况下,如何将节点折叠到现有范围中？