python - 在图中找到最短的三角形

Question

我有一组点，需要选择其中 3 个点的最佳子集，其中标准是点的某些属性和点对的某些属性的线性和。

在 Python 中，使用 itertools.combinations 非常容易:

all_points = combinations(points, 3)
costs = []
for i, (p1, p2, p3) in enumerate(all_points):
    costs.append((p1.weight + p2.weight + p3.weight
                  + pair_weight(p1, p2) + pair_weight(p1, p3) + pair_weight(p2, p3),
                 i))
costs.sort()
best = all_points[costs[0][1]]

问题是这是一个蛮力解决方案，需要枚举3个点的所有可能组合，点数为O(n^3)，因此很容易导致需要执行非常大量的评估.我一直在尝试研究是否有更有效的方法来做到这一点，或许可以利用成本函数的线性。

我已经尝试将其转换为具有节点和边权重的 networkx 图。但是，我还没有在该工具包中找到可以计算“最短三角形”的算法，尤其是同时考虑边和节点权重的算法。 (例如，最短路径算法往往只考虑边权重。)

有枚举所有团的函数，然后我可以选择 3 个团，并计算成本，但这也是蛮力，因此并不比用 combinations 做的更好。

我可以看看其他算法吗？

顺便说一句，如果我没有边权重，很容易只按节点权重对节点进行排序并选择前三个。因此，实际上是成对成本增加了这个问题的复杂性。我想知道我是否可以以某种方式列出所有对并找到形成三角形的那些对的前 k 个，或者更好的东西？至少，如果我能够有效地枚举最佳候选人并停止某些启发式的枚举，它可能比蛮力方法更好。

Answer 1

从现在开始，我将使用 n 作为节点数，使用 m 作为边数。如果你的图是完全连接的，那么 m 就是 n 选择 2。我也会忽略节点权重，因为正如你对初始帖子的评论所指出的那样，节点权重可以被吸收到它们所连接的边缘。

你的算法是O(n^3)；希望不难看出原因:您遍历每个可能的节点三元组。但是，可以在 O(m sqrt(m)) 中迭代图中的每个三角形:

for every node u:
    for every node v adjacent to u:
        if degree(u) < degree(v): continue;
        for every node w adjacent to v:
            if degree(v) < degree(w): continue;
            if u is not connected to w: continue;
            // <u,v,w> is a triangle!

此算法的 O(m sqrt(m)) 运行时间的证明非常重要，因此我将在此处指导您:https://cs.stanford.edu/~rishig/courses/ref/l1.pdf

如果您的图形是完全连接的，那么您必须坚持使用 O(n^3)，我认为。您可能有一些早期修剪的想法，但它们不会带来显着的加速，最多可能是 2 倍。