最優數字分配策略分析研究

索紅軍

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

【信息科學與工程研究】

最優數字分配策略分析研究

索紅軍

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

以移動通信頻率資源的分配為背景,提出一個最優數字分配方案.該方案將一個待分配的大區域分解成多個小區域,以貪心法先簡單分配好一個小區域,將這個小區域的左右邊界及上下邊界分別以影響最小的不同數字進行分配,然后再依據分配好的小區域,通過復制、轉換擴展到整個區域,最后再對整個區域進行優化.該方案和目前現有的方案比較,最大的優勢是分配過程非?？?適合對分配結果需要經常動態變化的情況下應用,可以為緊缺資源分配等相關方面的應用提供理論借鑒.

最優;分配;策略;研究

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

1 問題提出

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

2 最優數字分配

2.1 分配原理

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

由于每個單元格填充數字個數為2～5個,填充的數據為1～30,經過分析,填充4×4的表格違約分最低,并且能夠保證這個區域左右對應邊界及上下對應邊界處分配的數字相互間違約分最小,以確保下一步復制小區域時兩個區域相鄰部分違約分最小.若填充3×3的表格,由于30個待填充數應用少,后邊復制表格時會導致違約分增加.若填充5×5的表格,由于30個待填充數不夠用,需要重復使用,進而也將導致違約分增加.

表1 填充4×4的區域

表2 填充完的50×50區域

2.2 具體實現方法

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

2.2.1 填充算法

在填充4×4的表格時,可以按列填充,也可以按行填充,這里以按列填充說明.在填充時,最前邊的單元格可以通過1、3、5、7、9的序列分別填充(用公差為2的等差數列填充沒有違約分且用數最少),當30個數不夠用時,將會出現違約分.此時遍歷30個數,找出違約分最小的數填充,直到該4×4的區域填充完成.最后再將該區域復制,使其填充完整個50×50的區域.

2.2.2 減數與加數算法

當整個50×50的區域填充完成后,需要根據題目要求調整每個單元格中的數字個數(軟件設計大賽時大賽組委會通過50×50單元格區域的Excel文件提供).由于每個單元格填充的數字個數為2～5個,前邊按照4個數進行填充,因此對于需要填充少于4個數的單元格要刪除掉一些數字,對于需要填充5個數的單元格需要再加入1個數.假設單元格A要存放的數小于4個,則分別計算該單元格中所有數字的違約分,將違約分大的數刪除,重復該過程直到該單元格中數字個數符合要求.假設單元格A中應該填充5個數,則遍歷1～30這30個整數,找出違約分最小的數進行填充.

2.2.3 優化算法

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

3 仿真實驗及結果

對于前邊介紹的先分配小區域再擴展到大區域、最后再優化的最優數字分配方法,我們進行了仿真實驗(測試所用數據為從賽題官網下載的“隨機矩陣格式”的Excel表).

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

表3 數字分配測試結果

4 結語

2012年8月下旬,在南京進行了第一屆“中國軟件杯”大學生軟件設計大賽,經過賽前幾個月的分析研究及軟件設計,我們提出了通過先分配小區域,再應用小區域擴展到大區域并進行優化的最優數字分配方案.該分配方案單從分配結果上看,優勢不明顯,但分配過程非?？?在一些實時處理[6]等對分配過程的時間有特殊要求,或者需要經常變動分配結果的情況下,我們提出的分配方案有很大的優勢,可以為一些實際問題的解決提供理論依據.

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

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

[3]馬偉.認知無線電頻譜檢測技術研究[D].北京:北京郵電大學博士學位論文,2010.

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

[5]鮑軍鵬,張選平.人工智能導論[M].北京:機械工業出版社,2010.202-218.

[6]馬超.數字信號處理、實時信號處理[D].上海:上海交通大學碩士學位論文,2009.

【責任編輯 曹 靜】

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—),男,陜西白水人,渭南師范學院數學與信息科學學院副教授,工學碩士,主要從事人工智能及計算機應用研究.