排課模擬演算法

㈠ 有沒有人知道最優排課演算法怎麼設計

不是所有的問題都能在你能接受的時間復雜度內得到最優解的。
多項式演算法並不總是存在。

排課問題。。

你這什麼意思啊。這個每個班不是人數固定嘛？那讓人待在一個地方老師來教不就行了啊。。正納悶你什麼意思。。

這個問題能不能應用線性規劃模型？因為你敘述不清，所以我也沒有辦法幫你建立模型。

至於DFS(深度優先搜索，就是你所謂的遞歸窮舉)演算法，那是一定要最優性剪枝和可行性剪枝的。運用地恰當可以大大減小搜索樹的大小，至於20,20...這種數據量是小兒科的，應用DFS+剪枝應該可以得到很好的效果（我的意思是1s出解，因為我的世界衡量好與不好就是1s的限制)。

可行性剪枝：你自己定吧，我實在不明白你什麼意思。
最優性剪枝：這個需要動態規劃演算法協助估計剩餘可能需要的最小的目標函數值，再加上當前的目標函數值，大於最優解直接跳出。

我在剪枝上面基本上是文盲，不過對於解決你這個問題應該問題不大。

建議你好好考慮問題，再次用DFS演算法，用上面兩個方向考慮去掉多餘的解，這是完全可以得到的。

實際中這種問題的演算法都是非完美演算法。（我不知道這個問題的性質是P類還是NP類，NP類是一定沒有多項式時間演算法的）

比如很簡單的應用模擬退火演算法和遺傳演算法都可以比較完美地解決問題。
一般實際中較少地要求最優解，因為比起消耗，這是不值得的。

㈡ 水晶排課是怎麼排

只要設置好學校班數、節數、課程、教師任課，水晶排課就會自動排出所有課程表。

一個50個班的學校，從信息開始錄入到開始列印課程表的整個過程一般一個小時內就可以完全搞定。而且電腦自動排課的過程只需幾秒鍾，排完之後覺得不滿意，完全可以再用幾秒鍾的時間再排一次。

還能完美地導入Excel數據，並且能生成漂亮的Excel課程表，排課質量也非常優秀，基本告別所有手動和半自動排課方式，手動調課功能也非常強大。

(2)排課模擬演算法擴展閱讀：

水晶排課的優勢：

排課軟體，界面非常易用漂亮，手工排課一向是學校教務工作中最另人頭疼的事，非常費時費神，而且由於人工操作時多多少少會有些失誤。

往往經過一兩天的冥思苦想排出來的課程表，卻總會發現紕漏，導致課程表需要修改。而修改課程表一般都是牽一發而動全身，令人非常苦惱。水晶排課智能排課系統的出現解決了以上所有難題。

水晶排課軟體特性

最好的智能排課系統。完美地導入Excel數據，真正生成Excel課程表，先進的排課演算法，功能強大的手動排課，完美解決令頭頭疼的學校排課問題。

參考資料：網路-水晶排課

㈢ 如何用matlab實現基於遺傳演算法的自動排課系統的模擬測試

一句話講不清楚咯，挺復雜

㈣ 排課的演算法

排課演算法是一個復雜程度相當高的演算法，窮舉是行不通的。不同的班級，不同的教師的課程縱橫交錯，不可能對每一種組合一一窮舉。一間不到三十個班的學校，其課程組合的數量級常常超過整個宇宙質子數的總和。
但在這么多的課程組合中，找出「相對合理」的課程組合，滿足學校、教師、學生的要求是可行的。

㈤ 怎麼使用C#編寫排課系統 急需 希望高手能幫助下 提供下具體步驟和源代碼 感激不

我只提示，希望你自己完成
1、弄清楚排課演算法，完成演算法函數，注意輸入輸出介面
2、制定界面，定義輸入輸出（顯示）模塊（控制項）
3、主程序或事件調用排課演算法

㈥ c++如何實現排課系統的演算法

我的想法是……
1.首先把最難弄的老師排上，就是說她教的班多，限制多。（這步的實際操作就是把排課順序按照班數排序）
2.隨機安排課（當然要根據人類習慣，您總不能讓他一天上七節課),安排方式為先滿足部分人需求（當然不太公平），然後剩下的補空
3.這剩下的部分人可能因為班級的關系出現重課的問題，沒有關系，先把他安排上去，用repeat循環逐層更改被沖突對象的課節（最後可以選把美術音樂等老師，他們安排到下午的話上午比較好換）

具體跟據實際來定。。……我亂講講。這是我的想法模型。

㈦ 基於python的高校智能排課系統，求指導思路，演算法。

以教學任務為基本單位，在計算教學任務排課優先順序的基礎上，對教學任務的時間和教室的安排均採用優化資源查找的演算法．為簡化演算法，先安排教學任務的時間，然後再安排教室，設計並實現了一個高效智能排課系統．

㈧ Python實現基於遺傳演算法的排課優化

排課問題的本質是將課程、教師和學生在合適的時間段內分配到合適的教室中，涉及到的因素較多，是一個多目標的調度問題，在運籌學中被稱為時間表問題（Timetable Problem，TTP）。設一個星期有n個時段可排課，有m位教師需要參與排課，平均每位教師一個星期上k節課，在不考慮其他限制的情況下，能夠推出的可能組合就有 種，如此高的復雜度是目前計算機所無法承受的。因此眾多研究者提出了多種其他排課演算法，如模擬退火，列表尋優搜索和約束滿意等。

Github ： https://github.com/xiaochus/GeneticClassSchele

遺傳演算法（Genetic Algorithm）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。遺傳演算法的流程如下所示：

遺傳演算法首先針對待解決問題隨機生成一組解，我們稱之為種群（Population）。種群中的每個個體都是問題的解，在優化的過程中，演算法會計算整個種群的成本函數，從而得到一個與種群相關的適應度的序列。如下圖所示：

為了得到新的下一代種群，首先根據適應度對種群進行排序，從中挑選出最優的幾個個體加入下一代種群，這一個過程也被稱為精英選拔。新種群餘下的部分通過對選拔出來的精英個體進行修改得到。

對種群進行修改的方法參考了生物DAN進化的方法，一般使用兩種方法： 變異 和 交叉 。 變異 的做法是對種群做一個微小的、隨機的改變。如果解的編碼方式是二進制，那麼就隨機選取一個位置進行0和1的互相突變；如果解的編碼方式是十進制，那麼就隨機選取一個位置進行隨機加減。 交叉 的做法是隨機從最優種群中選取兩個個體，以某個位置為交叉點合成一個新的個體。

經過突變和交叉後我們得到新的種群（大小與上一代種群一致），對新種群重復重復上述過程，直到達到迭代次數（失敗）或者解的適應性達到我們的要求（成功），GA演算法就結束了。

演算法實現

首先定義一個課程類，這個類包含了課程、班級、教師、教室、星期、時間幾個屬性，其中前三個是我們自定義的，後面三個是需要演算法來優化的。

接下來定義cost函數，這個函數用來計算課表種群的沖突。當被測試課表沖突為0的時候，這個課表就是個符合規定的課表。沖突檢測遵循下面幾條規則：

使用遺傳演算法進行優化的過程如下，與上一節的流程圖過程相同。

init_population ：隨機初始化不同的種群。
mutate ：變異操作，隨機對 Schele 對象中的某個可改變屬性在允許范圍內進行隨機加減。
crossover ：交叉操作，隨機對兩個對象交換不同位置的屬性。
evolution ：啟動GA演算法進行優化。

實驗結果

下面定義了3個班，6種課程、教師和3個教室來對排課效果進行測試。

優化結果如下，迭代到第68次時，課程安排不存在任何沖突。

選擇1203班的課表進行可視化，如下所示，演算法合理的安排了對應的課程。