算法找到最佳的時間表

我正在尋找一個算法或一般解決以下問題的方法：算法找到最佳的時間表

學生A，...，M都刻着各種模塊的書面examniations。下表列出了銘文。如果每個學生每天都可以參加一次考試，那麼至少需要多少天才能組織會議？

  |A|B|C|D|E|F|G|H|I|J|K|L|M| 
Module 1 | | | |X| |X|X| |X|X| | | | 
Module 2 |X| | | | |X| | | |X|X| | | 
Module 3 | |X| | | | | |X| | |X| |X| 
Module 4 |X| | |X| | | | | | | | | | 
Module 5 | | |X| |X| | | | |X| | |X| 
Module 6 | | |X| | | | |X| | | | | | 
Module 7 |X|X| | | | | | |X| |X| | | 
Module 8 | | |X| | | |X| | | | |X| |

我如何解決問題？

來源

2015-11-09 BennoDual

我想說的第一步是建立兼容性表，即告訴你，如果有可能有模塊X和Y模塊相同的表天。 – njzk2

是這個作業嗎？ – Jelle

我建議尋找關鍵路徑方法。 –

隨着圖着色。

爲每個模塊創建一個節點，每當學生擁有模塊i和j時，節點i和j之間就存在一條邊。爲圖表着色，顏色代表日子。每當模塊不能在同一天時，節點之間就存在邊界，因此着色會提供有效的時間表。最小的着色給出了最短的時間表。

至於實際上解決的情況下（即圖着色的算法），這個大小我想舉一個簡單的比較暴力的做法，有點像這樣的建議：

for k in 1 .. 
    tryColour(k, 1) 

tryColour(k, i): 
    if i > numnodes: 
     found it 
    for c in 1 .. k: 
     if node i can have colour c: 
      colours[i] = c 
      tryColour(k, i+1)

我根本沒注意細節，這只是爲了這個想法：選擇一個節點，給它一種不是不可能的顏色，然後遞歸地爲其餘的顏色着色。如果遞歸着色爲空，請用下一種顏色重試。用越來越多的顏色來做這件事，直到找到解決方案。

來源

2015-11-09 19:01:05 harold

謝謝。有了這個，我可以「手工」解決問題。但是當我建立圖表時，是否有算法來計算所需的最小顏色數量？ – BennoDual

如果您使用的是Java，則可以爲節點添加一個狀態，並簡單地對它們進行計數或使用任何其他機制。 – Jelle

@Jelle這是怎麼給出一個着色？ – harold

一旦你有不兼容的表，其內容應當類似於：

a[1] = [2,4,5,7,8] 
a[2] = [1,3,4,5,7] 
a[3] = [2,3,5,6,7] 
a[4] = [1,2,7,8] 
a[5] = [1,2,3,6,8] 
a[6] = [3,5,8] 
a[7] = [1,2,3,4] 
a[8] = [1,5,6]

我認爲這是東西的想法：

創建每天節點，把一個模塊中它與它的不兼容模塊。
然後，只要在任何給定的節點仍然有不兼容的模塊沒有解決：
- 從該節點的彈出模塊兼容，
- 要麼將其放置在兼容的節點，或創建一個新的day-節點
- 然後從任何其他天節點在該模塊中，它仍然存在

每天節點具有模塊的列表會發生的那一天，和當天不會發生的模塊列表。雖然我不完全確定如何證明它是最佳的。它似乎是因爲它認爲與首先看到的模塊不兼容。

的快速和骯髒的Python實現的一個例子：https://repl.it/BY2B

來源

2015-11-09 19:55:45 njzk2

算法找到最佳的時間表

回答

相關問題