算法:连接器的优化

Question

假设有n 3D 空间中的不同点，即 P1, P2, P3, ..., Pn .

定义一个连接器，C ，作为一组有序的线段，其中集合中的下一个元素应与前一个元素共享一个公共(public)顶点。例如，{ P1-P2, P2-P4, P4-P7 }是连接器，而 { P1-P2, P3-P4,P4-P2 }不是。

定义连接器的内容，作为连接器包含的点集。

定义连接器的大小，即连接器中最长的单个线段的长度。

如果最长的单个段是连接器中的第一个或最后一个段，则将连接器定义为正确的连接器。

如果点上的连接符内容的并集是点集，则称点集是连通的。

问题是:

鉴于k相同数量级的正确连接器(k < n)m允许连接 n给定坐标的点最小化 m .

算法的要点应该是什么？我不知道从哪里开始。

Answer 1

一个想法是从最远的点开始，即它最近的邻居与其他点的邻居相比最远。然后从中构建一个连接器，始终添加下一个点的最近邻居，直到您在不违反以下规则之一的情况下无法添加更多点:

• 连接器不能有回路(一个点只能访问一次)
• 正确的连接器不能有比第一个连接器更大的边缘

注意:最后一个条件太强了，因为可以允许适当连接器的最后一个边缘大于第一个边缘，但我考虑到该算法还会对这样的“最后”边缘进行另一次尝试作为第一条边，但方向相反:所以我可以在此阶段排除该边。

一旦找到合适的连接器，算法就会回溯并尝试朝另一个方向分支，再次尽可能远。这种递归分支将导致一组适当的连接器。如果该集合至少有 k 个连接器，并且所有点都被至少一个这样的连接器覆盖，那么这是一个解决方案。

如果这行不通，可以重复整个逻辑，但这次第一条边必须有更大的尺寸。因此，将找到一个点，其中到其最近邻居的距离(至少具有该距离)被最大化。

下面是这种算法的更正式的草图:

Pre-processing:
    List for each point all the other points in order of increasing distance from it.

    set m = 0

Repeat:
    set max_dist = 0, list = empty
    For each point p:
        Find the first neighbor q for which distance(p,q) > m
        if distance(p,q) >= max_dist:
            if distance(p,q) > max_dist:
                clear list
            append (p,q) to the list

    let m = max_dist
    For each pair (p,q) in the list (all these pairs have same distance m):
        Let result = []
        Let connector be [p,q]
        Let p = q

        Recursive part (p):
            let end_point = True
            For each neighbor q of p (in order of distance):
                If distance(p,q) > m: 
                    break loop
                If q not in connector:
                    let end_point = False
                    Append q to connector
                    Call the recursive part for q
                    size(result) >= k and all points are in result:
                        exit recursion
                    Remove q from connector (backtracking)

            If end_point:
                append clone of connector to result

        If size(result) >= k and all points are in result:
            return m, as final result