基于图算法的电路模块划分方法的研究

论文摘要

电路模块划分方法是一种采用分治策略,按照一定的约束条件和标准将大型电路系统划分为若干个子电路的技术。其包括三方面的研究内容:一是电路系统拓扑关系的表达问题,二是分割电路的标准和约束条件的问题,三是根据划分的标准和要求研究具体的分割方法。电路模块划分方法无论是在电路系统的并行仿真,故障定位还是资源调配等方面都用广泛的应用。电路模块划分可以抽象成图或超图的分割问题。本文在研究以往电路模块划分方法的基础上,针对电路系统拓扑关系的表达问题,分别提出了电路拓扑关系图和超图模型,并使用稀疏矩阵存储技术和平衡二叉树存储电路拓扑图。针对电路分割的标准问题,在不同的应用背景下,分析并提出了不同的分割标准,并验证了其有效性。本文在具体分割方法的研究中,针对大型电路系统一次划分欠佳的问题,提出了层次划分的概念。并分别在电路系统图模型和超图模型下,根据电路的特点以及分割的目的,提出了几种迭代改进方法。并提出一种散列技术,提高了迭代改进方法中查找最优交换顶点对的效率。此外针对确定性算法有可能陷入局部最优的情况,提出了一种基于模拟退火方法的迭代优化改进算法。实验表明本文提出的几种算法在满足一定的时间复杂度的情况下,可以有效的达到分割的最优解。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 电路模块划分方法概述
• 1.2 课题研究的背景，目标以及意义
• 1.3 本文主要内容及组织
• 第二章 电路系统拓扑关系的表示
• 2.1 图论在电路拓扑关系中的应用
• 2.1.1 电路系统的图表达形式
• 2.1.2 电路系统的超图表达形式
• 2.2 电路系统图的储存形式
• 2.2.1 PSPICE网表文件的表达形式
• 2.2.2 稀疏矩阵存储技术
• 2.3 小结
• 第三章 电路模块划分约束条件研究
• 3.1 电路模块划分标准分析
• 3.1.1 Ncut准则和Mcut准则
• 3.1.2 电路划分问题的定义
• 3.2 电路模块划分在电路故障诊断中的约束条件分析
• 3.2.1 自测试条件STC与互测试条件MTC
• 3.2.2 运用测试条件与逻辑分析识别故障子网络
• 3.2.3 电路故障诊断约束条件的研究
• 3.3 小结
• 第四章 电路模块划分算法研究
• 4.1 初次聚合阶段
• 4.1.1 基于势能方法的贪婪算法
• 4.1.2 基于深度为N的广度优先搜索算法（BFS）的方法
• 4.2 二次聚合
• 4.2.1 基于FM算法的分割方法
• 4.2.2 针对有权图模型的划分方法
• 4.2.3 针对有权图模型的随机算法
• 4.3 小结
• 结论
• 致谢
• 参考文献
• 在校期间科研工作