【文章內(nèi)容簡介】 標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”。因?yàn)榛厮葜斑M(jìn)行了禁忌搜索，為防止回溯時(shí)間過長，為回溯設(shè)置回溯長度以及回溯半徑，用以限制回溯過程規(guī)模。 本章小結(jié)本章主要介紹研究該課題過程中使用到的一些技術(shù)及其理論。計(jì)算機(jī)的軟件的開發(fā)離不開計(jì)算機(jī)編程語言以及相關(guān)軟件的支持，所以首先確定了開發(fā)過程中使用的開發(fā)平臺(tái)環(huán)境，然后對其特性和優(yōu)點(diǎn)進(jìn)行簡要的介紹，說明選擇Apache + PHP + MySQL作為開發(fā)平臺(tái)的理由是其良好的兼容性以及代碼開源性。本章第二節(jié)羅列出研究過程中使用到的一些理論，簡要介紹了什么是啟發(fā)式搜索、禁忌搜索和回溯法，并且簡單的說明在課題研究中的那些部分需要使用該理論。第3章 需求分析 第3章 需求分析 問題定義 本系統(tǒng)是一個(gè)基于B/S模式的多用戶系統(tǒng)，最終面向的是所有在校的教師、學(xué)生和系統(tǒng)管理人員，下面分別從這三個(gè)角度對系統(tǒng)進(jìn)行定義。 學(xué)生使用系統(tǒng)的功能要求（1）每個(gè)在校學(xué)生都可以訪問該系統(tǒng)，學(xué)生畢業(yè)之后不可以在使用該系統(tǒng)。（2）在校學(xué)生可以通過該系統(tǒng)查看并可以打印本學(xué)期的個(gè)人課表。（3）學(xué)生可以對本學(xué)期每一天公共教室的使用情況進(jìn)行查詢，方便上自習(xí)教室的查找。（4）學(xué)生可以對自己感興趣的課程或感興趣的教師開設(shè)的課程的上課教室進(jìn)行查找，對課程的查找應(yīng)該支持模糊查詢。（5）學(xué)生可以對本學(xué)期自己所修課程的考試信息進(jìn)行查看，前提是本門課程已經(jīng)安排了考試。（6）學(xué)生可以更改自己的系統(tǒng)登錄密碼。（7）學(xué)生可以查看由教務(wù)人員發(fā)布的關(guān)于教室占用、教學(xué)樓開放或關(guān)閉等信息和教師發(fā)布的關(guān)于課程補(bǔ)課教室或課程更改上課教室的信息。 教師使用系統(tǒng)的功能要求（1）每個(gè)在職教師都可以訪問該系統(tǒng)，教師離職之后不可以再使用該系統(tǒng)。（2）在職教師可以通過該系統(tǒng)查看和打印本學(xué)期的個(gè)人任課課表。（3）教師可以根據(jù)教室類型大小和使用的時(shí)間對符合條件的教室進(jìn)行查找，對查找結(jié)果可以申請占用，占用時(shí)間最多為四個(gè)課時(shí)，教室的申請應(yīng)該在對教室使用時(shí)間的前一天或前幾天進(jìn)行。（4）教師可以對自己占用教室的歷史進(jìn)行查看，對于尚未發(fā)生的占用，教師可以取消該次占用。（5）教師可以對本學(xué)期自己任課的課程進(jìn)行考試安排，可以查看已經(jīng)安排過的考試的信息。（6）教師可以發(fā)布關(guān)于課程補(bǔ)課或課程更改上課教室的信息。（7）教師可以更改自己的系統(tǒng)登錄密碼。 管理員使用系統(tǒng)的功能要求（1）該系統(tǒng)應(yīng)該存在至少一個(gè)管理人員，對教室及其相關(guān)信息進(jìn)行管理。（2）管理員可以對教室的基本信息進(jìn)行管理，包括教學(xué)樓的查找添加和刪除、教學(xué)樓中教室的查找添加修改刪除。管理員可以對本學(xué)期每間教室的課程表進(jìn)行查看與打印。（4）管理員可以對本學(xué)期考試安排教室的信息進(jìn)行查看和取消。（5）管理員可以申請教室的占用，并且可以對本學(xué)期所有教室占用的信息進(jìn)行查看，對尚未發(fā)生的占用管理員有權(quán)刪除占用信息。（6）管理員可以在學(xué)期初對本學(xué)期起止時(shí)間等相關(guān)信息進(jìn)行設(shè)置。（7）管理員學(xué)期初可以清除畢業(yè)離校學(xué)生以及離職教師的登錄權(quán)限并且可以刪除上學(xué)期與課程安排有關(guān)的信息。（8）管理員可以對本學(xué)期課程安排等相關(guān)數(shù)據(jù)進(jìn)行導(dǎo)入。（9）管理員可以發(fā)布與教室有關(guān)的占用信息。（10）管理員在學(xué)期初可以通過系統(tǒng)對所有課程的上課時(shí)間和地點(diǎn)進(jìn)行安排。（11）管理員可以備份以及恢復(fù)數(shù)據(jù)庫內(nèi)容。（12）管理員可以對所有用戶進(jìn)行注冊和密碼修改。 可行性分析為了研究設(shè)計(jì)該系統(tǒng)的方案是否可行，接下來從技術(shù)可行性、操作可行性、經(jīng)濟(jì)可行性和法律可行性四個(gè)角度對開發(fā)該系統(tǒng)進(jìn)行可行性分析[5]。（1）技術(shù)可行性分析 根據(jù)問題定義階段對問題的描述以及當(dāng)今理論技術(shù)的發(fā)展現(xiàn)狀來看，該系統(tǒng)可以通過已選定的開發(fā)環(huán)境進(jìn)行開發(fā)。經(jīng)過對排課算法的初步學(xué)習(xí)和調(diào)研，使用PHP語言可以在有限時(shí)間開發(fā)出一個(gè)具有實(shí)際意義可以滿足用戶要求的對課程進(jìn)行自動(dòng)安排的算法。（2）操作可行性分析 該系統(tǒng)性質(zhì)上屬于信息管理系統(tǒng)，因此開發(fā)過程中可以參照其他成功的基于B/S模式的管理系統(tǒng)對該系統(tǒng)進(jìn)行操作界面的設(shè)計(jì)，由于開發(fā)語言與所選數(shù)據(jù)庫具有很好的兼容性，所以對數(shù)據(jù)庫的操作基本也可以全都在系統(tǒng)功能界面實(shí)現(xiàn)。綜合以上考慮，對互聯(lián)網(wǎng)有基本的了解曾經(jīng)使用或訪問過類似網(wǎng)站的人都有能力對系統(tǒng)進(jìn)行操作，管理員對系統(tǒng)的操作可以在軟件開發(fā)結(jié)束之后通過與開發(fā)者的溝通進(jìn)行進(jìn)一步的了解。（3）經(jīng)濟(jì)可行性分析 由于軟件開發(fā)所使用的環(huán)境基本都屬于開源軟件，都可以通過正當(dāng)途徑免費(fèi)獲得其使用權(quán)限，因此從經(jīng)濟(jì)角度上說開發(fā)該系統(tǒng)是可行的。（4）法律可行性分析 本軟件為自主創(chuàng)新的智力活動(dòng)，所使用工具都是通過合法途徑獲得，系統(tǒng)中不存在侵犯他人所有權(quán)的內(nèi)容存在，軟件的調(diào)研背景為本學(xué)校，所有數(shù)據(jù)來源都屬于自己調(diào)查和統(tǒng)計(jì)，產(chǎn)品的目標(biāo)為進(jìn)行課題研究不屬于任何商業(yè)活動(dòng)，軟件所涉及內(nèi)容也與法律無任何沖突，因此從法律角度講開發(fā)該軟件是可行的。 需求分析 系統(tǒng)功能需求對系統(tǒng)的大部分功能需求在問題定義階段已經(jīng)描述清楚，這里主要對排課功能進(jìn)行詳細(xì)的分析。課程安排過程需要滿足兩種需求[6]，硬性需求和軟需求，其中硬性需求如下：（1）所有課程都必須被安排。（2）所選課程的出席人數(shù)不能超過該教室的容量。（3）同一個(gè)教師的不同課程不可以發(fā)生在同一個(gè)時(shí)間。（4）同一個(gè)班級的不同課程不可以安排在同一個(gè)時(shí)間。（5）一個(gè)教室的同一個(gè)時(shí)間不可以安排兩門或兩門以上的課程。（6）上課的教室類型符合課程的需求。軟性條件如下：（1）課程應(yīng)該均勻的安排在整個(gè)學(xué)期。（2）一門課的多個(gè)課節(jié)最好安排在一個(gè)教室。（3）一門課一天不可以出現(xiàn)兩次或兩次以上。（4）對每個(gè)教室的排課量應(yīng)該大體保持一致。（5）對每個(gè)班級和教師而言，課程安排最好均勻分布在一周中。硬性要求是排課過程中必須遵循的要求，每門課程安排過程中都必須遵循以上要求，如果不能滿足應(yīng)該做相應(yīng)的調(diào)整。軟性要求是在對課程的安排滿足所有硬性條件的前提下最好可以滿足的需求，當(dāng)條件不允許時(shí)軟性要求可以適當(dāng)?shù)姆艑挕?安全性與完整性需求由于該系統(tǒng)的開發(fā)基于B/S模式，就B/S模式的管理系統(tǒng)的工作模式而言，對軟件進(jìn)行安全性和完整性進(jìn)行考慮是系統(tǒng)中必不可少的一步，這直接關(guān)系到軟件使用是否可靠和安全，關(guān)系到系統(tǒng)使用過程中是否會(huì)出現(xiàn)重大問題而造成其他重大損失[7]。就管理系統(tǒng)而言還不得不考慮信息數(shù)據(jù)的完整性需求，因此接下來將從訪問權(quán)限的安全性系統(tǒng)的容錯(cuò)能力以及系統(tǒng)數(shù)據(jù)的完整性進(jìn)行分析，確定系統(tǒng)安全性和完整性的需求。（1）訪問權(quán)限的設(shè)置由于B/S模式的管理系統(tǒng)的訪問一般是通過瀏覽器發(fā)送URL地址對相應(yīng)頁面進(jìn)行訪問，因此系統(tǒng)必須具有一個(gè)訪問權(quán)限核實(shí)的模塊，在每個(gè)頁面加載前進(jìn)行調(diào)用，防止有其他動(dòng)機(jī)的不良用戶通過URL訪問其無權(quán)訪問的頁面進(jìn)而對系統(tǒng)數(shù)據(jù)進(jìn)行修改對系統(tǒng)造成損失，其中權(quán)限核實(shí)的內(nèi)容應(yīng)包括兩個(gè)部分：無任何權(quán)限的用戶試圖跳過登錄步驟直接訪問功能界面和具有某種權(quán)限的用戶登陸后試圖通過服務(wù)器中以保存的身份信息訪問其他無權(quán)訪問的頁面。每個(gè)用戶登錄后其訪問權(quán)限應(yīng)有時(shí)間限制，如果用戶長時(shí)間（其時(shí)間暫定為10分鐘）對系統(tǒng)操作無任何操作，再次訪問系統(tǒng)時(shí)，系統(tǒng)給出相應(yīng)的提示后自動(dòng)跳轉(zhuǎn)到登陸頁面要求用戶再次登錄。（2）系統(tǒng)的容錯(cuò)能力由于該系統(tǒng)許多模塊的功能都與時(shí)間有關(guān)，因此容錯(cuò)主要從時(shí)間沖突角度考慮。由于系統(tǒng)用戶都屬于學(xué)校成員，因此系統(tǒng)中關(guān)于時(shí)間的設(shè)定都是基于學(xué)周的，當(dāng)用戶對教室資源進(jìn)行占用或取消占用時(shí)，要對用戶所選時(shí)間與當(dāng)前時(shí)間進(jìn)行比對，用戶占用教室時(shí)選擇的占用時(shí)間應(yīng)該在當(dāng)前時(shí)間之后，用戶取消教室相關(guān)使用信息時(shí)，取消動(dòng)作發(fā)生的時(shí)間應(yīng)該在使用動(dòng)作落實(shí)之前。對于可以由用戶輸入內(nèi)容的模塊，要對用戶輸入內(nèi)容進(jìn)行核實(shí)，以免因?yàn)橛脩舨僮魇д`或者好奇輸入非法內(nèi)容而使系統(tǒng)產(chǎn)生不可預(yù)知的錯(cuò)誤。 （3）數(shù)據(jù)完整性管理系統(tǒng)離不開對數(shù)據(jù)的操作，因此對數(shù)據(jù)的完整性關(guān)系到系統(tǒng)運(yùn)轉(zhuǎn)是否正確，因此要求數(shù)據(jù)相互聯(lián)系正確，數(shù)據(jù)記錄完整數(shù)據(jù)項(xiàng)，相同的數(shù)據(jù)在不同的表格中應(yīng)該一致。其具體內(nèi)容見下一章數(shù)據(jù)庫設(shè)計(jì)部分。 數(shù)據(jù)流程圖與功能劃分由于學(xué)生以及教師使用該系統(tǒng)的操作相對簡單且功能劃分也相對明確，因此對于學(xué)生和教師功能模塊在此章暫不贅述，具體內(nèi)容將在下兩章講述。而管理員模塊的功能相對來說較為復(fù)雜，無論是數(shù)據(jù)管理還是排課過程都涉及到與外界的數(shù)據(jù)交換，因此對該模塊建立數(shù)據(jù)流程圖，如圖31。下面將通過數(shù)據(jù)流程圖對管理員模塊尤其是排課過程進(jìn)行功能劃分，確定由系統(tǒng)完成的功能以及需要人進(jìn)行的操作。由于排課過程涉及課程、班級、教師和教室等多方面的信息，因此排課過程不可能由軟件獨(dú)立完成，現(xiàn)在對排課流程進(jìn)行描述，在描述過程中確定系統(tǒng)邊界，明確系統(tǒng)功能。（1）由于排課之前學(xué)校要對本學(xué)期所有應(yīng)該安排的課程進(jìn)行選定，因此系統(tǒng)應(yīng)生成最新教室資源的統(tǒng)計(jì)表，教務(wù)工作者在課程安排時(shí)要注意課程安排的總學(xué)時(shí)應(yīng)該不超過本學(xué)期教室時(shí)間資源總數(shù)的80%，以免課程過多最終導(dǎo)致部分課程無法調(diào)度安排失敗。（2）排課之前教務(wù)人員需要手工做的工作有：確定本學(xué)期所有需要安排的課程；確定每門課程需要出席的班級；確定每門課程的任課教師；確定每門課程上課所需教室的類型；確定每門課程開課的學(xué)周；確定每門課程的總學(xué)時(shí)數(shù)。以上數(shù)據(jù)處理完成后將其與本學(xué)期教師變動(dòng)信息、本學(xué)期所有入學(xué)班級信息、本學(xué)期所有入學(xué)學(xué)生信息輸入至預(yù)先設(shè)定好格式的Excel表格中，之后將表格提交至系統(tǒng)管理員。圖31 教室管理系統(tǒng)管理員模塊數(shù)據(jù)流程圖 （3）管理員使用系統(tǒng)將上步中提交的Excel文件導(dǎo)入數(shù)據(jù)庫。在導(dǎo)入數(shù)據(jù)之前，管理員應(yīng)將上學(xué)期已失效的數(shù)據(jù)刪除并設(shè)置本學(xué)期的起始截止時(shí)間，該功能由系統(tǒng)實(shí)現(xiàn)，系統(tǒng)導(dǎo)入結(jié)束顯示導(dǎo)入失敗的信息，由管理員和教務(wù)人員配合對導(dǎo)入失敗的信息進(jìn)行核對（核對過程屬于人工操作），核對完成后再次將正確的數(shù)據(jù)導(dǎo)入數(shù)據(jù)庫。（4）當(dāng)確定所有數(shù)據(jù)已經(jīng)成功導(dǎo)入后，管理員可以開始使用系統(tǒng)進(jìn)行排課，排課程序執(zhí)行結(jié)束后，系統(tǒng)生成安排失敗課程的報(bào)表，管理員將此表交至教務(wù)人員，然后教務(wù)人員根據(jù)失敗課程的任課教師以及所有出席班級的現(xiàn)有課程通過手工方式安排課程的上課時(shí)間，若時(shí)間仍無法調(diào)度成功可以考慮更換任課教師或?qū)⒄n程安排至非正常授課時(shí)間（如周末或者晚上）。（5）教務(wù)人員將安排信息提交至系統(tǒng)管理員，有管理員使用系統(tǒng)的手工排課功能對課程進(jìn)行空間安排，若不成功則返回步驟（4）直至全部課程安排成功。 數(shù)據(jù)字典在上一節(jié)中通過數(shù)據(jù)流圖對系統(tǒng)進(jìn)行了邊界劃分，本節(jié)將以數(shù)據(jù)字典的形式具體說明數(shù)據(jù)流圖中的主要數(shù)據(jù)對象的信息，以便開發(fā)過程中的程序設(shè)計(jì)及數(shù)據(jù)庫設(shè)計(jì)。名字：教學(xué)樓基本信息描述：本校所有教學(xué)樓的信息定義：教學(xué)樓基本信息=教學(xué)樓ID+教學(xué)樓所在校區(qū)+教學(xué)樓名稱位置：保存至數(shù)據(jù)庫名字：教室基本信息描述：本校全部教室的基本信息定義：教室基本信息=教室ID+所屬教學(xué)樓ID+教室類型+教室座位數(shù)位置：保存至數(shù)據(jù)庫名字：統(tǒng)計(jì)的教室數(shù)據(jù)別名：教室統(tǒng)計(jì)一覽表描述：對本校全部教室按校區(qū)類型和大小進(jìn)行分類統(tǒng)計(jì)定義：教室統(tǒng)計(jì)一覽表=教室所在校區(qū)+教室類型+教室大小+該類教室總數(shù)位置：輸出至打印機(jī)名字：課程及用戶信息別名：教務(wù)處學(xué)期數(shù)據(jù)報(bào)表定義：教務(wù)處學(xué)期數(shù)據(jù)報(bào)表=教師表+課程信息表+班級信息表+學(xué)生表位置：Excel文檔名字：課程信息描述：本學(xué)期所有學(xué)要安排的課程信息定義：課程信息=課程ID+課程名+課程起始學(xué)周+課程結(jié)束學(xué)周+課程全部課時(shí)+開課學(xué)院+任課教師ID+所需教室類型+出席課程班級位置：保存至數(shù)據(jù)庫 教務(wù)處學(xué)期數(shù)據(jù)表名稱：課程安排信息描述：系統(tǒng)對課程上課地點(diǎn)的安排結(jié)果定義：課程安排信息=安排編號+上課教室編號+上課星期+上課課節(jié)+任課教師ID位置：保存至數(shù)據(jù)庫名稱：課程時(shí)間安排信息別名：手工課程安排時(shí)間表描述：教務(wù)人員提供的用于課程手動(dòng)安排的課程時(shí)間信息定義：課程時(shí)間安排信息=課程ID+教室校區(qū)+教室類型+上課人數(shù)+課程起始學(xué)周+課程結(jié)束學(xué)周+上課星期+上課課節(jié)位置：保存至數(shù)據(jù)庫名稱：用戶信息描述：系統(tǒng)所有用戶的信息定義：用戶信息=教師信息+學(xué)生信息+管理員信息位置：保存至數(shù)據(jù)庫 教務(wù)處學(xué)期數(shù)據(jù)報(bào)表名稱：教師信息描述：本學(xué)期所有進(jìn)行授課的教師的基本信息定義：教師信息=教師ID+教師名稱+教師所屬學(xué)院+個(gè)人密碼位置：保存至數(shù)據(jù)庫 教務(wù)處學(xué)期數(shù)據(jù)表名稱：學(xué)生信息描述：所有在校學(xué)生的基本信息定義：學(xué)生信息=學(xué)生ID+學(xué)生姓名+學(xué)生所在班級ID+學(xué)生密碼位置：保存至數(shù)據(jù)庫 教務(wù)處學(xué)期數(shù)據(jù)表名稱：班級信息描述：本校全部班級的信息定義：班級信息=班級ID+班級入學(xué)年份+班級所屬學(xué)院+班級所屬專業(yè)+班級編號+班級學(xué)生人數(shù)位置：保存至數(shù)據(jù)庫 教務(wù)處學(xué)期數(shù)據(jù)表 本章小結(jié)本章的需求分析主要介紹了系統(tǒng)開發(fā)前進(jìn)行的準(zhǔn)備工作，系統(tǒng)需求分析做的好壞直接關(guān)系到系統(tǒng)開發(fā)過程的難易程度，因此本章從多個(gè)角度對系統(tǒng)進(jìn)行描述，第一節(jié)問題定義的內(nèi)容是開發(fā)者在和用戶進(jìn)行溝通后從用戶的角度確定系統(tǒng)開發(fā)主要該解決的問題；第二節(jié)可行性分析是綜合考慮各方面的客觀因素確定本系統(tǒng)是否可以去研究開發(fā)；第三節(jié)數(shù)據(jù)流程圖及功能劃分的內(nèi)容是在了解用戶的需求后，綜合考慮當(dāng)今技術(shù)背景，通過對整個(gè)系統(tǒng)數(shù)據(jù)的流動(dòng)對系統(tǒng)的邊界進(jìn)行明確的劃分，確定了那些工作應(yīng)由系統(tǒng)實(shí)現(xiàn)，那些內(nèi)容需要人配合系統(tǒng)實(shí)現(xiàn)；最后一節(jié)是對第三節(jié)的補(bǔ)充，以數(shù)據(jù)字典的形式解釋數(shù)據(jù)流程圖中出現(xiàn)的主要的數(shù)據(jù)對象的內(nèi)容。第4章 數(shù)據(jù)庫設(shè)計(jì) 第4章 數(shù)據(jù)庫設(shè)計(jì) 數(shù)據(jù)庫設(shè)計(jì)數(shù)據(jù)庫設(shè)計(jì)是系統(tǒng)設(shè)計(jì)中必不可少的一個(gè)階段，教室管理系統(tǒng)屬于一個(gè)信息管理系統(tǒng)，而信息管理系統(tǒng)的本質(zhì)就是一個(gè)對數(shù)據(jù)進(jìn)行管理的工具，因此數(shù)據(jù)庫設(shè)計(jì)的好壞直接關(guān)系著管理的復(fù)雜程度。對數(shù)據(jù)庫的設(shè)計(jì)步驟如下：圖 41 教室管理系統(tǒng)數(shù)據(jù)庫總體結(jié)構(gòu)圖（1）確定使用中小型數(shù)據(jù)庫管理系統(tǒng)MySQL作為系統(tǒng)數(shù)據(jù)庫，并使用PHP語言編