item placement algorithm

Question

因此，我正在尋找一個確定項目位置的算法，但是，我很難將我的測量形式化爲位置的「優點」。

問題出在這裏：我有一組k項目，我想沿着一條線放置。每個項目都有一個寬度，沒有兩個項目可以重疊。每個項目也有一個相應的時間間隔 - 所有的時間間隔都是固定的，不重疊的，並且形成一段線段的分區。

我想放置每個項目，以便它在它的間隔居中，但我不能保證間隔比項目更寬。

因此，作爲一種折衷方案，我願意部分（或完全）將項目轉移出他們的間隔。但是，我不願意改變項目的順序（他們必須保持它們的間隔順序）。

根據我的（鬆散定義的）度量，是否有一個很好的算法來找到沿着這條線的項目的「最佳」放置？

Answer 1

嗯，這裏是也許是最簡單的方法，我可以理解你的問題的解決方案：

讓我們假設每個項目，我們考慮兩種可能性：

1. 我們在放置其意位置（間隔即中心）

2. 我們不

然後，我們可以將這個問題重新表達爲以下函數：找到可以放置在它們間隔中心而不重疊的項目的最大子集合。

這似乎是應該有一個貪婪的解決方案，但我必須承認，我能做的最好的是想出一個非常天真的動態編程算法。這裏是我如何制定的重現：

假設我們正在考慮第n個項目（從左邊開始），並且我們要分配它，使得此項目的左邊緣不會通過右邊的最前面所有前面的項目。然後，它必須是真正的最佳分配滿足：

best_align(n, right) = 
    if center[n]-radius[n] > right[n]: 
      max(best_align(n+1, right+radii[n], 1+best_align(n+1,center[n]+radius[n]) 
    else: 
      best_align(n+1, right+radius[n]) 

這有一個明顯的DP解決方案，我編碼了（在Python中）。結果如下：

#Assumes that the items are sorted left-to-right by their centers 
def best_align(radii, centers): 

    assignments = { (radii[0]+centers[0]):[0], (-100000):[] } 

    for i in range(1, len(radii)): 

     nc = centers[i] + radii[i] 
     nassignments = { nc : [i] } 

     for right, assigned in assignments.items(): 

      #Handle case where object is not inserted 
      nr = right+radii[i] 
      if not nr in nassignments or len(assigned) > len(nassignments[nr]): 
       nassignments[nr] = assigned 

      #Handle inclusion case 
      if right <= centers[i]-radii[i] and len(assigned) >= len(nassignments[nc]): 
       nassignments[nc] = assigned + [i] 


     assignments = nassignments 

    return max([ (len(l), l) for l in assignments.values() ])[1] 

可變半徑是各種項目的半徑，而中心是目標分配位置。該算法返回可放置在期望位置的項目的最大子集。剩下的項目必須儘可能地儘可能地被模糊。例如，這裏有一些輸出：

在[11]：plc.best_align（[1,5，1]，[0，2，3]）

缺貨[11]：[2 ]

又如：

在[18]：plc.best_align（[1，10，1，1，1，1，1]，[0，2，4，6， 8，10，12]）

Out [18]：[2,3,4,5,6]

這個實現的時間複雜度是三維的，因爲處理這些分配集合的方式很幼稚。人們可以很容易地優化，通過將python列表替換爲之前列出的列表（儘管它會使演示文稿更加糟糕）來獲得二次方案。

Answer 2

這聽起來像是一個鬆散耦合的約束系統。粗略地說，您可以通過深入優先搜索相關約束元素的約束來找到「最佳」佈局（不保證是「最好」的，但應該是「功能性」的）。

讓我來形容。對於第一次運行，嘗試將所有元素放在它們的間隔中間。檢查以查看重疊的對象。當遇到重疊物體時，暫時將該物體移離重疊區域;檢查系統是否有重疊。重複所有重疊。

這將根據間隔的順序保留對象的順序。如果需要這樣的事情，應該可以用每個迭代的值來「評分」每個迭代的值，使其與間隔的差異量最小化，以嘗試最小化間隔的距離。