在图中寻找最短三角形

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]]

问题在于这是一种暴力解决方案，需要枚举所有可能的三点组合，这在点的数量为n时的时间复杂度为O(n^3)，因此容易导致执行大量评估。我一直在努力研究是否有更有效的方法来解决这个问题，也许可以利用成本函数的线性性。

我试图将其转化为一个具有节点和边权重的networkx图形。但是，我还没有找到该工具包中可以计算“最短三角形”的算法，尤其是考虑边缘和节点权重的算法。（例如，最短路径算法通常只考虑边权重。）

有一些列出所有团的功能，然后我可以选择3-团，并计算成本，但这也是暴力方法，因此不比像上面那样使用combinations做的更好。

还有其他算法可以研究吗？

顺便说一下，如果我没有边缘权重，很容易只按节点权重排序并选择前三个点。所以真正增加了这个问题的复杂性是成对的成本。我想知道是否可以列出所有配对并找到构成三角形顶点的前k个顶点对，或者有更好的方法？至少如果我能够高效地枚举顶级候选项并在某些启发式停止枚举，这可能比暴力方法更好一些。

- Steve

---

也许由于您有一组点，可以进行德劳内三角剖分。这样做也许能帮助简化复杂度？ - Josip Juros

谢谢您提出的有关将节点权重分割为边权重的建议，这是一个好主意。也许最小k-团算法可以帮助解决问题，但我很遗憾没有找到这样的算法。(一些维基百科搜索告诉我，找到k-团可能充其量只能使用暴力算法，所以也许没有更好的方法。) - Steve

你的图是有向还是无向的？权重是整数吗？权重范围有多大？权重总是正数吗？是否已知子立方算法取决于这些问题的答案。 - kcsquared

有趣，谢谢我会仔细阅读。快速回答：权重不是整数，可以为负数。（节点权重为正数，边权重为负数...试图在这两个标准之间找到最佳值，最大化一个并最小化另一个）。至于大小，从技术上讲没有限制，但在我的情况下，节点权重是以米为单位的距离，最大约为10米，而边权重是角度差异。因此，在实践中它们是有限制的。我正在尝试选择3个点，使它们与某物的距离最小，并最大化它们之间的角度差异。 - Steve

听起来你确实有一个几何问题，如果你解释一下它的几何形状，你可能会更容易解决。将问题简化到最一般的形式是使它们更难解决的有效方法。 - Matt Timmermans

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倍速度。

- Jacob Steinebronn