基于无向加权图上信号采样重构的推荐系统预测

为有效地捕获数据的潜在结构并且降低计算量,提出一种基于无向加权图上信号采样重构的推荐系统预测算法。为了利用未标记条目所携带的信息,将用户或项目及其关系建模为一个加权无向图。为了实现采样信号重构,在再生核希尔伯特空间中,将该问题近似地建模为一个二次无条件优化问题。为了降低计算复杂度,引入一种近似求解策略。在两个开放的公共数据库上的实验结果表明,该模型显著提高了预测精度,并且大大降低了计算复杂度。

一种多天线地面站的设备级资源调度算法

针对多天线地面站接收设备共享使用的需求,设计了一种设备级资源调度算法,以充分利用站内设备资源,提高地面站任务能力。首先,分析了多天线地面站资源调度需考虑的各类约束,并建立了各类调度资源和关系模型。然后,将所有卫星接收任务的时间分布抽象为无向图,通过定义边的权重计算任务冲突度。最后,提出了基于优先级和匹配性的概率选择算法,以迭代方式实现调度方案的寻优。仿真结果显示,所提算法的平均调度成功率较优先级算法和遗传算法分别提高了11.9%和6.9%,有效提高了接收设备使用效率。

基于课程学习权重集成的贝叶斯结构学习算法研究

从大量复杂的数据中学习贝叶斯网络(Bayesian network,BN)一直是一个难点问题,本文借鉴课程学习的思想,引入了一种适合于BN中节点之间互相影响程度的测量,然后划分课程阶段,分阶段构造无向图骨架,并利用优化函数对骨架进行优化;通过集成策略,将各个集成学习结果所得到的课程权重进行集合,并通过边过滤来减少错误边的出现;最后,通过爬山搜索构建BN结构。实验结果表明,在4个标准数据集上,本文所提方法具有较高的精确度和稳定性。与多种传统贝叶斯结构学习(Bayesian network structure learning,BNSL)方法相比,本文所提方法性能平均提高了37.18%。本文分析结果可为BNSL的增量学习过程进一步提供参考。

一种VLSI设计到无向赋权图的转换系统

基于VLSI剖分问题的需要,设计并实现了VLSI设计到无向赋权图的转换系统(VLSI/Graph Converter,VGC).介绍了电路构造图和图文件存储格式,给出了VGC的处理流程图,提出了针对VLSI线网的无向赋权图转换算法.该算法解决的关键问题是,遍历树状结构的VLSI线网,将其转换为无向赋权图并存储为指定的图文件格式.VGC系统在Windows平台下用C++实现.实验及分析表明,该系统能正确地将Verilog语言描述的门级CPU转换为无向赋权图,避免了直接在VLSI线网上进行剖分,提高了VLSI剖分的效率.

基于谱方法的无向赋权图剖分算法

在多水平方法初始剖分阶段提出了一种基于谱方法的无向赋权图剖分算法SPWUG,给出了基于Lanc-zos迭代计算Laplacian矩阵次小特征值及特征向量的实现细节。SPWUG算法借助Laplacian矩阵次小特征值对应的特征向量,刻画了节点间相对距离,将基于非赋权无向图的Laplacian谱理论在图的剖分应用方面扩展到无向赋权图上,实现了对最小图的初始剖分。基于ISPD98电路测试基准的实验表明,SPWUG算法取得了一定性能的改进。实验分析反映了在多水平方法中,最小图上的全局近似最优剖分可能是初始图的局部最优剖分,需要加强优化阶段的迁移优化算法逃离局部最优的能力。

基于无向加权图的协同生产网络脆弱性分析方法

为了分析企业故障对协同生产网络整体功能的影响,提出了基于脆弱性分析的研究方法;根据模糊集与复杂网络理论,将协同关系影响概率作为描述企业间业务联系的指标,构建了协同生产网络无向加权图模型;以最大可能路径作为协同生产网络效能函数,提出了兼顾企业功能和网络拓扑的脆弱性分析方法。实例分析结果表明,该方法可有效找到协同生产网络中存在的脆弱点。

基于无向图构建策略的主题句抽取

基于文档句构建无向图,将主题句的抽取问题转换为无向图中节点的权重计算问题。首先利用滑窗方法抽取主题词,构建空间向量并生成无向图,然后基于向量空间模型计算边权重,最后利用文档句相似度矩阵的权重模型对文档句权重进行建模与计算,依据压缩比得到文档的主题句。实验表明,该方法在不同的压缩比下生成的摘要质量高,主题句抽取结果接近于人工摘要,召回率和准确率综合指数较高。

网络中最短距离的递归算法

提出了在搜索过程中采用标记最短距离,调用递归函数用回溯搜索法求解网络最短距离的算法。该算法可以方便地求解复杂网络或复杂迷宫的通道与最短距离问题,在求解结果中给出从起点到网络通道上任意点的路径标识和最短距离值等信息,在无向加权图的最短路径求解中,显示出比Dijkstra方法小的时间复杂度。该算法克服了传统回溯法求解复杂迷宫时被时间复杂度和空间复杂度困扰的难题,显示出良好的应用前景。

一种VLSI剖分系统的研究与实现

基于多水平方法,设计并实现了一种VLSI剖分系统(Multilevel-based VLSI Partitioner,MVP)。介绍了MVP系统的结构框图、处理流程及模块功能。MVP系统的多水平剖分程序引入图核到粗化阶段,谱图论到初始剖分阶段,群智能到投影优化阶段,得到了无向赋权图更优的剖分。MVP系统特点体现在VLSI线网到无向赋权图的转换,避免了剖分算法直接在VLSI线网上进行剖分,提高了VLSI剖分的效率。实验及分析表明MVP系统的多水平剖分程序能找到更优的图剖分,以及MVP系统找到比现有技术更优的VLSI剖分,提高了VLSI剖分的性能。

一种基于谱分割的短文本聚类算法

短文本具有稀疏高维的特点,现有聚类算法在大规模短文本上的聚类精度较低且效率低下。针对该问题,提出一种以谱聚类理论作支撑,基于谱分割准则RMcut的新聚类算法。依据谱聚类理论,将短文本集合构建成一张带权无向图,并计算得到文档-文档的相似度矩阵,为聚类算法提供信息。不断迭代地用2-way方式划分该图,划分过程中使用RMcut值作为划分是否终止的条件,利用Prim算法将原图中的顶点加入到聚族中,以得到质量较高的聚类结果。实验结果表明,该算法具有较高的时间性能,与K-means算法、词共现聚类算法及基于免疫的聚类算法相比,聚类结果更准确。

求无向赋权图最小生成树的两种算法的探讨

对求无向赋权图最小生成树两种算法分别是PRIM算法和KRUSKAL算法。本文通过用堆改进了PRIM方法中选择最小边的方法。结合C语言的特点,实现了集合的划分和合并。对KRUSKAL方法进行了探讨,弥补了一些数据结构教科书上未给出C语言实现的KRUSKAL算法的不足。

赋权混合图的拓扑转化与同构判别

提出一种赋权混合图的拓扑转化方法,将混合图的顶点度、权值、无向边和有向边用不同素数进行区分,用素数构建一个描述混合图边方向的非对称矩阵S,将用素数描述的权值矩阵的元素与S矩阵元素进行相乘,将该乘积与素数重新映射,该映射下的素数反映了赋权和混合图边方向的综合信息,从而将赋权混合图转化为赋权无向图,最后对邻接矩阵动态修改法进行推广以适用于赋权混合图的同构判别,判别实例表明该方法的有效性和可靠性。

基于带权无向连接图的子装配体识别方法研究

子装配体识别是解决大规模装配序列规划问题的有效方法之一。为了高效、自动地识别子装配体,根据零件联接类型,建立了装配体的带权无向连接图模型。通过边权值的设定,使得装配体的带权无向连接图能够提供Ⅰ型和Ⅱ型子装配体识别所需的联接信息。将带权无向连接图与装配体的干涉矩阵和支撑矩阵相结合,设计并实现了Ⅰ型和Ⅱ型子装配体的识别算法。与有向连接图模型中子装配体识别算法相比,能够有效消除识别过程中对两种类型子装配体的冗余判断。实验结果表明,识别算法能够有效的进行两种类型子装配体的识别。

带权无向图中反馈顶点集的固定参数枚举算法

反馈顶点集(FVS)问题是一个经典的NP-完全问题,在很多领域有重要的应用.人们对该问题进行了大量的研究,但目前还没有有效的算法枚举带权无向图的反馈顶点集.文中通过对带权无向图中反馈顶点集问题的结构的深入分析,给出了一个有效的基于分支搜索技术的固定参数枚举算法.算法将反馈顶点集问题转化为反馈边集问题,通过枚举z个权值最大的森林来枚举z个权值最小的含k条边的反馈边集,从而得到z个权值最小的含k个顶点的反馈顶点集,算法时间复杂度为O(5kn2(logn+k)+3kz(n2logn+z)).

图形轮廓分层路由提取的MST生长算法

在以可达路径决策为核心的图形轮廓提取中,为有效地解决路由决策困难及路径特征值精度等问题,提出了图形轮廓分层路由提取的MST生长算法.该算法将图形路由拓扑结构划分为域内路由和域间路由.域内路由对非支配点关联路径进行重组,建立以支配点为节点的图形有权无向图;域间路由以无向图最小生成树MST为基础,利用树节点间唯一可达特性构造MST生长算法.最后综合这2个层次实现完整的图形轮廓提取.通过算例及应用证明了文中算法的可行性和有效性.

基于中医方剂数据库的Top-Rank-k频繁模式挖掘算法

为降低中医(TCM)方剂频繁模式挖掘过程中对经验参数的依赖,提高挖掘结果的准确性,针对中医方剂的数据特点,提出一种基于带权无向图的Top-Rank-k频繁模式挖掘算法。该算法可以直接挖掘出频繁k-itemset(k≥3)而无需产生1-itemset和2-itemset,并随之快速回溯到核心药物组合的频繁项集所对应的方剂信息;此外,采用一种动态位向量(DBV)的压缩机制对无向图中边的权重进行压缩存储,以有效地提高算法的空间存储效率。分别对中医方剂数据集、真实数据集(Chess、Pumsb和Retail)和合成数据集(T10I4D100K和Test2K50KD1)进行测试和比较,结果表明该算法与i NTK和BTK相比具有更高的时间和空间效率,而且也可以应用于其他类型的数据集。

多节点有向无环图优化算法

针对有向无环图结构进行研究,在分析信息版本存储特点和继承关系的基础上,以信息版本间差异为计算指标,设计了一种完整版本和增量版本的分布优化策略,来提高多节点信息整体存储和查询读取性能。分析和实例验证表明,该优化模式提高了多节点信息存储和查询读取效率。

基于VB的最小生成树KRUSKAL算法的实现

对求解加权连通无向图最小生成树的KRUSKAL算法进行了探讨,并用VB实现,同时以读取文件的方法输入图,弥补了利用面向过程的程序设计语言在求解最小生成树时输入数据的复杂性。通过可视化的形式显示无向图和最小生成树,使结果直观且容易理解。

多自由度行星轮系机构拓扑表示与同构判别

在多自由度行星轮系的众多设计方案中需要排除同构方案。针对多自由度行星轮系的拓扑图表示的复杂性,提出将行星轮系的基本构件用一组参数表示,将基本构件的表示参数作为拓扑图的顶点赋权,而基本构件之间的连接关系用另外一组参数表示,连接关系中的参数作为拓扑图边的赋权,从而将多自由度行星轮系转化为可以完整表达多自由度行星轮系的信息的赋权无向图。最后用邻接矩阵动态修改法对多自由度行星轮系的方案进行同构判别,同构判别实例表明多自由度行星轮系机构拓扑表示方法在排除同构方案中的有效性。

无向赋权图剖分优化问题的研究进展

无向赋权图剖分优化问题作为图论中的一个典型组合优化问题,在大规模集成电路设计、并行计算、数据挖掘、任务调度、知识发现、图像分割等领域有着广泛的应用。本文给出了无向图剖分优化问题的相关概念;从寻优策略的角度,将无向图剖分优化问题的求解算法分为构造性算法和迭代改进算法;分析了求解无向图剖分优化问题的迁移方法、几何方法、组合方法、谱方法、元胞自动机方法;重点讨论了多水平方法的粗化阶段、初始剖分阶段和优化阶段相应的匹配算法、初始剖分算法和迁移优化算法;介绍了无向图剖分优化问题的典型应用领域并指出了该问题今后的研究方向。