基于二分圖的畢業設計選題系統設計與實現

舒清錄

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

0 引言

畢業設計作為學生在校學習成果檢驗的最后一個教學環節，是非常重要和必要的。但從選題到材料歸檔的整個流程是一個漫長和繁雜的過程，特別是選題環節是整個過程的核心。從傳統做法來看，教師報選題，相關負責人審核、發布，學生在選題列表中選題，專業負責人根據學生選報情況分配選題。如果學生和選題規模小，完成選題任務任意，滿意率和得題率容易得到保證，相反查找、匹配工作量大且效果不好，有時需要進行多輪次篩選才能解決問題，效率低下。

畢業設計選題是最后一學期的教學環節，因各種原因部分學生不在校，導致選題活動不能有效開展，應該充分利用網絡時代的Web 技術，打破時空限制。以往系統較多采用PC 端的B/S 結構，在移動設備上展示效果不好，如果設計一款既能在PC 瀏覽器上查看，同時也能很好的在平板、手機等移動設備上展示的系統，能免去了維護系統帶來的不便。

綜上所述，開發一款能適應不同設備的、快速的、師生滿意率全局最優的系統是很有必要的。

1 系統分析

1.1 系統簡要概述

從實際應用需求來看，系統主要針對教師、學生、管理員3 類人員，他們各自完成各自的任務。主要包括的功能模塊有：基礎信息管理（專業、班級、部門、教師信息、學生信息、課題來源等）、學生自報選題管理模塊、選題申報和審核管理模塊、相關課程成績管理模塊、教師期望問卷調查管理模塊、基礎數據導入/導出管理模塊、郵件通知管理模塊、用戶身份驗證管理模塊、系統參數設置管理模塊等。圖1為系統的用例圖。

1.2 系統功能

（1）學生角色

學生身份驗證成功后，可維護自己的基礎信息；在系統規定的時間內進行自報選題，如果通過審批則不需要進行下一步的選題；當管理員設置允許選題后，可根據多種方式查詢、瀏覽或下載選題信息；對自己感興趣的選題，參加選題的教師期望問卷調查和志愿選擇，作為算法的影響因子；學生還可查在規定時間范圍內退選；系統自動匹配完成后，學生可以查看自己的選題情況，獲取選題相關的附加等信息。

（2）教師角色

教師身份驗證成功后，可維護自己的基礎信息；在系統規定的時間范圍內進行選題申報，填寫信息時除了一些基本的信息外，還需要規定此選題與學生的哪些課程相關以及生成對學生的期望問卷調查；能查看學院審批選題申報情況信息，并對未通過的選題進行完善；系統智能匹配操作流程完成后，教師可查看申報選題的被選情況，并導出學生名單。

（3）管理員角色

管理員首先通過Excel 文件批量導入畢業學生和指導老師信息，同時也提供單條信息編輯；確定各指導教師的最大指導量；進行系統參數設置，包括學生自報選題的起止時間、教師申報選題的起止時間、學生選題的起止時間、學生的最多志愿數等；對教師提交的選題進行分類并提交給相關人員進行審核；調用二分圖算法進行選題和學生智能匹配；匹配流程結束后可以導出選題被選情況表，系統自動根據用戶留的郵件發出通知。

1.3 系統技術路線選擇

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

2 系統設計

2.1 系統流程

管理員作為此系統總體控制者，決定了教師和學生能否使用[4]，教師在線申報課題并設定與選題相關的課程和教師對課題的期望調查表，學生在線完成課題選擇并完成期望調查和志愿選擇，系統以期望調查、志愿選擇和課程成績為綜合權值調用二分圖算法完成主動匹配過程，最后學生和教師可以在線查看匹配結果。具體的系統業務流程如圖2 所示。

圖2 系統業務流程圖

2.2 選題與學生自動匹配算法

（1）二分圖及其相關概念

在系統設計時，把選題問題歸結為選題集合和學生集合的匹配問題，而選題之間、學生集合之間又不存在關聯情況。所以此問題屬于如何把選題資源合理分配給學生，為了使問題得到最優解、學生和老師都比較滿意，采用二分圖[5]模型來建模，圖3 為其基本模型。

圖3 二分圖模型圖

二分圖：無向圖G=中，集合V1 和集合V2為頂點集V 的兩個子集且V=V1∪V2，V1∩V2=Φ；對?∈E，有u∈V1，e∈V2，則G 稱為二分圖。

匹配：設G=為無向圖，邊集E'?E，若E'中任意兩條邊沒公共端點，則E'為G 中的一個匹配。其中邊數最多的匹配稱為最大匹配。M 為G 的一個最大匹配，若|M|=min{|V1|，|V2|}，則稱此匹配為完全匹配，也稱作完備匹配。特別的當|V2|==|V1|稱為完美匹配。

（2）KM 算法

KM 算法是一個可用于對二分圖匹配問題進行求解[6]的算法，適合求二分圖完備匹配下的最大權匹配。在本系統中，取出學生集合X 和選題集合Y，對它們之間的連接XiYj有權W（ij課程成績+問卷+志愿計算的綜合權值），得到一種匹配使Wij之和的值最大。

在本系統中權值W 的約定為：Wi=Vi+ a * C_value+b*Q_value，Vi=V_value/V×（V-i+1）。其中，a、b 為比例（取值為0-1 之間的小數），V 為志愿轉換的值，W為權重，C_value 為多門或一門課程的平均成績（0-100之間），Q_value 為期望問卷調查表分數（0-100 之間）。

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

KM 算法要求二分圖得有左邊點數=右邊點數，且只能處理一對一任務[7]。在畢業設計選題的實際操作中，一個學生可選擇多個題目，一個題目也可以采用合作的形式被多個學生選擇，不符合KM 算法要求。為了能實現學生和選題一一對應且允許合作，考慮把一個合作選題分成多個獨立選題，例如題號為“20190101”的“基于FRID 的學生考勤管理系統”，限選2 人，則把題號改為“20190101-01”，對應的題目“基于FRID 的學生考勤管理系統——學生請假端”和題號為“20190101-02”的“基于FRID 的學生考勤管理系統——管審批端”。如果學生和選題數不相同時，構造效率矩陣時取較大值構成方陣，此兩種處理即可以解決此問題。

3 系統實現

系統大部分程序結構一致，都是通過HTML 文件實現頁面構建，JS 文件負責頁面動作處理，PHP 文件負責獲取和處理數據。JS 文件作為HTML 和PHP 的數據傳遞者，PHP 負責與數據庫的查詢。為了保證代碼的有效復用，定義了幾個公共類文件，例如connDB.php負責連接數據，functions.php 文件負責一些公共方法（如頁面跳轉，加密/解密，過濾掉非法字符等）

下面以用戶登錄為例進行闡述。

3.1 HTML的文件結構

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

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

（3）調用JS 方法處理用戶行為

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

3.2 JS處理文件實現

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

（3）PHP 文件實現總的處理流程為：使用require_once 引入數據連接類；利用session_start 開啟session，便于記錄關鍵的用戶信息并在頁面之間傳遞；通過$_POST 獲取用戶在HTML 頁面輸入的內容；調用MySQL 的query 方法執行SQL 語句并取得數據庫數據；對返回數據進行斷，并把用戶名稱、用戶類型、身份驗證標志（成功或失敗）以JSON 格式返回，傳遞給JS 解析并作相應處理。

（4）實現的部分界面

圖4 系統部分移動端效果圖

4 結語

本畢業設計選題系統做到了一切都在網上實現，提高了工作效率，避免了重復勞動，且對使用端的設備能很好的兼容，采用二分圖的最優匹配算法，合理地構造效率矩陣權值，使用學生和教師的整體滿意度最高，真正實現課題的雙向選擇，極大提高選題效率。在2018 年度選題系統試用中表現良好，達到了預期的效果。