算法：连接器的优化

假设3D空间中有不同的点，即P1, P2, P3, ..., Pn。算法：连接器的优化

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

将连接器的内容定义为连接器包含的一组点。

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

如果最长的单个段是连接器中的第一个或最后一个段，请将连接器定义为适当的连接器。

如果点上的连接器的内容联合是点集，则称一组点连接。

的问题是：

所用的相同幅度m的k适当的连接器（k < n）被允许连接n点，其坐标提供，尽量减少m。

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

来源

2016-09-24 user122049

可以在相同的连接器内重新访问边缘，可能是在相同的方向？像'a-> b-> c-> b-> d-> a-> b-> e'？ – trincot

它不能。假设一个连接器不应该有重复的顶点。 – user122049

这个命令是否重要？例如，我可以连接“{P1P5，P5P2，P2P3}”吗？ –

一个想法是从最远的点开始，即它的最近邻居与其他点的邻居相比是最远的。然后生成一个连接器，一直在增加下一个点的近邻，直到你不能没有打破这些规则之一添加更多的点：

连接器不能有循环（一个点只能访问一次）
一个适当的连接器不能有一个边缘比所述第一个

NB较大：最后一个条件太强，因为适当的连接器的最后边缘可以被允许为大于第一，但我考虑到该算法也会用第一个边缘这样的“最后”边缘做另一次尝试，但是在oppo现场方向：所以我可以在这个阶段排除这个边缘。

一旦找到合适的连接器，算法可能会回溯并试图在另一个方向上分支，并且尽可能地再次分开。这种递归分支将导致一组适当的连接器。如果该组至少有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

来源

2016-09-24 11:12:42 trincot

为什么你每次选择添加最近的邻居，而不是只有不比第一个分段更远的邻居？ –

您对，@גלעדברקן，他们都应该考虑，但我认为我这样做在伪代码在'对于递归部分内的每个p的邻居q'。 – trincot

一些一般性的想法。您的问题可能有多种解决方案。我会先考虑一个暴力方法，然后考虑是否可以改进该算法。另一个好方法是找到一个更容易解决的类似问题，并尝试将其转换为类似的问题。由于你不在问题中，所以我不会涉及正确性和时间复杂性。

蛮力通常意味着尝试每个组合。构建涵盖所有节点的所有可能的连接链。

一个贪婪算法：从一个随机节点开始。创建一个连接器到最近的节点。然后创建一个从该节点到最近的节点的连接器，该节点尚未连接。重复，直到所有节点都连接。这可能不会总是给出最佳结果。

迭代方法：使用任何方法连接所有节点。然后尝试交换节点。选择具有最高幅度和Q值的连接器的节点B，连接器AB，BC和PQ，QR。生产AQ，QC和PB，BR并保持交换，如果它们的数量减少。可能使用线性编程。

来源

2016-09-24 12:54:49 David

算法：连接器的优化

回答

相关问题