一种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算法取得了一定性能的改进。实验分析反映了在多水平方法中,最小图上的全局近似最优剖分可能是初始图的局部最优剖分,需要加强优化阶段的迁移优化算法逃离局部最优的能力。

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

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

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

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

基于DNA计算的无向赋权图哈密顿路径问题

本文给出一种通过DNA序列编码来处理权值的方式,对无向赋权图哈密顿路径问题进行了描述。首先用寡核苷酸片段编码图中的顶点和边,然后将这些寡核苷酸片段放入缓冲溶液中,利用连接酶将它们连接起来,从而产生所有无向边不同的DNA链,最后利用PCR扩增、探针、电泳等生物手段寻找对应于只经过图的顶点一次的无向Hamilton路的DNA链,通过比较以及前面实验条件的控制最终找到最短的Hamilton路径。

基于DPCNN的无向赋权图的最小生成树的求解

利用脉冲耦合神经网络(PCNN,Pulse Coupled Neural Network)的脉冲波并行传播特性,在其时延脉冲耦合神经网络(DPCNN,Delay PCNN)的基础上提出了一种求解无向赋权图最小生成树的新算法.算法针对最小生成树的权值总和最小且连通的性质,结合时延脉冲耦合神经网络脉冲波的并行传播,通过求解无向赋权图的最短路径并对其连通性进行判断,采用迭代的方法,成功地求解了无向赋权图的最小生成树.最后给出了仿真实验,证明了该方法的有效性,与传统算法比较有一定的优势.

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

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

内部节点受限的最小生成树问题算法研究

研究内部节点受限的最小生成树问题:给定一个赋权无向完全图G=(V,E),假定w:E→R^+为边集E的权重函数且满足三角不等式,给定点集V的一个子集R(RV),目标是寻找图G的一个满足R中的点皆为内部顶点的权重最小的生成树。由于该问题是NP-困难的,提出了一个伪多项式时间最优算法,设计了一个近似比为2的多项式时间近似算法,并且给出例子以说明该近似比是紧的。

网络中一类最短支撑树的计算方法

本文在无向赋权图求最短路的Dijkstra算法的基础上,提出了在有向网络图中寻找具有一个枢纽点且与其它各点均有定向联系的最短支撑树的算法,同时还给出了应用该算法的一个计算实例。

邮路规划与邮车调度最优化理论研究

对小规模MTSP问题,建立了可精确求解方案的0-1规划模型,并在满足邮政运输需求的前提下给出了最佳方案.问题一首先以县支局、县局为顶点构建无向赋权图,通过Floyd算法求解各局间的最短距离;然后以Fijk为决策变量,以邮车工作时间、车辆运载能力为主要约束,建立以总空载损失费用最小为目标的0-1非线性规划模型,运用规划软件Lingo求解.问题二考虑到市邮路成本,我们采用分层规划策略,首先以市支局、县局为顶点构建无向赋权图,求解出最短路矩阵,建立以邮路运行成本最小为目标的0-1非线性规划模型IIA求解;然后,建立各县区的最短路矩阵,同样建立规划模型IIB求解各县运输方案.问题三由于县局地理位置不变,对区邮路无影响,故以全市各县支局为中心采用逐步最优方法对所有县区支局重新划分;然后采用模型IIB求解.第四问中考虑县局迁移,我们建立近似的启发式算法完成县局选址,并运用规划模型II求解的到新方案.最后,我们对两种区域划分调整方法还进行了定量的分析.