索紅軍

(渭南師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院,陜西渭南 714099)

【信息科學(xué)與工程研究】

最優(yōu)數(shù)字分配策略分析研究

索紅軍

(渭南師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院,陜西渭南 714099)

以移動(dòng)通信頻率資源的分配為背景,提出一個(gè)最優(yōu)數(shù)字分配方案.該方案將一個(gè)待分配的大區(qū)域分解成多個(gè)小區(qū)域,以貪心法先簡(jiǎn)單分配好一個(gè)小區(qū)域,將這個(gè)小區(qū)域的左右邊界及上下邊界分別以影響最小的不同數(shù)字進(jìn)行分配,然后再依據(jù)分配好的小區(qū)域,通過(guò)復(fù)制、轉(zhuǎn)換擴(kuò)展到整個(gè)區(qū)域,最后再對(duì)整個(gè)區(qū)域進(jìn)行優(yōu)化.該方案和目前現(xiàn)有的方案比較,最大的優(yōu)勢(shì)是分配過(guò)程非?？?適合對(duì)分配結(jié)果需要經(jīng)常動(dòng)態(tài)變化的情況下應(yīng)用,可以為緊缺資源分配等相關(guān)方面的應(yīng)用提供理論借鑒.

最優(yōu);分配;策略;研究

在移動(dòng)通信中,相關(guān)部門會(huì)為通信運(yùn)營(yíng)商分配一定的頻率[1].為了保證在同一個(gè)區(qū)域內(nèi)以及與相鄰區(qū)域內(nèi)各通信用戶之間不能互相影響,必須使得各用戶的通信頻率有一定的間隔,因此和其他資源一樣,通信頻率也是一個(gè)有限的資源.通信運(yùn)營(yíng)商為了充分利用通信頻率資源,保證各通信用戶互不干擾,運(yùn)營(yíng)商必須采用合理的分配方案[2]來(lái)分配頻率資源.一個(gè)區(qū)域內(nèi)通信用戶的數(shù)量各不相同,還會(huì)動(dòng)態(tài)地變化,在有限的頻率資源下,各通信運(yùn)營(yíng)商建立基站時(shí)需要充分考慮本基站內(nèi)的頻率以及與周圍各基站頻率的關(guān)系,以避免通信過(guò)程中的相互干擾[3]問(wèn)題.這就涉及到怎樣合理地分配各區(qū)域內(nèi)的通信頻率,以保證各用戶之間通信時(shí)互不干擾.鑒于此,我們分析研究最優(yōu)數(shù)字分配策略.

1 問(wèn)題提出

源于第一屆“中國(guó)軟件杯”大學(xué)生軟件設(shè)計(jì)大賽題目,按照下面的要求研究分析最優(yōu)數(shù)字分配策略: 有2 500個(gè)數(shù)據(jù)存儲(chǔ)單元,形成一個(gè)50×50的正方形矩陣,每個(gè)數(shù)據(jù)存儲(chǔ)單元允許存儲(chǔ)2～5個(gè)整數(shù),整數(shù)范圍為1～30,每個(gè)整數(shù)使用次數(shù)不限.限制條件為,每個(gè)存儲(chǔ)單元內(nèi)的整數(shù)不能相同且不能相鄰.如有相同單元格中所放整數(shù)相同或者相鄰,則累加違約分100分或50分;如有相鄰單元格所放整數(shù)相同或者相鄰,則累加違約分20分或10分;如有和相鄰單元格的相鄰單元格所放整數(shù)相同,則累加違約分1分.最終根據(jù)違約分的大小來(lái)評(píng)定分配的優(yōu)劣,違約分越低越好.

2 最優(yōu)數(shù)字分配

2.1 分配原理

分配的原理是首先利用貪心算法[4],根據(jù)題目的要求,填寫一個(gè)4×4的表格,且每個(gè)單元格中存放4個(gè)整數(shù),如表1所示.其次將該區(qū)域向右、向下復(fù)制,直到填充完全部50×50的區(qū)域,其中最右邊和最下邊多余部分舍去,如表2所示.再次,根據(jù)每個(gè)單元格填充數(shù)字個(gè)數(shù)的要求,將多余的數(shù)刪除,將不足的數(shù)補(bǔ)充,其中刪除時(shí)刪掉影響違約分最大的數(shù),補(bǔ)充時(shí)補(bǔ)充影響違約分最小的數(shù),刪除完成后及補(bǔ)充完成后各利用貪心算法進(jìn)行優(yōu)化.最后,對(duì)整個(gè)表格進(jìn)行一次優(yōu)化,檢查個(gè)別影響違約分的數(shù)進(jìn)行修改完善.

由于每個(gè)單元格填充數(shù)字個(gè)數(shù)為2～5個(gè),填充的數(shù)據(jù)為1～30,經(jīng)過(guò)分析,填充4×4的表格違約分最低,并且能夠保證這個(gè)區(qū)域左右對(duì)應(yīng)邊界及上下對(duì)應(yīng)邊界處分配的數(shù)字相互間違約分最小,以確保下一步復(fù)制小區(qū)域時(shí)兩個(gè)區(qū)域相鄰部分違約分最小.若填充3×3的表格,由于30個(gè)待填充數(shù)應(yīng)用少,后邊復(fù)制表格時(shí)會(huì)導(dǎo)致違約分增加.若填充5×5的表格,由于30個(gè)待填充數(shù)不夠用,需要重復(fù)使用,進(jìn)而也將導(dǎo)致違約分增加.

表1 填充4×4的區(qū)域

表2 填充完的50×50區(qū)域

2.2 具體實(shí)現(xiàn)方法

根據(jù)前邊的原理介紹,完成該最優(yōu)數(shù)字分配需要四部分:(1)填充4×4的表格;(2)復(fù)制該4×4表格使其充滿整個(gè)50×50區(qū)域;(3)刪除多余的數(shù)或增加不足的數(shù);(4)優(yōu)化.其中第(1)和第(3)部分最關(guān)鍵.

2.2.1 填充算法

在填充4×4的表格時(shí),可以按列填充,也可以按行填充,這里以按列填充說(shuō)明.在填充時(shí),最前邊的單元格可以通過(guò)1、3、5、7、9的序列分別填充(用公差為2的等差數(shù)列填充沒(méi)有違約分且用數(shù)最少),當(dāng)30個(gè)數(shù)不夠用時(shí),將會(huì)出現(xiàn)違約分.此時(shí)遍歷30個(gè)數(shù),找出違約分最小的數(shù)填充,直到該4×4的區(qū)域填充完成.最后再將該區(qū)域復(fù)制,使其填充完整個(gè)50×50的區(qū)域.

2.2.2 減數(shù)與加數(shù)算法

當(dāng)整個(gè)50×50的區(qū)域填充完成后,需要根據(jù)題目要求調(diào)整每個(gè)單元格中的數(shù)字個(gè)數(shù)(軟件設(shè)計(jì)大賽時(shí)大賽組委會(huì)通過(guò)50×50單元格區(qū)域的Excel文件提供).由于每個(gè)單元格填充的數(shù)字個(gè)數(shù)為2～5個(gè),前邊按照4個(gè)數(shù)進(jìn)行填充,因此對(duì)于需要填充少于4個(gè)數(shù)的單元格要?jiǎng)h除掉一些數(shù)字,對(duì)于需要填充5個(gè)數(shù)的單元格需要再加入1個(gè)數(shù).假設(shè)單元格A要存放的數(shù)小于4個(gè),則分別計(jì)算該單元格中所有數(shù)字的違約分,將違約分大的數(shù)刪除,重復(fù)該過(guò)程直到該單元格中數(shù)字個(gè)數(shù)符合要求.假設(shè)單元格A中應(yīng)該填充5個(gè)數(shù),則遍歷1～30這30個(gè)整數(shù),找出違約分最小的數(shù)進(jìn)行填充.

2.2.3 優(yōu)化算法

按照題目要求的數(shù)字個(gè)數(shù)填充完整個(gè)50×50區(qū)域后,需要再進(jìn)一步對(duì)整個(gè)區(qū)域進(jìn)行優(yōu)化,以降低違約分.假設(shè)按列優(yōu)化的循環(huán)已經(jīng)到了單元格A的第一個(gè)數(shù)的位置,首先將該單元格每個(gè)數(shù)字所產(chǎn)生的違約分從小到大排序,然后將周圍單元格的所有數(shù)依次放在A單元格的第一個(gè)數(shù)的位置且算出每個(gè)數(shù)所產(chǎn)生的違約分,將該違約分和所檢測(cè)的單元格中數(shù)字產(chǎn)生的違約分比較,用產(chǎn)生違約分最小的數(shù)替換待檢測(cè)的數(shù).這樣循環(huán)直到將所有數(shù)字處理完畢.

3 仿真實(shí)驗(yàn)及結(jié)果

對(duì)于前邊介紹的先分配小區(qū)域再擴(kuò)展到大區(qū)域、最后再優(yōu)化的最優(yōu)數(shù)字分配方法,我們進(jìn)行了仿真實(shí)驗(yàn)(測(cè)試所用數(shù)據(jù)為從賽題官網(wǎng)下載的“隨機(jī)矩陣格式”的Excel表).

應(yīng)用VC++6.0編寫了數(shù)字分配程序及違約分統(tǒng)計(jì)、運(yùn)行時(shí)間統(tǒng)計(jì)等測(cè)試程序.在不同操作系統(tǒng)及硬件環(huán)境下的具體測(cè)試結(jié)果如表3所示.另外,我們有幸進(jìn)入了第一屆軟件設(shè)計(jì)大賽決賽,在決賽前,我們?cè)俅蝺?yōu)化了算法及相應(yīng)程序,在決賽過(guò)程中,針對(duì)大賽組委會(huì)提供的參賽數(shù)據(jù),我們參加決賽時(shí)運(yùn)行程序,違約分為41 875,運(yùn)行時(shí)間為21秒多.違約分最低的小組違約分為38 000,應(yīng)用的算法為模擬退火及遺傳算法[5],程序運(yùn)行時(shí)間為35分鐘之多(決賽中違約分最高的達(dá)70 000之多,運(yùn)行時(shí)間大約是25分鐘).其余小組程序運(yùn)行時(shí)間也多在30分鐘左右,運(yùn)行時(shí)間較快的也超過(guò)了20分鐘.最終,我們提出的最優(yōu)數(shù)字分配算法在只考慮分配結(jié)果的情況下盡管不是最優(yōu)的,但離最優(yōu)分配的結(jié)果較近.在綜合考慮分配時(shí)間的情況下,我們提出的算法具有較大的優(yōu)勢(shì),就是軟件運(yùn)行時(shí)間特別快,當(dāng)在需要綜合考慮分配結(jié)果和分配時(shí)間的情況下,該分配方案是一個(gè)較好的可選方案.

表3 數(shù)字分配測(cè)試結(jié)果

4 結(jié)語(yǔ)

2012年8月下旬,在南京進(jìn)行了第一屆“中國(guó)軟件杯”大學(xué)生軟件設(shè)計(jì)大賽,經(jīng)過(guò)賽前幾個(gè)月的分析研究及軟件設(shè)計(jì),我們提出了通過(guò)先分配小區(qū)域,再應(yīng)用小區(qū)域擴(kuò)展到大區(qū)域并進(jìn)行優(yōu)化的最優(yōu)數(shù)字分配方案.該分配方案單從分配結(jié)果上看,優(yōu)勢(shì)不明顯,但分配過(guò)程非常快,在一些實(shí)時(shí)處理[6]等對(duì)分配過(guò)程的時(shí)間有特殊要求,或者需要經(jīng)常變動(dòng)分配結(jié)果的情況下,我們提出的分配方案有很大的優(yōu)勢(shì),可以為一些實(shí)際問(wèn)題的解決提供理論依據(jù).

[1]徐曉燕,孟德香,梁童,等.全球移動(dòng)通信頻率分配情況分析[J].電信工程技術(shù)與標(biāo)準(zhǔn)化,2011,(12):16-19.

[2]陳忻磊,胡昱宙,張沛超,等.數(shù)字化變電站系統(tǒng)最優(yōu)可靠性分配方法[J].電力系統(tǒng)保護(hù)與控制,2012,40(8):25-29.

[3]馬偉.認(rèn)知無(wú)線電頻譜檢測(cè)技術(shù)研究[D].北京:北京郵電大學(xué)博士學(xué)位論文,2010.

[4]賀毅朝,劉坤起,張翠軍,等.求解背包問(wèn)題的貪心遺傳算法及其應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì),2007,28(11):2655-2658.

[5]鮑軍鵬,張選平.人工智能導(dǎo)論[M].北京:機(jī)械工業(yè)出版社,2010.202-218.

[6]馬超.數(shù)字信號(hào)處理、實(shí)時(shí)信號(hào)處理[D].上海:上海交通大學(xué)碩士學(xué)位論文,2009.

【責(zé)任編輯 曹 靜】

The Analysis and Study of the Optimal Digital Allocation Strategy

SUO Hong-jun
(School of Mathematic and Information Science,Weinan Normal University,Weinan 714099,China)

Based on the distribution of mobile communication frequency resource for the background,this paper puts forward an optimal scheme of digital distribution.The program will be allocated a large area and then divided into a plurality of small area,with the greedy method briefly assigned to a small region around the border.The right and left boundary of the small region and its upper and lower boundary will be allocated respectively which affects different digital minimum distribution.Then the small regional distributions by the replication and transformation are extended to the entire region,and finally the whole area is optimized.The scheme and the existing scheme are compared,and it proves that the biggest advantage is that the allocation process is very fast,the allocated results for application dynamically is needed to change,which can provide a theoretical reference for application as the shortage of resource allocation and other related aspects.

optimal;allocation;strategy;research

TP301.6

A

1009-5128(2014)07-0028-03

2014-03-11

索紅軍(1971—),男,陜西白水人,渭南師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院副教授,工學(xué)碩士,主要從事人工智能及計(jì)算機(jī)應(yīng)用研究.