算法：連接器的優化

假設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

算法：連接器的優化

回答

相關問題