如何連接一組孤立的頂點

在一個平面上給定一組頂點，選擇一個點作爲入口，入口附近的一個點作爲出口，我應該如何連接它們以使任意兩個連續點的邊不會更大超過某個最大值？如下所示，*代表頂點，給定點爲In，比從入口附近的點退出，是否有任何算法可以做到這一點？幫幫我？如何連接一組孤立的頂點

* * * * * * * * * * 
* * * * * * * * * * 
* * * * * * * * * * 
* * * * * * * * * * <------ in 
* * * * * * * * * * 
* * * * * * * * * * <------- out 
* * * * * * * * * * 
* * * * * * * * * * 
* * * * * * * * * * 
* * * * * * * * 
* * * * * * * * *

來源

2015-07-13 Mingguo Peng

你試過蠻力嗎？另外，你的問題陳述還不清楚。正常網格上的點還是隨機分佈的？你想連接所有點嗎？邊緣是否允許交叉？給定的入口和/或出口還是算法選擇它們？最後，這個問題真的是一個編程問題嗎？ – kazemakase

@kazemakase，對不起，我的誤導，是的，點是在一個規則的網格，我必須連接所有點。邊緣被允許交叉。入口點是手動選擇的，出口點應在算法入口附近選擇。實際上，我是一位IC物理設計工程師，我在佈局中有很多單元，我想通過金屬層連接它們。肯定這是一個編程問題 –

使用breadth first search：

# Input: G (set of vertices), v (entry vertex) 
    procedure BFS(G,v) is 
     let Q be a queue 
     Q.enqueue(v) 
     label v as discovered 
     while Q is not empty 
     v ← Q.dequeue() 
     process(v) 
     for all edges from v to w in G.adjacentEdges(v) do 
      if w is not labeled as discovered 
       Q.enqueue(w) 
       label w as discovered

G.adjacentEdges(v)將搜索是足夠接近，但還沒有被發現的頂點。 process(v)將測試v是否是退出頂點。每個頂點也必須記住它是如何從入口頂點到達的。

來源

2015-07-13 09:22:30 Oswald

感謝您的建議，但所有的頂點都是孤立的，它們沒有連接，我想連接它們以生成一條從入口到出口的線。你有什麼建議嗎？ @Oswald –

他們可能沒有連接，但他們有距離（正如您的陳述所暗示的那樣，*任意兩個連續點的邊緣不會超過某個最大值*）。爲了廣度優先搜索的目的，這可以被解釋爲*具有連接*。 – Oswald

無論如何，既然你澄清，你需要連接**所有**頂點，你應該去kazemakase的解決方案。 – Oswald

如果點放置在一個規則的網格上，並且沒有點缺失，則解決方案相對簡單（A，B，C）。如果網格同時具有奇數行和奇數列，並且點之間的對角距離大於最大允許距離（D），則可能會出現問題。

enter image description here

您可能還需要檢查出的Moore curve或space-filling curves一般來說，如果你有興趣的可能的解決方案的理論性能。

我認爲問題變得相當複雜，如果點不是均勻分佈的，或者網格上的所有位置都沒有被佔用。

來源

2015-07-13 11:16:16 kazemakase

哇，謝謝@kazemakase，「如果點不是均勻分佈的，或者並非網格上的所有位置都被佔用，我認爲問題變得相當複雜。」那麼，情況就是這樣，有些位置可能會打開，謝謝你的信息，我會試一試， –

@MingguoPeng你可以簡單地假裝位置沒有打開，但這可能會違反你的最大距離限制。 – kazemakase

如何連接一組孤立的頂點

回答

相關問題