用於在形狀內分佈線的優化算法的選擇

Question

考慮具有鋼筋和孔的混凝土板元件的以下表示。

我需要一種算法，在具有不同的孔的任意形狀自動分配線。

的主要限制是：

1. 線不能是區域的外側或一個孔的內部
2. 兩個側由端線之間的距離不能超過一個可變D
3. 線上必須定位在固定間隔I，即y mod I = 0，其中y是行的Y座標。
4. 形狀內的每個可用的點不能由管線進一步比D/2

我想通過最小化線Ñ的總數，以優化的解決方案。什麼樣的優化算法適合這個問題？我假設大多數方法涉及到將光柵形狀簡化爲像素高度（像素高度爲I），並禁用或啓用每個像素。我認爲這是一個明顯的LP問題，並試圖用GLPK進行設置，但發現很難用這個簡化的光柵來描述任意數量的行。我也懷疑解決方案空間可能太大。

我已經在C＃中實現了一個算法，可以完成這項工作，但並不是非常優化。這是如何工作的：

1. 創建幾何
2. 的簡化光柵計算用於使用複雜的公式，可能需要的線路長度和距離其它杆和障礙考慮每個小區的分數。
3. 確定哪些需要加強（其中y方向>d遊離細胞數）
4. 接與需要加強最高分數的細胞，並儘可能在-x加強它和+ X方向
5. 重複

根據複雜的公式，這個效果很好，但開始把最後幾行的時候給予不想要的結果，因爲它不能移動已經放線。 有沒有其他的優化技術，我應該看看？

Answer 1

我不確定接下來會發生什麼 - 我相當確定這不是你想到的 - 但如果聽起來合理，你可以試試看。

因爲距離至多爲d簡單，並且可以是任何小於，似乎乍一看像一個貪心算法應該在這裏工作。總是放置下一行，以便（1）儘可能少，（2）儘可能遠離現有線路。

假設你有這個問題的最優算法，並放置在距離a <= d從最後一行的下一行（S）。說它放置b行。我們的貪心算法肯定會放置不超過b線（因爲第一個標準是把儘可能少的），如果它把b線將它們放置在距離c與a <= c <= d，因爲它然後將這些線就可能。

如果貪心算法沒有做優化算法做了什麼，它在不同的下列方式之一：

1. 它放置在相同或更少的行得更遠。假設最佳算法在距下一步距離a'處放置b'行。然後這些線將在距離a+a'處，並且總共將有b+b'線。但貪婪算法可以通過選擇c' = (a+a') - c將b'行置於位移a+a'處模擬最佳算法。由於c > a和a' < d,c' < d這是合法的安置。

2. 它將更少的線放在一起。這種情況實際上是有問題的。可能的是，這個地方k不必要的行，如果任何放置需要至少k線和所述最遠的那些需要更多的，並且被選擇的孔的佈置，使得（例如）它跨越的距離爲d的倍數。

因此，貪婪算法在情況2下結果不起作用。但是，在其他情況下它確實不起作用。特別是，我們在第一種情況下的觀察是非常有用的：對於任何兩個展示位置(distance, lines)和(distance', lines')，如果distance >= distance'和lines <= lines'中，第一落點總是首選。這表明，下面的算法：

PlaceLines(start, stop) 

    // if we are close enough to the other edge, 
    // don't place any more lines. 
    if start + d >= stop then return ([], 0) 

    // see how many lines we can place at distance 
    // d from the last placed lines. no need to 
    // ever place more lines than this 
    nmax = min_lines_at_distance(start + d) 

    // see how that selection pans out by recursively 
    // seeing how line placement works after choosing 
    // nmax lines at distance d from the last lines. 
    optimal = PlaceLines(start + d, stop) 
    optimal[0] = [d] . optimal[0] 
    optimal[1] = nmax + optimal[1] 

    // we only need to try fewer lines, never more 
    for n = 1 to nmax do 

     // find the max displacement a from the last placed 
     // lines where we can place n lines. 
     a = max_distance_for_lines(start, stop, n) 

     if a is undefined then continue 

     // see how that choice pans out by placing 
     // the rest of the lines 
     candidate = PlaceLines(start + a, stop) 
     candidate[0] = [a] . candidate[0] 
     candidate[1] = n + candidate[1] 

     // replace the last best placement with the 
     // one we just tried, if it turned out to be 
     // better than the last 
     if candidate[1] < optimal[1] then 
      optimal = candidate 

    // return the best placement we found 
    return optimal 

這可以通過記憶化通過把結果(seq, lines)成(start, stop)索引緩存來改善。這樣，我們就可以識別出我們何時試圖計算可能已經評估過的任務。我希望我們會遇到這種情況，無論你是否對問題實例使用粗略或精細離散化。

我沒有詳細討論如何使用max_lines_at_distance和max_distance_for_lines函數，但也許是關於這些函數的一個詞。

第一個告訴你在給定的位移很多線路都需要如何跨越幾何形狀。如果將幾何圖形和彩色孔像素化爲黑色，則這意味着在指定的位移處查看單元格行，並考慮連續的黑色線段，並從中確定所需的線條數。

第二告訴您，對於線的給定的候選號，從目前的位置處線的該數量可以被放置在最大距離。您可以通過告訴您可以放置​​該行數的最大距離或更少來使其更好。如果你使用這種改進，你可以扭轉在你迭代n和方向：

1. 如果f(start, stop, x) = a和y < x，你只需要搜索最多a，不stop，從那時起;
2. 如果f(start, stop, x)未定義，並且y < x，則不需要再搜索。

注意，如果這是不可能的地方n或更少的線start和stop之間的任何該功能可以是不確定的。

另請注意，您可以單獨記憶這些功能以節省重複的查找。您可以爲每一行預先計算max_lines_at_distance並將其存儲在緩存中供以後使用。然後，max_distance_for_lines可能是一個循環，在兩個邊界內檢查緩存。