學生時間調度算法

我需要找到一個算法來找到最好的時間來讓我們說一個研究小組。該系統具有關於一組學生及其課程表的信息。系統應該給與會面時間，與任何人的課程時間表沒有衝突。什麼是解決這個問題的最好方法。我正在尋找任何調度算法，但沒有找到合適的人。學生時間調度算法

在此先感謝

來源

2010-01-18 user171034

我記得這個問題的最佳解決方案是由遺傳算法

產生的解看到此鏈接http://www.codeproject.com/KB/recipes/GaClassSchedule.aspx

來源

2010-01-18 16:00:24 dfens

我不認爲GA對這個問題會有很大的幫助，因爲沒有適合評估解決方案的標準。乙醚是空閒的時間段，或者沒有。 – 2010-01-18 16:16:16

，因爲有一個最佳解決方案可以在小於指數時間內找到，所以GA真的不需要！ – Agos 2010-01-18 16:17:59

不，你正在考慮制定一個時間表，這是一個NP-Complete問題。這個問題要簡單得多。 :) – JPvdMerwe 2010-01-18 16:20:57

有趣的問題。

這是我會做什麼：

首先，對齊所有timescheduals，爲了一切學生（例如開始星期一，每天在24小時devided）。您可以爲每個週期使用布爾值或整數，並將它們存儲在數組中。
然後一起對所有調度執行加法操作。

然後看起來是這樣的，例如：

Student A: 11100000111111100000 
Student B: 00000011111000010001 
Student C: 00000000111111110001 
_______________________________+ 
      11100022333222220002 
       ^^^   ^^^

然後，你需要使用一個簡單的循環，其保持當前的軌跡找到所有間隙在陣列中（用零區）零長度。記憶開始和結束索引並將其翻譯回來（步驟1的反向）到一個時間區域。

來源

2010-01-18 16:03:10 Pindatjuh

謝謝，我正在尋找更多的算法方法。 – user171034 2010-01-18 16:05:22

+1爲簡單起見。研究小組的規模和一天中的職位空缺數量足夠小，以至於對這個NP問題的大多數暴力方法都是一種選擇。對上述解決方案的一個推動是使用整數數組（每個學生一個數組，每個時隙一個整數）並且對時隙值進行求和而不是對它們進行求和，即布爾方式。這個系統允許SUM數組提供更好的選擇「第二選擇」的指導，即當一些學生不可用時滿足可能性。 – mjv 2010-01-18 16:16:14

謝謝，更新了這個例子。 – Pindatjuh 2010-01-18 16:30:13

這是一個匹配的問題，並且可以通過maximum flow algorithm

每個學生和研究組被解決是在一個有向圖，並輸入用於一個節點的每個學生具有一個流動單元作爲輸入，並連接到所有研究組中節點。每個研究節點組具有無限的輸出能力，當網絡中的流量是最大的，你有你的正確組合

也Introduction to Algorithms（流網絡章）見

來源

2010-01-18 16:04:13 Alon

+1。欲瞭解更多相關材料，請查閱http：// en。wikipedia.org/wiki/Linear_Programming – Agos 2010-01-18 16:20:21

最大流量遠不是簡單的代碼，使用一分鐘的分辨率就可以輕鬆使用某種類型的蠻力。 – JPvdMerwe 2010-01-18 16:29:28

每天有24*60 = 1440分鐘。所以你可以很容易地蠻力，因爲你不需要超過一分鐘的準確度。不過，我要描述一個簡單的DP。

您可以創建一個布爾數組來存儲該分鐘中組的學生是否有班級。你也有第二個數組。該數組存儲此塊中和左側的空餘數量。所以你可以做的是從右向左遍歷布爾數組，如果塊中有一個類，則使數字爲0，否則將其加1，再加上前一分鐘的數字。

不過，我覺得我的解釋缺乏的，所以這裏是僞代碼：

blocked = <boolean array>; 
numtoleft = <array containing the counts>; 
if blocked[0]: 
    numtoleft[0] = 0; 
else: 
    numtoleft[0] = 1; 

for i = 1 to 1440-1: 
    if blocked[i]: 
     numtoleft[i] = 0; 
    else: 
     numtoleft[i] = numtoleft[i-1];

然後你可以通過「numtoleft」陣列中發現的最大數量容易找到的最大的開放式插槽，您可以添加限制到你正在看的時代。

編輯：

下面是蟒蛇的算法：

def largestslot(blocked, startminute, endminute): 
    numtoleft = [0]*1440 
    numtoleft[startminute] = 0 if blocked[startminute] else 1 
    for i in xrange(startminute+1, endminute+1): 
     numtoleft[i] = 0 if blocked[i] else 1 
    ansmax = max(numtoleft[startminute:endminute+1) 
    ansi = numtoleft.index(ansmax) 
    return (ansi-ansmax, ansi)

來源

2010-01-18 16:08:15 JPvdMerwe

我不認爲這是一個優雅的解決方案。 – user171034 2010-01-18 16:10:05