我試圖找到一種將一組范圍放在更大范圍內的最佳方法。我喜歡把它想象成可以左右移動的扁平盒子。需要考慮的一些事項：
- 有 N 個盒子，每個盒子都有一個中心點 Ci。
- 有 N 個吸引點（每個盒子一個），我們可以稱它們為 Pi。每個盒子被一個吸引點吸引，力與距離成正比。
- 盒子的順序是固定的。吸引點和盒子的順序是一樣的。所以 C1 被 P1 吸引，C2 被 P2 吸引，等等。
- 框不能重疊。
我做了一個圖表，可能更容易理解：
問題是，我可以使用什么演算法來移動框，以便每個 Ci 盡可能接近其各自的 Pi。換句話說，我如何找到最小化所有 Ci-Pi 對之間距離 (Li) 的 Ci 點的位置？
如果您能指出一些要閱讀的材料或其他東西，我也會有所幫助，我對這類問題不是很熟悉......我的猜測是某種力導向演算法會起作用，但我我不知道如何實作這些。
uj5u.com熱心網友回復：
編輯：這是一個粗略的解決方案，以最小化 all 的總和Li，這不再是問題。
讓我們將盒子命名為 B，Bicenter也是如此Ci。讓n是盒子和點的數量。假設所有的盒子都可以適應更大的范圍，我會這樣做：
設Q(a, b)為Pifromi=a到的平均值i=b。
將所有盒子彼此相鄰（按順序）放置以形成一個超級盒子，使該超級盒子的中心位于Q(1, n)。如果它超過了較大范圍的一端，請將其移動到極限位置。
然后，對于每個Bi，在不移動其他框的情況下將其盡可能靠近Pi（并且仍然在更大的范圍內）。重復直到你不能再移動任何盒子。
現在，最小化所有總和的唯一方法Li如下。
讓我們G成為一組觸摸的盒子。設F(G)謂詞：如果一個系列的中心框是Biand Bj（如果系列中有奇數個框，i=j），那么Ci != Piand Cj != Pj。
找到一個G為F(G)真的，并移動相應的框，使之F(G)變為假。如果這組盒子在移動時撞到了另一個盒子，則將該盒子添加到該組中并重復。當然，不要將任何框移到更大范圍之外。
一旦沒有G哪個F(G)是正確的或您需要移出更大范圍的，您就有了解決方案（可能是無限數量的一個）。
uj5u.com熱心網友回復：
由于“每個盒子都以與距離成比例的力被吸引到一個吸引點”，您正在描述一個系統，其中盒子通過彈簧連接到吸引點（參見胡克定律），并且您想要確定系統靜止（最小勢能狀態）。
因為力與距離成正比，所以您想要最小化距離平方的總和，或Li^2從i=0到的總和i=n。這是一個演算法來做到這一點。
這個想法是對最終需要觸摸的盒子進行分組，并根據它們對應的吸引點來確定它們作為一個組的位置。
第一步是不要找到這些組，因為我們實際上可以先從一個大組開始，然后在必要時將其洗掉。為簡單起見，讓我們將所有都Li視為有符號距離。所以Li = Ci-Pi。讓我們也命名盒子的尺寸，盡管處理半尺寸會更容易。所以讓我們Si成為第 i 個盒子的一半大小。最后，讓我們寫出Xifromi=a到i=blike的總和sum[a,b](Xi)。
下面是如何計算一組盒子的位置，假設每個盒子都接觸下一個盒子。Li是組位置的函式：如果x是那個位置，Li(x) = Ci(x) - Pi（其中Ci(x)只是x加上一些常數）。x可以是該組框的點，例如第一個框的左邊緣。
我們也知道sum[a,b](Li(x)^2)必須是最小的。這意味著該和的導數必須為零：sum[a,b](2*Li(x)) = 0。所以：
sum[a,b](2*Li) = 0
sum[a,b](Li) = 0
sum[a,b](Ci - Pi) = 0
sum[a,b](Ci) = sum[a,b](Pi)
計算sum[a,b](Pi)很簡單，sum[a,b](Ci)可以用Ca（第一個框的中心）表示，因為C[i 1] = Ci Si S[i 1].
現在您可以計算一組框的位置，首先使用由所有框組成的組，然后從該組中洗掉框，如下所示。
從左邊開始，考慮所有帶有 的框Li > 0并計算Q = sum(Li)所有對應的i。類似地，從右邊開始，考慮所有具有Li < 0和計算R = -sum(Li)所有對應的框i（注意負號，因為我們想要絕對值）。現在，如果Q > R，洗掉左側的框并與它們組成一個新組，否則洗掉右側的框并與它們組成一個新組。
您不能同時創建這兩個新組，因為從一端移除框會改變原始組的位置，而您從另一端移除的框不應被移除。
如果您創建了一個新組，請重復：計算每個單獨的框組的位置（此時它們永遠不會重疊），并在必要時洗掉框。否則，你有你的解決方案。
uj5u.com熱心網友回復：
目標似乎是二次函式，所有約束都是線性的。所以我認為你可以通過標準的二次規劃求解器來解決它。如果我們寫S_i為第 i 個盒子的一半大小，并且給出了 Pi，那么：
Minimize y
with respect to C_1, C_2, ...C_n
subject to
y = sum_i (P_i - C_i)^2
C_i S_i S_{i 1} <= C_{i 1} for each i = 1, ... n-1
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/510092.html
標籤：算法几何学范围
上一篇：如何根據日期合并排序？
下一篇：樹遍歷到第n個節點