基于分治策略歸并算法的考研擇校指南平臺研究

李博涵 王紅蕾 青島黃海學院

據(jù)最新統(tǒng)計，2019年研究生招生考試考生已達285萬人，比去年增加47萬人。但是，考研時對報考學校的選擇成為很多應屆生面臨的首要問題。有些同學因為不了解報考的相關知識而達不到預期的報考效果，甚至有些同學因此錯過了深造的機會。

1 歸并算法與分治策略

對于此類問題我們首先考慮的是歸并算法，于是我們在已有的歸并算法基礎上做出了改進。首先我們先向內(nèi)存申請空間，該空間存儲排序序列之和。然后設置狀態(tài)指針，賦予指針初始值進行合并空間操作，這一步的目的是進行目標院校的聚類操作，設置目標狀態(tài)量作為指針改進原有的歸并算法，將目標院校，目標專業(yè)，師資力量，科研狀況，生活環(huán)境，學習氛圍以及綜合排名等作為序列。同時設置新的目標狀態(tài)量作為新的指針，用來合并分數(shù)、興趣、排名等序列與前序列進行擬合，執(zhí)行歸并操作。

本文在數(shù)據(jù)結(jié)構(gòu)上基于歸并技術，但在歸并技術上，我們改進的算法復雜度低，結(jié)構(gòu)相對簡單，實現(xiàn)相對容易，更實用，更適合數(shù)據(jù)聚類分析。擇校系統(tǒng)有大量的數(shù)據(jù)，它可以被視為采樣點，每個采樣點都有不同的屬性，輸出的結(jié)果是根據(jù)候選人的需要。根據(jù)不同屬性進行數(shù)據(jù)分類，從而找到最合適的學校類型信息。

2 改進的人工魚群算法

面對龐大的數(shù)據(jù)量與篩選數(shù)值，歸并算法執(zhí)行起來顯然力不從心，所以我們想到使用仿真技術的加持進行分治，兩者配合使用有效的縮短了查詢所用時間亦提高效率。

首先，輸入算法的初始值，包括人工魚的范圍、位置坐標、魚群的擁擠因子等等。將初始迭代次數(shù)設為0，然后在范圍內(nèi)生成n個隨機人工魚個體并計算隨機初始魚群中個體的食物濃度，并在公告欄中篩選出最大值。人工魚群個體通過模擬魚群的聚集和覓食行為，不斷地改變其狀態(tài)，經(jīng)過一定時間后產(chǎn)生新的魚群。每只人工魚移動一次后，它會檢查自己的狀態(tài)，并將其與公告板上的狀態(tài)進行比較。如果它比公告板更好，它會將其當前狀態(tài)更新到公告板。最后確定迭代次數(shù)是否達到最大值，如果達到最大值，則將結(jié)果輸出到公告板上，否則，將從改變狀態(tài)產(chǎn)生新的魚群開始繼續(xù)執(zhí)行。

根據(jù)人工魚群的行為描述可以得到每條人工魚個體都是依據(jù)其視線范圍搜尋其目前所處的境以及伙伴的狀況，由此達到幾個局部極值附近聚集人工魚的效果。通過這個方法我們不難發(fā)現(xiàn)目標函數(shù)值較大的人工魚聚集在較大的值域附近，從而得到全局極值域。

本文將人工魚群算法運用到擇校最優(yōu)解中，首先選取目標函數(shù)為考生的擇校信息與某學校的相似度最高，數(shù)學模型如下：

由以上步驟可知，人工魚算法可以在較短時間內(nèi)將某個數(shù)據(jù)最近距離的極值點匯聚在一起，但是考慮到考生在檢索過程中可能不會將所有元素都輸入或者一些用戶的檢索歷史比較少或者比較多，都會造成一定的誤差，因此本文又采用了稀疏矩陣的方法將該系統(tǒng)進行進一步完善。

3 稀疏矩陣

因為考生對學校的要求比較繁多，本文將這些檢索的信息進行融合，形成一種屬性，根據(jù)屬性相似來為數(shù)據(jù)稀疏的同學推薦一些學校。

通過計算考生檢索的相似度較高的信息，將它們列成一個集合{Uk}，記錄為稀疏矩陣，通過定義函數(shù)f(x，y，z)表示考生x與考生y關于某個要求的相似度。假設考生x與考生y都喜歡學術類比賽較多的學校，則 f(x，y，z)=1，否則 f(x，y，z)=0。可以通過以下算法進行描述：用 表示對學術類比賽的要求所占的比重，

之后設置一個閾值w，如果考生所輸入的對學術類比賽的數(shù)據(jù)量低于w，則引入考生的屬性，融合考生屬性后，預測評分計算公式為：

其中N(x)表示所有與用戶屬性x相似的用戶集合，rxi表示用戶x對科技類比賽興趣i預測值。

通過以上三種方法的結(jié)合，既可以將系統(tǒng)內(nèi)所含院校進行一個高效的分類，又可以更智能的為用戶匹配出適合自己的學校。

4 結(jié)語

本文采用計算機算法并進行初步模擬，驗證了算法的可行性，但是只有算法是遠遠不夠，我們還需要大量的數(shù)據(jù)來進行模擬，以此達到最優(yōu)的效果。從國內(nèi)研究現(xiàn)狀來看，大多數(shù)學者只分析了考研擇校的現(xiàn)狀及影響因素，并沒有建立考研擇校指南平臺，沒有真正為考研學生提供便利。本項目結(jié)合軟件建模和計算機算法，創(chuàng)建指南系統(tǒng)，為考研學生提供真正的便利。