软件定义光网络中基于最小点覆盖的控制平面跨层生存性设计

为降低软件定义光网络对单控制器的依赖,并避免多控制器冲突,有效提升控制平面的生存性,该文提出基于最小点覆盖的控制平面生存性设计策略。该策略结合集中控制约束条件,以最小点覆盖理论为基础,建立可靠的分级管控模型,设定控制器的管控优先级:全局控制器具有最高管控优先级,对全网进行集中管控;本地控制器次之,只对本地业务进行集中管控;权威交换机的管控优先级最低,用于完成局部波长粒度的光层快速管控。在此基础上,基于跨层信息模型为控制信道路由和资源分配进行生存性冗余设计。仿真表明,该策略能够满足网络对控制时延的要求,使控制平面的故障概率降低了30%,有效提升了网络在恶劣环境下的生存性。

基于最小点覆盖和反馈点集的社交网络影响最大化算法

社交网络中的影响最大化问题是指在特定的传播模型下,如何寻找k个最具影响力的节点使得在该模型下社交网络中被影响的节点最多,信息传播的范围最广。该问题是一个优化问题,并且已经被证明是NP-难的。考虑到图的最小点覆盖和反馈点集中的顶点对图的连通性影响较大,该文提出一种基于最小点覆盖和反馈点集的社交网络影响最大化算法(Minimum Vertex Covering and Feedback Vertex Set,MVCFVS),并给出了具体的仿真实验和分析。实验结果表明,与最新的算法比较,该算法得到的节点集在多种模型下都具有优异的传播效果,例如在独立级联模型和加权级联模型中超过当前最好的算法,并且还具有更快的收敛速度。

基于最短路算法的最小点覆盖问题

基于经典的最短路算法——Dijkstra算法,以最短路路长的最大值为标准,按照一定原则选择点覆盖的顶点,得出了最小点覆盖问题的一个近似算法,其时间复杂性为O(n3).最后给出了一个近似比为1.067的算例,阐释了算法的实现过程及有效性.

一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法

二分图受约束最小点覆盖问题作为一个NP-完全问题,无法在多项式时间内得到最优解,除非P=NP。基于此,本文提出了一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法,具体为:当二分图受约束最小点覆盖问题实例中存在满足约束条件的最小点覆盖(ku,kl)时,对任意给定的近似率δ=1+ε>1,一定可以找到一个受约束近似点覆盖(ku,kl),对应的近似率为max{ku/ku,kl/kl}≤1+ε,整个近似算法的运行时间复杂度为O(22/ε)。显然,它是二分图受约束最小点覆盖问题的一个多项式时间近似方案(polynomial time approximation scheme,PTAS算法)。

广义Petersen图的最小点覆盖集

点覆盖问题是一个著名的NP完全问题.本文对广义Petersen图P(n,2)的精确最小点覆盖数进行研究,讨论并证明了广义Petersen图P(n,2)的最小点覆盖数,给出了最小点覆盖集的构造方法.

基于最小点覆盖的共享单车投放点选取方法

针对城市共享单车投放点和电子围栏等设置不合理的问题,考虑共享单车对城市交通环境影响和共享单车运营企业的成本,研究了一种基于最小点覆盖的共享单车投放点选取算法。将整个城市交通网络抽象为图,将共享单车投放点抽象为图的节点。对于图的不同点覆盖方案,引入路段权值函数和调度成本矩阵,以最少投放点和最小调度成本2个指标对不同点覆盖方案进行排序,从中选优得到共享单车投放点选取方案。算法既考虑了共享单车投放点在城市交通网络的覆盖情况,又考虑了共享单车企业车辆投放和车辆调度的成本问题,克服了现有共享单车投放点选取方法的单一性和盲目性的问题。

基于最大最小蚁群算法求解最小点覆盖问题

最小点覆盖问题是组合优化中经典的NP完全问题.最大最小蚁群算法通过对信息素浓度的限定使其不会在好的顶点上变得更强,也不会使过弱的点被忽略从而避免了局部最优现象的出现.针对最小点覆盖问题使用最大最小蚁群算法进行求解,避免了蚁群算法求解最小点覆盖问题时出现的早期停滞现象,通过实验表明算法对最小点覆盖问题的可行性.

最小权点覆盖下的智能电表通信故障区域预警方法

电表通信故障预警可以保证智能电表的通信安全,有利于实现对智能电能表的全过程质量管控。但是,智能电表的工作轨迹具有随机性,跟踪难度较大,其故障变量信息的提取难度较大。为此,提出了基于最小权点覆盖的智能电表通信故障区域预警方法。利用智能电表运行状态的观测向量作为故障检测的关键变量,计算出运行状态观测向量的平均轨迹。根据智能电表通信故障数据变量在不同时刻的运行轨迹,提取出智能电表通信故障的关键变量信息,完成智能电表通信故障的检测。在最小权点覆盖下,采集智能电表通信故障数据。利用Fisher准则,计算出智能电表通信故障属性的重要程度,通过设计智能电表通信故障区域预警算法,实现智能电表通信故障区域的预警。实验结果表明,研究方法可以成功预警智能电表通信故障,通过较高的预警准确率确保了智能电表的稳定运行。

最小权点覆盖的扫描测试向量生成算法

现有的边界扫描测试算法,多数主要通过建立无限制短路故障模型来生成测试向量,但以此方法构造的测试矩阵紧凑性指标较差。提出了一种利用可能性理论下有限制故障模型的最小权点覆盖集进行测试向量生成。首先,通过分析ProtelDXP提供的电路板网表信息建立网络近邻关系图,即赋权图。然后结合Dijkstra算法求取初始点到其余各点的最短路径,并根据最短路径的最大值依照相关准则确定点覆盖集,并给出了具体的算法步骤;最后根据所得出的最小权点覆盖集生成测试矩阵。最后以某大型机载电路板为研究样例,进行理论分析及实验验证表明,上述方法与传统方法相比,获得的测试矩阵具有较好的紧凑性,算法性能有了大幅度提升。

基于改进贪婪算法的测量节点选择优化方法

未来应用场景对名字解析系统有着确定性时延保障的需求,如何有效选择测量节点,为确定时延名字解析提供支撑是本文着力解决的问题。本文将网络测量节点部署问题映射成为最小点覆盖问题,并基于传统的贪婪算法提出一种面向网络测量节点选取的改进贪婪算法,从优化贪婪算法迭代周期和针对实际场景特点改进排序算法2个方面进行优化。实验结果表明,基于改进贪婪算法的求解方式比传统贪婪算法的求解方式,平均耗时减少了90%以上。

圆通速递在保定地区的网点布局优化分析

针对圆通速递在河北保定地区的网点布局,本文以各个客户群的需求和各个服务网点的服务能力为约束,建立最小点覆盖模型和以物流成本最小为目标函数的中转站选址模型。为提高搜索速度,采用重心法,进行迭代求解。最后针对保定地区圆通快递网点布局的现状,从网点布局密度、快件派送路线等方面分析其不足,依据本文所建立的最小点覆盖模型和中转站选址模型,优化其布局,降低物流成本,提高物流运转效率。

最小权点覆盖问题的一个近似算法

在点、边赋权的简单图中,关于最小权点覆盖问题,以经典的最短路算法-Dijkstra算法为基础,提出了一个求解该问题的近似算法.首先,在给定的赋权图中任选一点作为初始点,并给出允许集及相关定义.然后,利用经典的最短路算法-Dijkstra算法,求出初始点到允许集中各顶点的最短路径,并按照一定的原则选择近似最小权点覆盖集.最后,通过算例阐释了算法的实现过程的合理性及有效性.

基于禁忌搜索与扰动策略的探针部署算法

在采用改进蚁群算法对智能电网探针部署无向图最小点覆盖集求解过程中,由于对相邻顶点的重复计算,导致计算时间增加,使计算结果陷入局部区域求解。基于此,提出一种基于禁忌搜索与扰动策略的探针部署算法。通过结合快速邻域切换以及建立禁忌表增强局部寻优能力并减少计算时间,结合扰动策略扩展集合求解范围,使所求解最小点覆盖结果达全局最优。实验结果表明,相比改进蚁群算法,该算法计算时间更少,寻优能力更强,寻优范围更广。

退化图中的子图计数问题研究

令G表示n个顶点的图,如果G的每个子图中都包含一个度至多为k的顶点,则称G为k-退化图.令N(G,F)表示G中F子图的个数.主要研究了k-退化图中完全子图和完全二部子图的计数问题,给出了计数的上界以及相应的极图.首先,证明了Ν(G,K_(t))≤(n-k)(k t-1)+(k t).其次,如果s,t≥1,n≥k+1且s+t≤k,我们证明了Ν(G,K_(s,t))≤{(k s)(n-s s)-1/2(k s)(k-s s),t=s,(k s)(n-s t)+(k t)(n-t s)-(k t)(k-t s),t≠s.此外,还研究了在最大匹配和最小点覆盖为给定值的情况下,图G中的最大边数.记v(G),K(G)分别为图G的最大匹配数和最小点覆盖.证明了当v(G)≤k,K(G)=k+r且n≥2k+2r^(2)+r+1时,有e(G)≤(k+r+1 2)+(k-r)(n-k-r-1).