基于二分圖的畢業(yè)設(shè)計(jì)選題系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

舒清錄

（滇西科技師范學(xué)院智能與信息工程學(xué)院，臨滄677000）

0 引言

畢業(yè)設(shè)計(jì)作為學(xué)生在校學(xué)習(xí)成果檢驗(yàn)的最后一個(gè)教學(xué)環(huán)節(jié)，是非常重要和必要的。但從選題到材料歸檔的整個(gè)流程是一個(gè)漫長(zhǎng)和繁雜的過(guò)程，特別是選題環(huán)節(jié)是整個(gè)過(guò)程的核心。從傳統(tǒng)做法來(lái)看，教師報(bào)選題，相關(guān)負(fù)責(zé)人審核、發(fā)布，學(xué)生在選題列表中選題，專業(yè)負(fù)責(zé)人根據(jù)學(xué)生選報(bào)情況分配選題。如果學(xué)生和選題規(guī)模小，完成選題任務(wù)任意，滿意率和得題率容易得到保證，相反查找、匹配工作量大且效果不好，有時(shí)需要進(jìn)行多輪次篩選才能解決問(wèn)題，效率低下。

畢業(yè)設(shè)計(jì)選題是最后一學(xué)期的教學(xué)環(huán)節(jié)，因各種原因部分學(xué)生不在校，導(dǎo)致選題活動(dòng)不能有效開(kāi)展，應(yīng)該充分利用網(wǎng)絡(luò)時(shí)代的Web 技術(shù)，打破時(shí)空限制。以往系統(tǒng)較多采用PC 端的B/S 結(jié)構(gòu)，在移動(dòng)設(shè)備上展示效果不好，如果設(shè)計(jì)一款既能在PC 瀏覽器上查看，同時(shí)也能很好的在平板、手機(jī)等移動(dòng)設(shè)備上展示的系統(tǒng)，能免去了維護(hù)系統(tǒng)帶來(lái)的不便。

綜上所述，開(kāi)發(fā)一款能適應(yīng)不同設(shè)備的、快速的、師生滿意率全局最優(yōu)的系統(tǒng)是很有必要的。

1 系統(tǒng)分析

1.1 系統(tǒng)簡(jiǎn)要概述

從實(shí)際應(yīng)用需求來(lái)看，系統(tǒng)主要針對(duì)教師、學(xué)生、管理員3 類人員，他們各自完成各自的任務(wù)。主要包括的功能模塊有：基礎(chǔ)信息管理（專業(yè)、班級(jí)、部門、教師信息、學(xué)生信息、課題來(lái)源等）、學(xué)生自報(bào)選題管理模塊、選題申報(bào)和審核管理模塊、相關(guān)課程成績(jī)管理模塊、教師期望問(wèn)卷調(diào)查管理模塊、基礎(chǔ)數(shù)據(jù)導(dǎo)入/導(dǎo)出管理模塊、郵件通知管理模塊、用戶身份驗(yàn)證管理模塊、系統(tǒng)參數(shù)設(shè)置管理模塊等。圖1為系統(tǒng)的用例圖。

1.2 系統(tǒng)功能

（1）學(xué)生角色

學(xué)生身份驗(yàn)證成功后，可維護(hù)自己的基礎(chǔ)信息；在系統(tǒng)規(guī)定的時(shí)間內(nèi)進(jìn)行自報(bào)選題，如果通過(guò)審批則不需要進(jìn)行下一步的選題；當(dāng)管理員設(shè)置允許選題后，可根據(jù)多種方式查詢、瀏覽或下載選題信息；對(duì)自己感興趣的選題，參加選題的教師期望問(wèn)卷調(diào)查和志愿選擇，作為算法的影響因子；學(xué)生還可查在規(guī)定時(shí)間范圍內(nèi)退選；系統(tǒng)自動(dòng)匹配完成后，學(xué)生可以查看自己的選題情況，獲取選題相關(guān)的附加等信息。

（2）教師角色

教師身份驗(yàn)證成功后，可維護(hù)自己的基礎(chǔ)信息；在系統(tǒng)規(guī)定的時(shí)間范圍內(nèi)進(jìn)行選題申報(bào)，填寫信息時(shí)除了一些基本的信息外，還需要規(guī)定此選題與學(xué)生的哪些課程相關(guān)以及生成對(duì)學(xué)生的期望問(wèn)卷調(diào)查；能查看學(xué)院審批選題申報(bào)情況信息，并對(duì)未通過(guò)的選題進(jìn)行完善；系統(tǒng)智能匹配操作流程完成后，教師可查看申報(bào)選題的被選情況，并導(dǎo)出學(xué)生名單。

（3）管理員角色

管理員首先通過(guò)Excel 文件批量導(dǎo)入畢業(yè)學(xué)生和指導(dǎo)老師信息，同時(shí)也提供單條信息編輯；確定各指導(dǎo)教師的最大指導(dǎo)量；進(jìn)行系統(tǒng)參數(shù)設(shè)置，包括學(xué)生自報(bào)選題的起止時(shí)間、教師申報(bào)選題的起止時(shí)間、學(xué)生選題的起止時(shí)間、學(xué)生的最多志愿數(shù)等；對(duì)教師提交的選題進(jìn)行分類并提交給相關(guān)人員進(jìn)行審核；調(diào)用二分圖算法進(jìn)行選題和學(xué)生智能匹配；匹配流程結(jié)束后可以導(dǎo)出選題被選情況表，系統(tǒng)自動(dòng)根據(jù)用戶留的郵件發(fā)出通知。

1.3 系統(tǒng)技術(shù)路線選擇

總體上采用了PHP+MySQL+Bootstrap+jQuery+AJAX 組合的技術(shù)路線。本系統(tǒng)采用WampServer2.5集成開(kāi)發(fā)包，其中PHP 版本為5.5.12，Apache 版本為2.4.9，MySQL 版本為5.6.17；為了在瀏覽器端（視圖層）有良好的展示效果和適應(yīng)性，前端采用了Bootstrap 框架（移動(dòng)設(shè)備優(yōu)先，插件集豐富，強(qiáng)大的柵格系統(tǒng)[1-2]）；前端與后臺(tái)通過(guò)jQuery+AJAX 進(jìn)行數(shù)據(jù)交換，充分利用jQuery 良好的瀏覽器兼容性和AJAX 的高效性[3]（與服務(wù)器進(jìn)行少量數(shù)據(jù)交換，即可實(shí)現(xiàn)網(wǎng)頁(yè)局部異步刷新，增強(qiáng)了用戶的體驗(yàn)度）。

2 系統(tǒng)設(shè)計(jì)

2.1 系統(tǒng)流程

管理員作為此系統(tǒng)總體控制者，決定了教師和學(xué)生能否使用[4]，教師在線申報(bào)課題并設(shè)定與選題相關(guān)的課程和教師對(duì)課題的期望調(diào)查表，學(xué)生在線完成課題選擇并完成期望調(diào)查和志愿選擇，系統(tǒng)以期望調(diào)查、志愿選擇和課程成績(jī)?yōu)榫C合權(quán)值調(diào)用二分圖算法完成主動(dòng)匹配過(guò)程，最后學(xué)生和教師可以在線查看匹配結(jié)果。具體的系統(tǒng)業(yè)務(wù)流程如圖2 所示。

圖2 系統(tǒng)業(yè)務(wù)流程圖

2.2 選題與學(xué)生自動(dòng)匹配算法

（1）二分圖及其相關(guān)概念

在系統(tǒng)設(shè)計(jì)時(shí)，把選題問(wèn)題歸結(jié)為選題集合和學(xué)生集合的匹配問(wèn)題，而選題之間、學(xué)生集合之間又不存在關(guān)聯(lián)情況。所以此問(wèn)題屬于如何把選題資源合理分配給學(xué)生，為了使問(wèn)題得到最優(yōu)解、學(xué)生和老師都比較滿意，采用二分圖[5]模型來(lái)建模，圖3 為其基本模型。

圖3 二分圖模型圖

二分圖：無(wú)向圖G=中，集合V1 和集合V2為頂點(diǎn)集V 的兩個(gè)子集且V=V1∪V2，V1∩V2=Φ；對(duì)?∈E，有u∈V1，e∈V2，則G 稱為二分圖。

匹配：設(shè)G=為無(wú)向圖，邊集E'?E，若E'中任意兩條邊沒(méi)公共端點(diǎn)，則E'為G 中的一個(gè)匹配。其中邊數(shù)最多的匹配稱為最大匹配。M 為G 的一個(gè)最大匹配，若|M|=min{|V1|，|V2|}，則稱此匹配為完全匹配，也稱作完備匹配。特別的當(dāng)|V2|==|V1|稱為完美匹配。

（2）KM 算法

KM 算法是一個(gè)可用于對(duì)二分圖匹配問(wèn)題進(jìn)行求解[6]的算法，適合求二分圖完備匹配下的最大權(quán)匹配。在本系統(tǒng)中，取出學(xué)生集合X 和選題集合Y，對(duì)它們之間的連接X(jué)iYj有權(quán)W（ij課程成績(jī)+問(wèn)卷+志愿計(jì)算的綜合權(quán)值），得到一種匹配使Wij之和的值最大。

在本系統(tǒng)中權(quán)值W 的約定為：Wi=Vi+ a * C_value+b*Q_value，Vi=V_value/V×（V-i+1）。其中，a、b 為比例（取值為0-1 之間的小數(shù)），V 為志愿轉(zhuǎn)換的值，W為權(quán)重，C_value 為多門或一門課程的平均成績(jī)（0-100之間），Q_value 為期望問(wèn)卷調(diào)查表分?jǐn)?shù)（0-100 之間）。

樸素的KM 算法的時(shí)間復(fù)雜度為Θ（n4），增廣路需要找Θ（n）次。為了使時(shí)間復(fù)雜度減少到Θ（n3），給每個(gè)y 頂點(diǎn)一個(gè)起始量為無(wú)窮大的“松弛量-slack”函數(shù)。找增廣路時(shí)，如果邊不在圖中，則slack[j]=min（slack[j]，X[i]+Y[j]-W[i][j]）。

KM 算法要求二分圖得有左邊點(diǎn)數(shù)=右邊點(diǎn)數(shù)，且只能處理一對(duì)一任務(wù)[7]。在畢業(yè)設(shè)計(jì)選題的實(shí)際操作中，一個(gè)學(xué)生可選擇多個(gè)題目，一個(gè)題目也可以采用合作的形式被多個(gè)學(xué)生選擇，不符合KM 算法要求。為了能實(shí)現(xiàn)學(xué)生和選題一一對(duì)應(yīng)且允許合作，考慮把一個(gè)合作選題分成多個(gè)獨(dú)立選題，例如題號(hào)為“20190101”的“基于FRID 的學(xué)生考勤管理系統(tǒng)”，限選2 人，則把題號(hào)改為“20190101-01”，對(duì)應(yīng)的題目“基于FRID 的學(xué)生考勤管理系統(tǒng)——學(xué)生請(qǐng)假端”和題號(hào)為“20190101-02”的“基于FRID 的學(xué)生考勤管理系統(tǒng)——管審批端”。如果學(xué)生和選題數(shù)不相同時(shí)，構(gòu)造效率矩陣時(shí)取較大值構(gòu)成方陣，此兩種處理即可以解決此問(wèn)題。

3 系統(tǒng)實(shí)現(xiàn)

系統(tǒng)大部分程序結(jié)構(gòu)一致，都是通過(guò)HTML 文件實(shí)現(xiàn)頁(yè)面構(gòu)建，JS 文件負(fù)責(zé)頁(yè)面動(dòng)作處理，PHP 文件負(fù)責(zé)獲取和處理數(shù)據(jù)。JS 文件作為HTML 和PHP 的數(shù)據(jù)傳遞者，PHP 負(fù)責(zé)與數(shù)據(jù)庫(kù)的查詢。為了保證代碼的有效復(fù)用，定義了幾個(gè)公共類文件，例如connDB.php負(fù)責(zé)連接數(shù)據(jù)，functions.php 文件負(fù)責(zé)一些公共方法（如頁(yè)面跳轉(zhuǎn)，加密/解密，過(guò)濾掉非法字符等）

下面以用戶登錄為例進(jìn)行闡述。

3.1 HTML的文件結(jié)構(gòu)

（1）在間加入下列內(nèi)容加入charset="utf-8"保證頁(yè)面的字符能正常顯示；考慮到移動(dòng)端瀏覽器問(wèn)題，將頁(yè)面以原始比例顯示，并不支持縮放，保證瀏覽效果；引入Bootstrap 框架需要的必要文件。

此處重點(diǎn)是class 的選擇和id 的設(shè)定，class 決定顯示的樣式，id 決定能否方便被JS 文件感知、獲取其值，info 空區(qū)域用于錯(cuò)誤提示。

（3）調(diào)用JS 方法處理用戶行為

在HTML 文檔的之前加入，確保頁(yè)面渲染效果，并調(diào)用自定義的功能，例如用戶名、密碼、驗(yàn)證碼不能為空，用戶身份信息是否正確等。

3.2 JS處理文件實(shí)現(xiàn)

總的處理流程為：使用$（document）.ready（）快速加載代碼；通過(guò)$（'#登錄按鈕id'）.click（）為登錄按鈕添加點(diǎn)擊事件，響應(yīng)點(diǎn)擊動(dòng)作；通過(guò)$（"#元素id"）.val（）獲取HTML 上的輸入值；調(diào)用jQuery 的AJAX 方法，并設(shè)置type、url、data、dataType、success 以及error 的參數(shù)或動(dòng)作。

（3）PHP 文件實(shí)現(xiàn)總的處理流程為：使用require_once 引入數(shù)據(jù)連接類；利用session_start 開(kāi)啟session，便于記錄關(guān)鍵的用戶信息并在頁(yè)面之間傳遞；通過(guò)$_POST 獲取用戶在HTML 頁(yè)面輸入的內(nèi)容；調(diào)用MySQL 的query 方法執(zhí)行SQL 語(yǔ)句并取得數(shù)據(jù)庫(kù)數(shù)據(jù)；對(duì)返回?cái)?shù)據(jù)進(jìn)行斷，并把用戶名稱、用戶類型、身份驗(yàn)證標(biāo)志（成功或失敗）以JSON 格式返回，傳遞給JS 解析并作相應(yīng)處理。

（4）實(shí)現(xiàn)的部分界面

圖4 系統(tǒng)部分移動(dòng)端效果圖

4 結(jié)語(yǔ)

本畢業(yè)設(shè)計(jì)選題系統(tǒng)做到了一切都在網(wǎng)上實(shí)現(xiàn)，提高了工作效率，避免了重復(fù)勞動(dòng)，且對(duì)使用端的設(shè)備能很好的兼容，采用二分圖的最優(yōu)匹配算法，合理地構(gòu)造效率矩陣權(quán)值，使用學(xué)生和教師的整體滿意度最高，真正實(shí)現(xiàn)課題的雙向選擇，極大提高選題效率。在2018 年度選題系統(tǒng)試用中表現(xiàn)良好，達(dá)到了預(yù)期的效果。