最优数字分配策略

aimisiyou

        最优数字分配策略
比赛题目条件：
假设有2500个数据存储单元，形成为50*50的正方形矩阵。每个数据存储单元允许存储2~5个整数，整数范围为1~30，每个整数使用次数不限。

50*50数据存储单元如下表形式：
1-1 1-2 1-3  1-4…2-1 2-2  2-3  2-4…3-1  3-2  3-3  3-4…4-1  4-2  4-3  4-4………………其中1-1、1-2等表示存储单元在矩阵中的行列位置，也可以将其作为存储单元的名称。

比赛题目要求：
将1~30的整数按各存储单元的整数个数要求，分配到各数据存储单元中。未按要求分配整数，比赛无成绩，直接出局；

每个存储单元内的整数不能相同且不能相邻。如：1和2、2和2、2和3不能出现在同一个存储单元中。如果违反规则，按下述罚则处理：针对每个存储单元都统计一遍，出现一次相同，结果累加100违约分；出现一次相邻，结果累加50违约分；

每个存储单元与相邻的存储单元内的整数不能相同且不能相邻。如：第2-2存储单元内的整数与第1-1、1-2、1-3、2-1、2-3、3-1、3-2、3-3存储单元内的整数不能相同且不能相邻。如果违反规则，按下述罚则处理：针对每个存储单元都统计一遍，出现一次相同，结果累加20违约分；出现一次相邻，结果累加10违约分；

每个存储单元与相邻存储单元的相邻存储单元内的整数不能相同。如：第2-2存储单元内的整数与第1-4、2-4、3-4、4-1、4-2、4-3、4-4存储单元内的整数不能相同。如果违反规则，按下述罚则处理：针对每个存储单元都统计一遍，出现一次相同，结果累加1违约分；

各比赛小组自己设计分配算法，在规定时间内（比如1小时）运算分配结果，哪个小组最后的违约分值最低，哪个小组获胜。


违约分计算举例：
行\列列1列2…行11,3,57,9…行211,12,131,4……………上表所示为部分存储单元内整数分配结果，违约值计算方法如下：
当前存储单元标识冲突存储单元标识当前存储单元违规整数冲突存储单元违规整数违约分数1-12-211201-12-234101-12-254102-21-111202-21-143102-21-145102-12-11112502-12-1121350为了方便计算，同存储单元内（如2-1）的冲突整数按照规则计算一次违约分，相邻存储单元内（如1-1和2-2）的冲突整数由于参照主体改变会重复计算违约分。最后的总分为所有违约分的总和。

aimisiyou

首先，我们得弄清楚各存储单元之间的逻辑关系。如邻居关系、邻居的邻居关系。

aimisiyou

在移动通信过程中，移动用户的通信内容通过移动台（手机等移动通信设备）转换成频率信号后和通信基站（专门负责收发无线信号的物理通信设备）之间进行交互传输。
   国家相关部门为各电信运营商划定专门的频率区间，此频率区间按照相关电信标准可平均划分若干等份小的频率区间作为信号传输的最小单位，每个最小单位最多可同时为8个移动用户服务。各电信运营商频率区间不一样，频率带宽也不一样，即可划分的最小单位个数也不一样。
   因此，各电信运营商需要根据用户密度在有限的频率资源条件下，建立多个通信基站，每个通信基站分配1个或多个服务频率，以服务通信区域内的用户群。同时，如果基站内或邻近的基站使用相同或相近的频率收发信号，这些基站由于距离位置关系，会相互产生不同程度的电磁干扰，导致基站服务的移动用户出现不同程度的通信障碍。
因此，各电信运营商在建立基站并分配服务频率的过程中会充分考虑周围基站的服务频率，使各基站的服务频率要尽量不与周围基站的服务频率相近，以减少通话过程中的干扰问题。在没有更好的频率资源可用的情况下，运营商会考虑重新分配所有基站的服务频率，达到降低干扰的目的。

根据业务背景，可按如下所述理解题目条件：
50*50的存储单元矩阵为某电信运营商服务某区域的50*50个通信基站
1~30的整数为某电信运营商的可用频率资源
每个存储单元内的整数个数为基站内服务频率个数
比赛要求2~5可理解为同基站内或相邻基站内尽量不能出现频率相近的情况，如果出现这种情况，不同距离位置的基站，会产生不同程度的通话干扰。

aimisiyou

先选取重复数最多的整数，看能将其分配到哪些其存贮单元里而不出现增加违约分的情况。
以50*50为例，[（50-1）/3+1]*[（50-1）/3+1]=289，即重复数最多的整数个数不超过289时，按黄色存储单元分配。若超过289，则要考虑如何将违约分增加的最少。

aimisiyou

来个实例。200个随机整数（1~9之间整数，15个1,24个2,27个3,20个4,19个5,27个6,17个7,29个8,22个9）存入10*10存贮单元内，每个存贮单元存储2个数据，如何存贮这200个数据使得违约分增加的最少？

aimisiyou

贪心算法不适用，会导致邻居存储单元相隔1的情况很多。实在不行，就用万能的遗传算法（虽然有些类似大海捞针）。

tzfcn

规则没有看懂，不如做几个示例。

aimisiyou

不知是否与最近看的配对控制数有些联系？

aimisiyou

tzfcn 发表于 2020-7-19 18:43
规则没有看懂，不如做几个示例。

就三个方面核对：1、每个存储单元内部；2、每个存储单元邻居；3、每个存储单元邻居的邻居。

aisong220