包裝時隙的算法

我有一組具有開始和結束時間的事件。我想使它們只要盒在一系列的行沒有重疊，這樣的事情包裝時隙的算法

00:00 01:00 02:00 03:00 04:00 05:00 06:00 07:00 08:00 
--|--------|--------|--------|--------|--------|--------|--------|--------|-- 
     AAAAAAAAAAAA BBBBBB  CCCCCCCCCCCCCCCCCCCC  DDDDDDDDDDDD 
--|--------|--------|--------|--------|--------|--------|--------|--------|-- 
     EEEEEEEEEEEEEE  FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 
--|--------|--------|--------|--------|--------|--------|--------|--------|-- 
      GGGGGGGGGGGGGGGGGGG   HHHHHHHH  IIIIIIIIIIIII 
--|--------|--------|--------|--------|--------|--------|--------|--------|--

任何特定的盒子中，以任何特定行的分配並不重要。我想要的是一個算法，將這些箱子打包成最小的行數。

有沒有一個已知的算法呢？

來源

2014-09-05 spraff

對我來說，這似乎是[子集和問題]（https://en.wikipedia.org/wiki/Subset_sum_problem）的變體。 – ThreeFx 2014-09-05 09:51:51

國際時間表比賽2007有一個課程安排跟蹤和考試調度軌道。許多研究人員參加了那場比賽。大量的啓發式和metaheuristics嘗試，但在結束本地搜索metaheuristics（如禁忌搜索和 模擬退火）明顯擊敗其他算法（如遺傳算法）。

看看由一些入圍用2個開源框架：

JBoss的OptaPlanner（Java的，開放源碼）Unitime（Java的，開放源碼） - 多爲大學

- 傑弗裏·迪斯：Algorithm for creating a school timetable

參考：

來源

2014-09-05 11:28:54 Margus

這不幸地解決了與OP中所述不同的問題。如果開始和結束時間與原始問題一樣固定，則不需要使用組合優化。該解決方案適用於開始時間和結束時間不固定的情況，而只是各個時隙的長度，並且必須儘可能高效地打包。 – 2014-09-08 11:47:50

我只會貪婪地將它們打包（從左到右，並將事件添加到第一個軌道的上下方向）。它速度快，確定性強，很可能在實踐中產生良好效果。

來源

2014-09-05 10:41:57

幾年前我嘗試過，發現它經常很浪費。 – spraff 2014-09-05 11:10:58

您可以通過排序intervalls來改進貪婪的方法。從最長的時間間隔開始。只是一種啓發式，但應該有助於縮小差距。 – Matthias 2014-09-05 11:11:45

我已經解決相同問題與下列溶液：

查找LB =分鐘（開始時間）和RB = MAX（結束時間）。
將長度爲LB的空行添加到RB;
對於行中的每個「自由時間」扇區（最初，將僅存在一個扇區：LB到RB）：
- 3.1查找，將適合該扇區中的最長的元素;
- 3.2.1如果有這樣的元素 - 嵌入行中;
- 3.2.2否則顯然這個空閒扇區是不可用的;
如果還有目前所有的空閒扇區進行了測試後留下的元素，去2.

要知道，將一個元素（步驟3.2.1）時，設定的自由枚舉的扇區（步驟3）將會改變。

來源

2014-09-05 11:14:06 July

這被稱爲間隔分區。貪婪算法按照開始時間的順序分配框，並將框放入適合的第一行（如果不適合，則打開新行）會得到最佳結果。參見例如Kleinberg & Tardos：「算法設計」。

來源

2014-09-05 12:29:24

如果我正確理解你的問題，找出哪些日期重疊是最重要的。你沒有說，如果算法應該是非常有效的，或者它應該適用於非常大的數據。因此，我會推薦以下步驟：

找出哪些日期相互重疊。也許在地圖上，您將每個條目映射到與其重疊的條目列表。
按開始時間對元素進行排序。
只要一行中有空格，就可以選擇具有最近開始時間的元素到最後一個元素結束時間的元素。
從與此重疊的所有元素中選擇一個重疊最多的元素，它與上一個元素不重疊並將其添加到您的行中。
如果一行滿了，檢查最大的差距，看一個元素是否適合它;否則轉到下一行。

也許通過重疊和第5步中的最終檢查來加權元素可能有助於改善正常的貪婪方法。

來源

2014-09-05 13:28:35

包裝時隙的算法

回答

相關問題