日期排課演算法

『壹』 論文「計算機自動排課系統的設計與實現」的開題報告怎麼寫

方案名稱：智能排課系統。

方案目的：利用計算機替代傳統的繁瑣的手工排課方法。

方案闡述：本系統受游戲設計中A星演算法中的廣度搜索法啟發，結合手中的文獻，總結出來的一種排課方式。本方案先採用採用信息收集的方式，收集信息。然後利用回逆演算法進行智能排課。最後，再進行適當的人為調整，即可生成符合要求的課表。

方案詳解：當需要生成課表時，用戶需先設定排課條件。基本條件有：周課時設置，課程信息，班級信息，教師信息，場地信息，教學計劃（即那些老師教那些班級、可以選擇的空教室、是否有合班課等信息）。將所有信息存入資料庫。自動排課，即系統自動調用資料庫收集的信息然後利用設定的演算法進行排課。最後，將系統生成的課表進行差錯檢查，分別在班級信息，教師信息，場地信息表中檢測其有無沖突。然後進行查看和手工調課。最後生成所需求的課表。

演算法詳解：

回溯是一種優先搜索法。它按優先條件向前搜索，以達到目標，但當搜索到某一步時，發現原先的選擇並不優或達不到目標，就退回一步重新選擇。這種走不通就退回的技術為回溯法，而滿足回溯條件的某個狀態點稱之為回溯點。

具體到計算機智能排課系統中，選優條件即為排課數學模型中的約束條件群（需求集中的元素特徵與資源集中的元素特徵相互作用形成的數學關系）。換言之，若不滿足約束條件群，該選擇即為不優或達不到目標。當遍歷該步驟的所有可能仍未滿足約束條件群，則該狀態滿足了回溯條件，該狀態點即為回溯點。下圖即為回溯演算法排課流程。

值得指出的是，當得到第一次滿足選優條件的排課結果後，可以將課表輸出到屏幕上，由系統管理員直接審視排課結果，若感覺不滿意，則可回到第一次得出的排課結果，將該狀態設為回溯點，繼續運行該演算法，可以得到另一種排課結果，直至程序管理員滿意為止。

當然，也有可能使用該法遍歷了所有的可能，仍無滿足選優條件之排課結果，此時，計算機就根據反饋的結果，自動放寬約束條件，重新進行排課。

該排課系統已在實際應用，排課結果較為理想，並且充分發揮了運算速度快的特點。

計算機自動排課也需要進行人工干預，以便可以使得各個高校能夠根據自己的具體要求對排課演算法中的一些參數進行設置和調整，並對計算機排出的課表進行調整．本演算法所設計的人工干預過程有：等價類劃分中參數的設置，教室類型的設置，時間模式庫的設置，優先順序函數中參數的設置．用戶可以根據自己的具體要求對這些參數和庫進行設置．另外，對於計算機排出的課程表，用戶也可以通過人機交互進行適當調整，從而得到用戶滿意的課程表．

參考文獻：《高校智能排課系統文獻綜述》

作者，日期不詳。

《以代理人為基礎的中學排課系統研究》

台灣高雄師大學 楊錦潭 歐文性

PS: 本人經過幾天了解和獲得老師的指點，覺得該系統如何能使用數據結構圖和離散數學中的圖論解決會能具有可操作性和智能性。另外，本人認為可以設計一個信息採集的介面，用於採集一些教師的需求信息（例如：不想上某個時段的課程。）這樣可以使整個信息更加人性化，但實現起來也比較有難度。知識水平有限，只能在我所能想到的范圍進行思考。

『貳』 如何用C語言實現大學排課

#include <stdio.h>
#include <stdlib.h>
#define M 100

struct Student
{
int StudentID;
char name[50];
float PeacetimeScore;
float TestScore;
float TotalScore;
};

int main()
{
int InputInformation (struct Student student[]);
void TotalScoreStatistics (struct Student student[], int n);
void TotalScoreSort (struct Student student[], int n);
void ScoreRevise (struct Student student[], int n);
void display (struct Student student[], int n);
int menu ();

int n = 1, count;
struct Student student[M];

while (n)
{
n = menu ();
switch (n)
{
case 1:
count = InputInformation (student);
break;
case 2:
TotalScoreStatistics (student, count);
break;
case 3:
TotalScoreSort (student, count);
break;
case 4:
ScoreRevise (student, count);
break;
case 5:
display (student, count);
break;
case 0:
printf ("您選擇了退出!\n");
break;
default :
printf ("輸入有誤,重新輸入!\n");
break;
}
}

return 0;
}

int menu ()
{
int n, i;

char * menu[]={"* * * * * * * * * * * * * * *MENU* * * * * * * * * * * * * * *",
" 1.學生信息錄入",
" 2.總成績統計",
" 3.總成績排序",
" 4.成績更改",
" 5.顯示所有學生信息",
" 0.退出",
"* * * * * * * * * * * * * * *MENU* * * * * * * * * * * * * * *"};
for (i=0; i<8; i++)
printf ("%s\n", menu[i]);
printf ("請選擇(輸入序號):");
scanf ("%d", &n);

return n;
}

int InputInformation (struct Student student[])
{
int i;
FILE *fp;

for (i=0; ; i++)
{
printf ("輸入第 %d 個學生的如下信息:\n", i+1);
printf ("學號:");
scanf ("%d", &student[i].StudentID);
if (student[i].StudentID == 0) //如果學號輸入是0則結束輸入
break;
getchar ();
printf ("姓名:");
gets (student[i].name);
printf ("平時成績:");
scanf ("%f", &student[i].PeacetimeScore);
printf ("考試成績:");
scanf ("%f", &student[i].TestScore);
fp = fopen ("myfile.txt", "a");
if (fp == NULL)
{
printf ("文件打開失敗!\n");
exit (-1);
}
fprintf (fp, "%d %s %.2f %.2f\n", student[i].StudentID, student[i].name,
student[i].PeacetimeScore, student[i].TestScore);
}
fclose (fp); //關閉文件
return i;
}

void TotalScoreStatistics (struct Student student[], int n)
{
int i;

printf ("\n 學號 姓名 總成績\n\n");
for (i=0; i<n; i++)
{
student[i].TotalScore = student[i].PeacetimeScore * 0.2 + student[i].TestScore * 0.8;
printf (" %d %s %.2f\n", student[i].StudentID, student[i].name, student[i].TotalScore);
}
}

void TotalScoreSort (struct Student student[], int n)
{
int i, j;
float temp;

for (i=0; i<n; i++)
for (j=i+1; j<n; j++)
if (student[i].TotalScore > student[j].TotalScore)
{
temp = student[i].TotalScore;
student[i].TotalScore = student[j].TotalScore;
student[j].TotalScore =temp;
}
for (i=0; i<n; i++)
printf ("%.2f ", student[i].TotalScore);
printf ("\n");
}

void ScoreRevise (struct Student student[], int n)
{
int m, k, i = 0;
FILE *fp;

printf ("輸入要修改的學生的學號:");
scanf ("%d", &k);
printf ("您是要修改平時成績還是考試成績呢?\n");
printf ("1.修改平時成績\n");
printf ("2.修改考試成績\n");
printf ("輸入您的選擇:");
scanf ("%d", &m);
for (i=0; i<n; i++)
if (student[i].StudentID == k)
if (m == 1)

『叄』 c++排課系統的演算法

這個不是排列組合題目吧？如果不是，那就很簡單。大致說下思路，自己實現吧。
把學校機房的課時按每小時或者按幾個小時為單位編成一個數據結構。這個具體看學校怎麼安排上機課，如果最小單位為2小時，當然以2小時為單位，如果有班級只上半小時的上機課當然以半小時為單位。比如一周5天每天10小時我們可以把它編成50個單位的一個數據結構。可以為數組，可以為鏈表，當然也可以為更復雜的結構，看你的需要。簡單的機房上機課時結構基本子元素為：起止時間、已安排班級（若未安排則為空）、已安排老師
把班級和老師也儲存在一個數據結構里。然後確定班級排上機課的原則。比如是平均分配機時，那麼將每個班級增加一個計數器。那麼班級的數據結構每個元素至少要有這么幾個子元素：班級標識、班級計數器、班級空閑時間表。排上機課的時候，首先取出機房上機課時的數據結構，取出第一個元素，然後遍歷存儲班級信息的數據結構，優先取出班級計數器最小的班級，查看這個班級這時是否有課，無課則插入到上機課時的數據結構中，同時將班級計數器加一，有課則選擇下一個計數器數字最小的元素。（計數器只是表示班級安排了多少上機課，也可以用一個數字代替，僅僅表示權重，比如計算機系的班級權重就可以調高。建議將整個鏈表中計數器數字的最小值保存在這個鏈表的某處，使得訪問者一開始就能得到而不用訪問所有元素）。重復上述過程，直到所有上機課時都被分配。
老師的分配過程和上述班級分配類似。

看來是新手，加油！

『肆』 excel根據開課日期及總課時數，自動計算最後一次排課日期

這是公式，你驗證一下

『伍』 c++如何實現排課系統的演算法

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

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

『陸』 排課的演算法

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

『柒』 求排課演算法源碼

排課演算法：有N個老師，每個老師每星期有若干節課。其中每節課都固定安排在某星期段上。每個星期有固定節課。我們要求排課並且不沖突。

『捌』 排課邏輯的演算法

這是一個難題，目前還在研究中，您可以查查排課演算法

『玖』 自動排課系統的一些演算法思想, 寫出一些關於自動排課的演算法思想,講述明白一點.

排課演算法的重點就是課程合理安排的問題,這裡面最要的部分應該是正確的使用演算法實現數學中排列組合.
比如寫規定好某某課不能放在第幾節,某某課一天不能超過幾節,某某課屬於某個老師,同一個老師的課同一時間只能安排一節,然後根據這些先決條件進行排列組合就可以了.
good luck.

『拾』 排課專家演算法是用來做什麼的

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。
（三）回溯法
回溯法有「通用的解題法」之稱。用它可以求出問題的所有解或任一解。概括地說，回溯法是一個既帶有系統性又帶有跳躍性的搜索法。它在包含問題所有解的一顆狀態空間樹上，按照深度優先的策略，從根出發進行搜索。搜索每到達狀態空間樹的一個節點，總是先判斷以該節點為根的子樹是否肯定不包含問題的解。如果肯定不包含，則跳過對該子樹的系統搜索，一層一層地向它的祖先節點繼續搜索，直到遇到一個還有未被搜索過的兒子的節點，才轉向該節點的一個未曾搜索過的兒子節點繼續搜索；否則，進入子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根的所有兒子都已被搜索過才結束；而在用來求問題的任一解時，只要搜索到問題的一個解就可結束。 本文來自CSDN博客，轉載請標明出處： http://blog.csdn.net/hanpoyangtitan/archive/2009/04/03/4046709.aspx