2022MathorcupD题完整思路和论文

已经初步写出论文&＃xff0c;论文地址见文末。
符号说明
F &＃xff1a;圆覆盖后图形区域
r_i &＃xff1a;圆i 的半径&＃xff1b;
dij &＃xff1a;圆i 与圆j 的圆心距&＃xff1b;
Sij &＃xff1a;圆i 与圆j 的重叠面积&＃xff1b;
T &＃xff1a;目标区域内所有节点集合
C &＃xff1a;公共节点集合
O &＃xff1a;圆心节点集合
M &＃xff1a;覆盖区域圆个数
​

自适应K&＃xff0d;中心聚类方法基本思想&＃xff1a;使用圆心数据作为K&＃xff0d;中心聚类的初始中心&＃xff0c;开始聚类&＃xff0c;然后用最小的圆覆盖同类中的节点&＃xff0c;判断是否满足约束条件&＃xff0c;不满足则调整圆&＃xff0c;再将此时的圆心作为下一次聚类的中心&＃xff0c;重新聚类&＃xff0c;重复上面过程&＃xff0c;最终得到满足题目条件的一跳覆盖区划分的结果。
自适应K&＃xff0d;中心聚类方法流程如下&＃xff1a;
①设置迭代次数Num&＃xff0c;使用正六边形一跳覆盖区方案的圆心位置作为聚类的初始中心。采用这种初始位置选择的方法&＃xff0c;使得我们的初始中心在目标区域内的分布较平均&＃xff0c;使得聚类后的同类范围相差不大&＃xff1b;
②K&＃xff0d;中心聚类方法聚成K 类&＃xff1b;
③用最小的圆来完全覆盖K 类中的节点&＃xff0c;此时的覆盖圆集满足约束条件2&＃xff09;&＃xff1b;
④考虑约束条件1&＃xff09;&＃xff0c;当上面的覆盖圆集中某圆的半径时&＃xff0c;我们选择圆内节点与其它圆心的距离最远的点&＃xff0c;将圆心朝着该点移动&＃xff0c;直到可以用半径为r 的圆覆盖它为止。此时该半径为r 的圆肯定不覆盖原来同类中的所有节点&＃xff0c;漏覆盖的点将其加入最接近的一类中。由于我们初始中心的为半径为100 的正六边形一跳覆盖区方案&＃xff0c;所以一定可以用半径小于100 的圆覆盖住露出的节点。从而得到新的覆盖圆集&＃xff1b;
⑤考虑约束条件3&＃xff09;中满足转发任务的条件&＃xff0c;这里我们理解转发任务即为在两圆的公共部分是否存在公共节点&＃xff0c;存在则满足转发任务&＃xff0c;反之则不满足。检查上面得到的覆盖圆集中圆的公共部分中是否存在公共节点&＃xff0c;如果不存在&＃xff0c;则找到离此圆距离最近的外部节点&＃xff0c;扩大圆的半径并移动圆心&＃xff0c;直到覆盖距离最近外部节点。圆心移动和扩大半径示意图见图5。满足此条件的覆盖圆集中的节点为连通的&＃xff0c;也就解决了约束条件4&＃xff09;的问题&＃xff1b;
建立一个记录库&＃xff0c;任意选取一个公共节点记入记录库&＃xff0c;搜索其它公共节点&＃xff0c;如果与记录库中节点连通&＃xff0c;则加入记录库中&＃xff0c;继续搜索直到没有公共节点与记录库中节点连通。如果记录库包含所有存在的公共节点&＃xff0c;说明网络节点连通&＃xff0c;否则不连通。
效果展示&＃xff1a;
​

论文地址&＃xff1a;https://mianbaoduo.com/o/bread/YpmXmpdp