最优数字分配策略分析研究

索红军

(渭南师范学院数学与信息科学学院,陕西渭南 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—),男,陕西白水人,渭南师范学院数学与信息科学学院副教授,工学硕士,主要从事人工智能及计算机应用研究.