基于背包問題與貪心算法的高效數(shù)據(jù)整合系統(tǒng)

◆劉順程 岳思穎 李楠鍵

基于背包問題與貪心算法的高效數(shù)據(jù)整合系統(tǒng)

◆劉順程 岳思穎 李楠鍵

（重慶郵電大學(xué)軟件工程學(xué)院 重慶 400065）

隨著互聯(lián)網(wǎng)+時代的到來，各行各業(yè)為使其業(yè)務(wù)更易于管理，紛紛將數(shù)據(jù)以及結(jié)構(gòu)化報表通過計算機(jī)進(jìn)行動態(tài)生成；這使得如何高效處理數(shù)據(jù)并生成結(jié)構(gòu)化體系成為了當(dāng)務(wù)之急，比如生成線上考試試卷、商品的規(guī)格參數(shù)列表、公司流程報表等。本文以高效數(shù)據(jù)整合算法為研究重點，分別介紹了傳統(tǒng)數(shù)據(jù)整合的方法與缺陷，同時重點介紹了基于背包問題與貪心算法的高效數(shù)據(jù)整合算法——一種更高效安全的數(shù)據(jù)整合框架。

背包問題；貪心算法；數(shù)據(jù)整合；容器組件

0 引言

隨著互聯(lián)網(wǎng)的普及，黨和國家號召充分利用互聯(lián)網(wǎng)資源，使得將各行各業(yè)的紙質(zhì)化資料進(jìn)行網(wǎng)絡(luò)化、虛擬化成為了趨勢。當(dāng)前傳統(tǒng)的數(shù)據(jù)整合方法在高并發(fā)環(huán)境中由于效率較低，易導(dǎo)致服務(wù)器系統(tǒng)崩潰。于是，基于背包問題與貪心算法的高效數(shù)據(jù)整合系統(tǒng)應(yīng)運(yùn)而生。

1 算法背景于傳統(tǒng)方法

1.1貪心算法

貪心算法的基本思路是從問題的某一個初始解出發(fā)一步一步地進(jìn)行,根據(jù)某個優(yōu)化測度,每一步都要確保能獲得局部最優(yōu)解。每一次只考量一個數(shù)據(jù)，是否選取該數(shù)據(jù)取決于是否滿足局部最優(yōu)的條件，直到把所有的數(shù)據(jù)枚舉完成，或者滿足了某優(yōu)化條件后，算法終止。從全局看來，每種選擇方案依賴于已作出的選擇，而不依賴于未作出的選擇；因此最終的結(jié)果也成為了該問題的最優(yōu)方案[1]。

1.2背包問題

背包問題是一種組合優(yōu)化的NP完全問題。問題可以簡單描述為：給定一組物品和一個背包，每個物品有其對應(yīng)的重量和價值，而背包則有其所能裝載重量的上限。因此，我們要通過合理選擇來使得在不超過背包裝載量的上限下，背包所裝載物品的價值盡可能地大。背包問題可以抽象成一個容器-物品填充模型，即當(dāng)前可供選擇的物品中，能否通過合理選擇，使得容器被填滿且其承載價值達(dá)到最大[2]。

1.3傳統(tǒng)方案與潛在問題

在傳統(tǒng)數(shù)據(jù)整合方案中，常常使用某種單一的數(shù)據(jù)類為物品，需求結(jié)構(gòu)體為容器，來進(jìn)行自動化數(shù)據(jù)組合生成需求結(jié)構(gòu)。首先構(gòu)建結(jié)構(gòu)體容器，使用相應(yīng)約束條件定義背包容量，隨后以每條數(shù)據(jù)的特性來進(jìn)行容器填充，當(dāng)容器中的約束條件達(dá)到預(yù)設(shè)值后，數(shù)據(jù)組合成功；若在遍歷完所有數(shù)據(jù)后仍沒有達(dá)到背包容器預(yù)設(shè)值，則數(shù)據(jù)組合失敗。然后又將另一種數(shù)據(jù)類定義為物品，相應(yīng)需求結(jié)構(gòu)體為容器，繼續(xù)進(jìn)行上述操作，直到將所有的結(jié)構(gòu)體所需的數(shù)據(jù)填充完成，數(shù)據(jù)整合結(jié)束。

隨著大數(shù)據(jù)時代的來臨，這種傳統(tǒng)方案暴露出了組合效率低下、存在線程死鎖風(fēng)險等諸多問題。例如，在實驗環(huán)境中，數(shù)據(jù)類物品存放于內(nèi)存中，遍歷數(shù)據(jù)能迅速完成；但是在實際生產(chǎn)環(huán)境中，數(shù)據(jù)類物品存放于數(shù)據(jù)庫中。相比于內(nèi)存讀取，數(shù)據(jù)庫的讀取速度是及其緩慢的；面對實際環(huán)境中的多線程、高并發(fā)的服務(wù)操作，傳統(tǒng)數(shù)據(jù)組合算法會對數(shù)據(jù)庫進(jìn)行反復(fù)讀寫，這樣極易造成數(shù)據(jù)庫連接數(shù)達(dá)到上限，從而引起數(shù)據(jù)庫阻塞，程序線程死鎖等惡劣情況，導(dǎo)致整個系統(tǒng)崩潰。

2 基于背包問題與貪心算法的高效數(shù)據(jù)填充方案

本方案的基于背包問題與貪心算法的高效數(shù)據(jù)填充系統(tǒng)，包括多背包容器組件、物品屬性組件、本地模擬填充組件和數(shù)據(jù)存儲組件。

2.1系統(tǒng)架構(gòu)

多背包容器組件，用于將傳統(tǒng)背包方案的單個容器擴(kuò)充為多個容器用于數(shù)據(jù)填充中對多種數(shù)據(jù)結(jié)構(gòu)體的描述。比如在實際的數(shù)據(jù)整合過程中，我們所需的填充項一定不止一個。于是，我們使用多背包容器組件來描述整個數(shù)據(jù)填充項集合，使得單次運(yùn)行該算法即可完成所有的數(shù)據(jù)填充，避免了多次操作數(shù)據(jù)庫易引起的問題。

物品屬性組件，用于將傳統(tǒng)方案中的數(shù)據(jù)集轉(zhuǎn)化為虛擬物品，虛擬物品在初始化后，需要調(diào)用本地模擬填充模塊進(jìn)行屬性賦值。比如將容器所需的某種數(shù)據(jù)虛擬化為物品，而該物品屬性數(shù)量一定大于傳統(tǒng)背包物品的兩個屬性（V，W），所以我們需要調(diào)用本地模擬填充模塊進(jìn)行數(shù)據(jù)庫查詢，將數(shù)據(jù)物品項的屬性進(jìn)行賦值，使其得到多重屬性，以便完善后續(xù)的填充需求。

本地模擬填充組件，用于將傳統(tǒng)數(shù)據(jù)整合算法中，反復(fù)讀取數(shù)據(jù)庫來提取數(shù)據(jù)進(jìn)行容器填充的過程轉(zhuǎn)化為只進(jìn)行一次數(shù)據(jù)庫提取；獲取所有數(shù)據(jù)信息后，首先對物品屬性組件的每個物品進(jìn)行屬性填充，從而記錄整合時候每個結(jié)構(gòu)體應(yīng)具備的約束條件；隨后使用貪心算法，在本地容器組件中對容器進(jìn)行數(shù)據(jù)填充，填充規(guī)則按照容器定義以及物品屬性，并使用貪心算法根據(jù)屬性權(quán)值進(jìn)行優(yōu)先集填充；直到所有的容器填充完成，本地模擬填充結(jié)束。

數(shù)據(jù)存儲組件，用于將傳統(tǒng)整合算法中通過模塊約束條件在數(shù)據(jù)庫中選取數(shù)據(jù)并進(jìn)行數(shù)據(jù)庫存儲轉(zhuǎn)化為通過本地模擬填充容器保存的相關(guān)數(shù)據(jù)直接存儲在數(shù)據(jù)庫中；從而讓系統(tǒng)獲得數(shù)據(jù)整合結(jié)果，使得數(shù)據(jù)庫的讀取次數(shù)再次減少，提升程序運(yùn)行效率。

2.2系統(tǒng)執(zhí)行流程

（1）通過需求結(jié)構(gòu)體構(gòu)造多個背包，并且設(shè)置為虛擬容器；

（2）向容器添加描述其屬性（如某某數(shù)據(jù)容器），直到所有虛擬容器添加完成；

（3）根據(jù)需求，創(chuàng)建單個或多個物品組件（使用容器完成），初始化物品組件的屬性均為Null；

（4）從數(shù)據(jù)庫讀取數(shù)據(jù)整合所需的所有相關(guān)數(shù)據(jù)；

（5）根據(jù)數(shù)據(jù)與相關(guān)需求，將S3中創(chuàng)建的物品組件進(jìn)行屬性填充，為每個物品容器的屬性進(jìn)行賦值，直到所有物品組件填充完畢；

（6）根據(jù)背包問題，依照貪心算法，對S1中創(chuàng)建的背包容器進(jìn)行物品填充，以當(dāng)前容器指向的描述物品（屬性），對物品的當(dāng)前的屬性權(quán)值由高到低為策略繼續(xù)選擇，將選擇結(jié)果保存在當(dāng)前背包容器中；

（7）判斷本地模擬填充的背包容器是否滿足需求數(shù)據(jù)的約束。若滿足則準(zhǔn)備開始填充下一個背包容器執(zhí)行S8，否則執(zhí)行S9；

（8）判斷背包中所有容器是否填充完成，若完成則執(zhí)行S12,否則執(zhí)行S6；

（9）判斷在剩余的物品數(shù)據(jù)（當(dāng)前物品沒有匹配的屬性）中是否有物品集合可供選擇，若有執(zhí)行S10，否則執(zhí)行S11；

（10）調(diào)整該物品的屬性權(quán)值，允許背包容器進(jìn)行填充，執(zhí)行S6；

（11）拋出錯誤，算法運(yùn)行失敗，返回空值，系統(tǒng)結(jié)束；

（12）將本地模擬填充模塊填充完成的背包容器數(shù)據(jù)，存儲在數(shù)據(jù)庫中；

（13）所有調(diào)用完成，系統(tǒng)結(jié)束。

3 結(jié)束語

進(jìn)入互聯(lián)網(wǎng)+時代，眾多行業(yè)都需要更高效精準(zhǔn)的數(shù)據(jù)管理方案?；诒嘲鼏栴}與貪心算法的高效數(shù)據(jù)整合系統(tǒng)，能將數(shù)據(jù)集進(jìn)行自動整合并提供更安全、更高效的解決方案，同時有效解決了傳統(tǒng)方案中存在的安全隱患。相信該系統(tǒng)在未來的大數(shù)據(jù)領(lǐng)域中會得到更好的發(fā)展。

[1]常友渠，肖貴元，曾敏.貪心算法的探討與研究[J].重慶電力高等專科學(xué)校學(xué)報，2008.

[2]史今馳.背包問題的實用求解算法研究[D].山東;山東大學(xué)，2005.