課程表演算法

⑴ 我想編寫一個自動生成課程表的程序,但是演算法我不知道怎麼寫!

你要說明白一點，有什麼要求，實現怎麼樣的功能，才好回答！一般是用隨機函數，然後用循環語句執行，嵌套條件語句判斷滿足條件，不滿足就返回從新執行，直到滿足條件，列印輸出結果，這是我學習dBASE時期，＆BASIC時的演算法，應該是通用的，結構化的編程語言都通用的！

⑵ 怎樣做好高校排課

1課題背景與研究意義
排課問題早在70年代就證明是一個NP完全問題，即演算法的計算時間是呈指數增長的，這一論斷確立了排課問題的理論深度。對於NP問題完全問題目前在數學上是沒有一個通用的演算法能夠很好地解決。然而很多NP完全問題目具有很重要的實際意義，例如。大家熟悉地路由演算法就是很典型的一個NP完全問題，路由要在從多的節點中找出最短路徑完成信息的傳遞。既然都是NP完全問題，那麼很多路由演算法就可以運用到解決排課問題上，如Dijkstra演算法、節點子樹剪枝構造網路最短路徑法等等。
目前大家對NP 完全問題研究的主要思想是如何降低其計算復雜度。即利用一個近似演算法來代替，力爭使得解決問題的時間從指數增長化簡到多項式增長。結合到課表問題就是建立一個合適的現實簡約模型，利用該簡約模型能夠大大降低演算法的復雜度，便於程序實現，這是解決排課問題一個很多的思路。
在高等院校中，培養學生的主要途徑是教學。在教學活動中，有一系列管理工作，其中，教學計劃的實施是一個重要的教學環節。每學期管理人員都要整理教學計劃，根據教學計劃下達教學任務書，然後根據教學任務書編排課程表。在這些教學調度工作中，既有大量繁瑣的數據整理工作，更有嚴謹思維的腦力勞動，還要填寫大量的表格。因此工作非常繁重。
加之，隨著教學改革的進行及「211」工程的實施，新的教育體制對課表的編排提出了更高的要求。手工排課時，信息的上通下達是極其麻煩的，而採用計算機排課，教學中的信息可以一目瞭然，對於優化學生的學習進程，評估每位教師對教學的貢獻，領導合理決策等都具有重要的意義，必將會大大推進教學的良性循環。
2課題的應用領域
本課題的研究對開發高校排課系統有指導作用。
排課問題的核心為多維資源的沖突與搶占，對其研究對類似的問題（特別是與時間表有關的問題：如考試排考場問題、電影院排座問題、航空航線問題）也是個參考。
3 課題的現狀
年代末，國外就有人開始研究課表編排問題。1962年，Gotlieb曾提出了一個課表問題的數學模型，並利用匈牙利演算法解決了三維線性運輸問題。次後，人們對課表問題的演算法、解的存在性等問題做了很多深入探討。但是大多數文獻所用的數學模型都是Gotlieb的數學模型的簡化或補充，而至今還沒有一個可行的演算法來解決課表問題。
近40年來，人們對課表問題的計算機解法做了許多嘗試。其中，課表編排的整數規劃模型將問題歸結為求一組0-1變數的解，但是其計算量非常大。解決0-1線性優化問題的分支一定界技術卻只適用也規模較小的課表編排，Mihoc和Balas（1965）將課表公式化為一個優化問題，Krawczk則提出一種線性編程的方法。Junginger將課表問題簡化為三維運輸問題，而Tripathy則把課表問題視作整數線性編程問題並提出了大學課表的數學模型。
此外，有些文獻試圖從圖論的角度來求解排課表的問題，但是圖的染色問題也是NP完全問題，只有在極為簡單的情況下才可以將課表編排轉化為二部圖匹配問題，這樣的數學模型與實際相差太遠，所以對於大多數學校的課表編排問題來說沒有實用價值。
進入九十年代以後，國外對課表問題的研究仍然十分活躍。比較有代表的有印度的Vastapur大學管理學院的ArabindaTripathy、加拿大Montreal大學的Jean Aubin和Jacques Ferland等。目前，解決課表方法的問題有：模擬手工排課法，圖論方法，拉格朗日法，二次分配型法等多種方法。由於課表約束復雜，用數學方法進行描述時往往導致問題規模劇烈增大，這已經成為應用數學編程解決課表問題的巨大障礙。國外的研究表明，解決大規模課表編排問題單純靠數學方法是行不通的，而利用運籌學中分層規劃的思想將問題分解，將是一個有希望得到成功的辦法。
在國內，對課表問題的研究開始於80年代初期、具有代表性的有：南京工學院的UTSS（A University Timetable Scheling System）系統，清華大學的TISER（Timetable SchelER）系統，大連理工大學的智能教學組織管理與課程調度等，這些系統大多數都是模擬手工排課過程，以「班」為單位，運用啟發式函數來進行編排的。但是這些系統課表編排系統往往比較依賴於各個學校的教學體制，不宜進行大量推廣。
從實際使用的情況來看，國內外研製開發的這些軟體系統在實用性上仍不盡如人意。一方面原因是作為一個很復雜的系統，排課要想面面俱到是一件很困難的事；另一方面每個學校由於其各自的特殊性，自動排課軟體很難普遍實用，特別是在調度的過程中一個很小的變動，要引起全部課程的大調整，這意味著全校課程大變動，在實際的應用中這是很難實現的事。
4解決NP問題的幾種演算法及其比較
解決NP完全問題只能依靠近似演算法，所以下面介紹幾種常用演算法的設計思想，包括動態規劃、貪心演算法、回溯法等。
動態規劃法是將求解的問題一層一層地分解成一級一級、規模逐步縮小的子問題，直到可以直接求出其解的子問題為止。分解成的所有子問題按層次關系構成一顆子問題樹。樹根是原問題。原問題的解依賴於子問題樹中所有子問題的解。動態規劃演算法通常用於求一個問題在某種意義下的最優解。設計一個動態規劃演算法，通常可按以下幾個步驟進行：
1. 分析最優解的性質，並刻劃其結構特徵。
2. 遞歸的定義最優解。
3. 以自底向上的方式計算出最優解。
4. 根據計算最優解時得到的信息，構造一個最優解。
步驟1~3是動態規劃演算法的基本步驟。在只需要求出最優解的情形，步驟4可以省去。若需要求出問題的一個最優解，則必須執行步驟4。此時，在步驟3中計算最優解時，通常需記錄更多的信息，以便在步驟4中，根據所記錄的信息，快速地構造出一個最優解。
（二）貪心演算法
當一個問題具有最優子結構性質時，我們會想到用動態規劃法去解它，但有時會有更簡單、更有效的演算法，即貪心演算法。顧名思義，貪心演算法總是做出在當前看來最好的選擇。也就是說貪心演算法並不是整體最優上加以考慮，他所作出的選擇只是在某種意義上的局部最優的選擇。雖然貪心演算法不是對所有問題都能得到整體最優解，但對范圍相當廣的許多問題它能產生整體最優解，如圖的演算法中單源最短路徑問題，最小支撐樹問題等。在一些情況下，即使貪心演算法不能得到整體最優解，但其最終結果卻是最優解的很好的近似解。
在貪心演算法中較為有名的演算法是Dijkstra演算法。它作為路由演算法用來尋求兩個節點間的最短路徑。Dijkstra演算法的思想是：假若G有n個頂點，於是我們總共需要求出n-1條最短路徑，求解的方法是：初試，寫出V0(始頂點)到各頂點(終頂點)的路徑長度，或有路徑，則令路徑的長度為邊上的權值；或無路經，則令為∞。再按長度的遞增順序生成每條最短路徑。事實上生成最短路徑的過程就是不斷地在始頂點V何終頂點W間加入中間點的過程，因為在每生成了一條最短路徑後，就有一個該路徑的終頂點U，那麼那些還未生成最短路徑的路徑就會由於經過U而比原來的路徑短，於是就讓它經過U。
（三）回溯法
回溯法有「通用的解題法」之稱。用它可以求出問題的所有解或任一解。概括地說，回溯法是一個既帶有系統性又帶有跳躍性的搜索法。它在包含問題所有解的一顆狀態空間樹上，按照深度優先的策略，從根出發進行搜索。搜索每到達狀態空間樹的一個節點，總是先判斷以該節點為根的子樹是否肯定不包含問題的解。如果肯定不包含，則跳過對該子樹的系統搜索，一層一層地向它的祖先節點繼續搜索，直到遇到一個還有未被搜索過的兒子的節點，才轉向該節點的一個未曾搜索過的兒子節點繼續搜索；否則，進入子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根的所有兒子都已被搜索過才結束；而在用來求問題的任一解時，只要搜索到問題的一個解就可結束。
加油！

⑶ 大學排課需要注意什麼

1課題背景與研究意義
排課問題早在70年代就證明是一個NP完全問題，即演算法的計算時間是呈指數增長的，這一論斷確立了排課問題的理論深度。對於NP問題完全問題目前在數學上是沒有一個通用的演算法能夠很好地解決。然而很多NP完全問題目具有很重要的實際意義，例如。大家熟悉地路由演算法就是很典型的一個NP完全問題，路由要在從多的節點中找出最短路徑完成信息的傳遞。既然都是NP完全問題，那麼很多路由演算法就可以運用到解決排課問題上，如Dijkstra演算法、節點子樹剪枝構造網路最短路徑法等等。
目前大家對NP 完全問題研究的主要思想是如何降低其計算復雜度。即利用一個近似演算法來代替，力爭使得解決問題的時間從指數增長化簡到多項式增長。結合到課表問題就是建立一個合適的現實簡約模型，利用該簡約模型能夠大大降低演算法的復雜度，便於程序實現，這是解決排課問題一個很多的思路。
在高等院校中，培養學生的主要途徑是教學。在教學活動中，有一系列管理工作，其中，教學計劃的實施是一個重要的教學環節。每學期管理人員都要整理教學計劃，根據教學計劃下達教學任務書，然後根據教學任務書編排課程表。在這些教學調度工作中，既有大量繁瑣的數據整理工作，更有嚴謹思維的腦力勞動，還要填寫大量的表格。因此工作非常繁重。
加之，隨著教學改革的進行及「211」工程的實施，新的教育體制對課表的編排提出了更高的要求。手工排課時，信息的上通下達是極其麻煩的，而採用計算機排課，教學中的信息可以一目瞭然，對於優化學生的學習進程，評估每位教師對教學的貢獻，領導合理決策等都具有重要的意義，必將會大大推進教學的良性循環。
2課題的應用領域
本課題的研究對開發高校排課系統有指導作用。
排課問題的核心為多維資源的沖突與搶占，對其研究對類似的問題（特別是與時間表有關的問題：如考試排考場問題、電影院排座問題、航空航線問題）也是個參考。
3 課題的現狀
年代末，國外就有人開始研究課表編排問題。1962年，Gotlieb曾提出了一個課表問題的數學模型，並利用匈牙利演算法解決了三維線性運輸問題。次後，人們對課表問題的演算法、解的存在性等問題做了很多深入探討。但是大多數文獻所用的數學模型都是Gotlieb的數學模型的簡化或補充，而至今還沒有一個可行的演算法來解決課表問題。
近40年來，人們對課表問題的計算機解法做了許多嘗試。其中，課表編排的整數規劃模型將問題歸結為求一組0-1變數的解，但是其計算量非常大。解決0-1線性優化問題的分支一定界技術卻只適用也規模較小的課表編排，Mihoc和Balas（1965）將課表公式化為一個優化問題，Krawczk則提出一種線性編程的方法。Junginger將課表問題簡化為三維運輸問題，而Tripathy則把課表問題視作整數線性編程問題並提出了大學課表的數學模型。
此外，有些文獻試圖從圖論的角度來求解排課表的問題，但是圖的染色問題也是NP完全問題，只有在極為簡單的情況下才可以將課表編排轉化為二部圖匹配問題，這樣的數學模型與實際相差太遠，所以對於大多數學校的課表編排問題來說沒有實用價值。
進入九十年代以後，國外對課表問題的研究仍然十分活躍。比較有代表的有印度的Vastapur大學管理學院的ArabindaTripathy、加拿大Montreal大學的Jean Aubin和Jacques Ferland等。目前，解決課表方法的問題有：模擬手工排課法，圖論方法，拉格朗日法，二次分配型法等多種方法。由於課表約束復雜，用數學方法進行描述時往往導致問題規模劇烈增大，這已經成為應用數學編程解決課表問題的巨大障礙。國外的研究表明，解決大規模課表編排問題單純靠數學方法是行不通的，而利用運籌學中分層規劃的思想將問題分解，將是一個有希望得到成功的辦法。
在國內，對課表問題的研究開始於80年代初期、具有代表性的有：南京工學院的UTSS（A University Timetable Scheling System）系統，清華大學的TISER（Timetable SchelER）系統，大連理工大學的智能教學組織管理與課程調度等，這些系統大多數都是模擬手工排課過程，以「班」為單位，運用啟發式函數來進行編排的。但是這些系統課表編排系統往往比較依賴於各個學校的教學體制，不宜進行大量推廣。
從實際使用的情況來看，國內外研製開發的這些軟體系統在實用性上仍不盡如人意。一方面原因是作為一個很復雜的系統，排課要想面面俱到是一件很困難的事；另一方面每個學校由於其各自的特殊性，自動排課軟體很難普遍實用，特別是在調度的過程中一個很小的變動，要引起全部課程的大調整，這意味著全校課程大變動，在實際的應用中這是很難實現的事。
4解決NP問題的幾種演算法及其比較
解決NP完全問題只能依靠近似演算法，所以下面介紹幾種常用演算法的設計思想，包括動態規劃、貪心演算法、回溯法等。
動態規劃法是將求解的問題一層一層地分解成一級一級、規模逐步縮小的子問題，直到可以直接求出其解的子問題為止。分解成的所有子問題按層次關系構成一顆子問題樹。樹根是原問題。原問題的解依賴於子問題樹中所有子問題的解。動態規劃演算法通常用於求一個問題在某種意義下的最優解。設計一個動態規劃演算法，通常可按以下幾個步驟進行：
1. 分析最優解的性質，並刻劃其結構特徵。
2. 遞歸的定義最優解。
3. 以自底向上的方式計算出最優解。
4. 根據計算最優解時得到的信息，構造一個最優解。
步驟1~3是動態規劃演算法的基本步驟。在只需要求出最優解的情形，步驟4可以省去。若需要求出問題的一個最優解，則必須執行步驟4。此時，在步驟3中計算最優解時，通常需記錄更多的信息，以便在步驟4中，根據所記錄的信息，快速地構造出一個最優解。
（二）貪心演算法
當一個問題具有最優子結構性質時，我們會想到用動態規劃法去解它，但有時會有更簡單、更有效的演算法，即貪心演算法。顧名思義，貪心演算法總是做出在當前看來最好的選擇。也就是說貪心演算法並不是整體最優上加以考慮，他所作出的選擇只是在某種意義上的局部最優的選擇。雖然貪心演算法不是對所有問題都能得到整體最優解，但對范圍相當廣的許多問題它能產生整體最優解，如圖的演算法中單源最短路徑問題，最小支撐樹問題等。在一些情況下，即使貪心演算法不能得到整體最優解，但其最終結果卻是最優解的很好的近似解。
在貪心演算法中較為有名的演算法是Dijkstra演算法。它作為路由演算法用來尋求兩個節點間的最短路徑。Dijkstra演算法的思想是：假若G有n個頂點，於是我們總共需要求出n-1條最短路徑，求解的方法是：初試，寫出V0(始頂點)到各頂點(終頂點)的路徑長度，或有路徑，則令路徑的長度為邊上的權值；或無路經，則令為∞。再按長度的遞增順序生成每條最短路徑。事實上生成最短路徑的過程就是不斷地在始頂點V何終頂點W間加入中間點的過程，因為在每生成了一條最短路徑後，就有一個該路徑的終頂點U，那麼那些還未生成最短路徑的路徑就會由於經過U而比原來的路徑短，於是就讓它經過U。
（三）回溯法
回溯法有「通用的解題法」之稱。用它可以求出問題的所有解或任一解。概括地說，回溯法是一個既帶有系統性又帶有跳躍性的搜索法。它在包含問題所有解的一顆狀態空間樹上，按照深度優先的策略，從根出發進行搜索。搜索每到達狀態空間樹的一個節點，總是先判斷以該節點為根的子樹是否肯定不包含問題的解。如果肯定不包含，則跳過對該子樹的系統搜索，一層一層地向它的祖先節點繼續搜索，直到遇到一個還有未被搜索過的兒子的節點，才轉向該節點的一個未曾搜索過的兒子節點繼續搜索；否則，進入子樹，繼續按深度優先的策略進行搜索。

⑷ 請教課程表排課軟體演算法的設計

排課軟體的演算法是很復雜的，雲校排課~看看他們的演算法，據說是比較先進的~