algorithm - 复杂的多对多关系？

Question

我正在从事一个具有复杂数据结构的项目，我不确定如何解析。我一直在尝试构建一个解决方案，但我提出的每个想法都感觉它不会有 100% 的准确性。如果已经存在一种众所周知且经过测试的方法，那么我可以依赖它。

下面是一个例子:

假设一家商店有一个促销列表，每个促销都有自己的列表，说明它是否可以与其他促销联系起来。我需要想出一堆可以相互联系的促销事件，而不是遗漏任何促销事件。

假设我有促销事件 A、B、C、D。我会得到一个列表，告诉我哪些促销事件与哪些促销事件叠加:

A -> B = S(可堆叠)

A -> C = N(不可堆叠)

A -> D = S

B 也有它的列表，D 也有它的列表。我不能假设没有 N 就意味着它是可堆叠的，但我可以假设没有 S 就意味着它不可堆叠。可能有从 1 到无限的促销事件。

我需要确保获得所有可能的促销组合。最后，我需要一个包含所有组合(最好是唯一组合)的数组，但如果列出每个组合，即使是非唯一的也可以。如果你知道这样一个问题的名称，你可以只用名称来回答，你不需要编辑我的问题，一个名称就足以让我自己在谷歌上搜索更多。

Answer 1

我认为这可以表述为 clique problem .

您需要构建一个图，其中促销是顶点，如果促销可以堆叠，则两个顶点之间有一条边。一个可能的提升现在是一个完整的子图或一个团，这是一个子图，其中每个顶点都连接到子图中的其他顶点。

这是一个 NP 完全问题，但如果您的系统不是太大，解决它应该是可行的。

蛮力算法非常简单。有两种特殊情况。

1. 首先所有的顶点都是团(每个单独的提升)
2. 连接两个顶点的所有边都是团(两个提升的列表)

然后休息

k = 2 .. (number of vertices)
  v in vertices
    if (v.neighbors.size >= k)
      s in distinct combination of k neighbors of v and v 
        if each vertex in s has a link to other vertices in s add s to the list

从算法中可以看出，随着组合数量呈指数增长，如果有很多链接，速度会变慢。