简单图中回路问题的求解

回路是图论中一个重要的概念 ,在软件设计中也有广泛的应用。文章对简单图中回路的搜索问题进行了详细的讨论 ,在原有针对结点的遍历算法基础上构造出适用于路径搜索的算法 ,并着重分析了在无向图中简化搜索路径、提高算法效率的问题 ,使之成为更具一般性的回路搜索算法     

节点分层法求解通风网络中的所有通路

针对目前通风网络所有通路搜索算法效率较低的问题,提出节点分层法.通过节点分层和层间分支拼接求解所有通路,避免了频繁的后退操作,提高了算法效率.根据节点分层法和现有通路搜索方法开发了算法效率测试软件,并对不同规模的通风网络进行所有通路搜索效率对比测试.研究结果表明:节点分层法搜索效率随着网络规模增大而提高;对于1 010条分支的通风网络,节点分层法较深度优先搜索法提高41.59%.该方法适合大规模通风网络所有通路的快速求解.     

含有单向回路的风网平衡图绘制方法

在火风压作用下发生风流逆转和采用多级机站通风的矿井往往存在单向回路。通风网络中存在单向回路时,将无法绘制其所对应的平衡图。采用通风网络拓扑关系等效变换的方法,删除造成单向回路的风机分支,并构造新的风机分支．其末节点是新网络的汇点,原风机分支末节点是新网络的源点,变换后的网络与原网络在分支数上相同,说明平衡图矩形块的个数不变。除造成单向回路的风机分支外,变换后的网络与原网络拓扑关系相同。将含有单向回路的通风网络变换成无单向回路的通风网络,从而实现了含有单向回路的风网平衡图的绘制。     

用独立通路法确定矿井通风网络的极值流

确定矿井通风网络极值流的常用算法有Ford-Fulkcrson法、Edmonds-Karp法和Dinic法。所谓独立通路就是采用深度优先搜索法在找通路的过程中，后面的通路至少要含有一条前面的通路所不含有的分支。独立通路法确定网络的极值流，就是利用找独立通路的思想来找增广路，找增广路时每次至少有一个分支达到饱和。从网络的源点开始进行寻边，找分支的可增广量为量大的出边，将该出边的末节点作为新的寻边始节点，继续找可增广量最大的出边，该搜索过程一直到所寻找的分支的末节点为网络的汇点为止，一条增广路即一条通路确定完毕，将该通路中分支的最小增广量作为通路的增广量对通路的各分支进行增广。增广后至少有一条分支达到饱和，删除饱和分支，用导出的网络继续找新的增广路并增广。     

建立矿井通风网络独立回路矩阵的一种快速算法

本文通过对矿井通风网络基本关联矩阵的特性进行分析，提出了一种只需对矿井通风网络基本关联矩阵进行有限步初等行运算，便能迅速建立独立回路矩阵的算法。     

矿井通风网络风流控制的实用算法

介绍矿井通风网络风流控制的一般性结论、基本数学模型和计算方法，指出了常规计算方法的不足，提出了一种能够避免大量矩阵运算、适用于实际通风网络的新算法，其程序简单，计算时问省，并结合实例阐述了算法原理。     

哈密顿回路存在性判定及输出算法

给出L集合、L矩阵、连接积和通路矩阵的概念及基于这些概念的一些哈密顿回路的存在性判定定理和通过构造通路矩阵序列Mk=Mk－1*M（k=2，...，n）直接求出简单图（无向和有向）的全部哈密顿回路的算法及实例．     

利用早停可微架构搜索的三维点云模型分类

针对现有三维点云分类网络采用人工设计费时费力的问题,提出早停可微架构搜索(early-stopping differentiable architecture search,ES-DARTS)算法。利用从人工设计网络架构中提取到的先验知识,预定义一个包含高效候选操作的搜索空间,可快速搜索出适用于三维模型分类任务的高性能网络模型;通过追踪网络搜索阶段各候选操作的权重变化,找出跳跃连接操作在双重优化过程中发挥不公平竞争作用的临界点并在此处停止搜索,以保证各候选操作之间的稳定性,解决DARTS算法搜索过程中易出现性能崩溃的问题。提出的算法在ModelNet40数据集上达到了93.2%的识别准确率,比当前人工设计的主流网络具有更高的识别准确率。     

基于遗传算法的一体化通风网络优化算法

概括混合型一体化通风网络优化的模型,分析目前混合型通风网络优化的4种求解方法优缺点。针对混合型通风网络优化的要求,提出混合型通风网络风量分配和风流调控一体化的优化思路。在通风网络理论和图论的基础上,引入遗传算法随机产生2个动态网络的邻接矩阵和余树弦风量值,使用附有条件的最小支撑树算法产生2个最小支撑树,进而求得相应的回路矩阵。通过余树弦风量值和回路矩阵等分别计算通风网络风量分配值和风阻调节值,基于通风总功率和约束条件构建广义最小化目标函数,依此对分风和调风方案进行评价,使用遗传算法中进化算子对分风和调风方案实施进化操作,最终得到满意解。研究结果表明：该算法是严格数学意义上全局优化算法,解决调风地点约束的通风网络优化问题,利用网络结点流量平衡的等式约束条件,减少最优化模型中变量数目,提高算法效率。     

基于遗传算法的通风网络两步法风流调节优化算法

概括混合型通风网络优化模型,归纳混合型通风网络风量最优分配和风流最优调控两步法优化基本框架。首先,在满足矿井通风风量需求的基础上,实现风量分配优化。然后,结合矿井通风网络实际调风需求,引入遗传算法随机产生动态网络的邻接矩阵,使用附有条件的最小支撑树算法求解部分余树弦(调风地点)约束下的最小支撑树和独立回路矩阵,根据回路矩阵计算通风网络余树弦风阻调节值,在通风总功率和约束条件基础上构建广义最小化目标函数,依此对调节方案进行评价,使用遗传算法中的进化算子对调节方案编码实施进化操作,最后通过迭代得到满意解。研究结果表明:两步法思想简化混合型通风网络优化问题,解决调风地点约束的通风网络优化问题,执行效率高,能够解决较大规模的通风网络优化问题。     

基于邻接矩阵的电力电子变换器潜电路分析方法

建立了电力电子变换器潜电路的邻接矩阵分析方法。将变换器各元件间的连接状态采用邻接矩阵存储,通过深度优先搜索算法对邻接矩阵中处于连接状态的顶点序列进行搜索,根据路径判别条件实现了潜电路的识别,得到用顶点序列描述的潜电路路径。以C和VC＋＋6.0为平台编制了基于邻接矩阵的电力电子变换器潜电路分析软件,并以升压谐振开关电容变...     

一种带路径约束的多商品流网络设计问题及其禁忌算法

多商品流网络设计问题在实际中有很广阔的应用背景,然而在多商品流模型中,有些实际应用问题对运送商品的路径提出了额外要求,如时间、可行性等．在此,将考虑一种带路径约束的多商品流网络设计问题,并借助改进单纯形法、列生成和最短路径算法为提出的模型构造一种禁忌(tabu search)算法,最后给出该算法的计算实验结果．     

矿井通风仿真系统中的网络简化技术

通风网络自动简化技术是矿井通风仿真系统的重要组成部分，它是分析矿井通风系统的强有利工具。网络简化对提高与通风网络拓扑关系相关的计算程序的运算速度以及降低计算机内存占有量也具有重要意义。在通风网络风量按需调节通路法、计算机自动识别角联风路等方面都涉及到通路的计算问题，有时风路增加1条有可能导致通路总数的成倍增加，所以对通风网络进行自动简化处理具有非常重要的意义。从图论和集合论出发，通过对网络拓扑关系的分析，提出了通风网络简化的数学模型，分析了网络简化的层次性，应用开发的网络简化软件对铁法矿务局大明一矿的通风网络进行了简化处理。     

存在风阻未知分支的大规模复杂通风网络解算方法

在一个复杂的地下矿通风网络中,通常存在风阻或风量无法直接通过工程的方法事先测量出来的分支,为复杂通风网络中分支风流特征突然改变的原因推断带来了相当大的困难。为了解决此问题,利用通风系统节点风量平衡定律、回路风压平衡定律和通风系统中其风阻值或风量值可事先测量出来的部分分支的信息,重新构建了通风系统风网解算模型,通过对该模型的严密理论推导,获得了一种新的风网解算方法．该算法还可进行通风系统漏风点辨识。     

网孔自动搜索算法在水电仿真中的设计与实现

将电路抽象为图论中的图,在验证了网孔和最小独立闭合环一致性的基础上,把求电路中网孔的问题转化为抽象图中搜索最小独立闭合环的问题;然后以图论中图的广度优先搜索算法为基础,给出了基于广度优先搜索的最小独立闭合环自动搜索算法(BSA)的基本原理和算法描述.实验表明,该算法可以准确高效地搜索出图中所有的最小独立闭合环,算法的运行速度快,占用的空间小,完全可以满足实时性和内存空间的需求.     

小世界模型下基于信任机制的资源搜索

在P2P中,大量的资源共享已经成为重要应用之一。有效的资源搜索方法是实现资源共享功能的重要基础,资源搜索效率既取决于网络的拓扑结构,又与搜索策略相关。现有的搜索算法存在网络负载较大和搜索效率偏低的问题。以P2P为研究对象,根据小世界网络较短平均路径长度和较高聚类系数的特性,提出一种小世界模型下基于信誉机制来遴选最优路径(CMS),从而实现一定可信程度下资源高效率搜索。实验结果表明,该搜索机制提高资源搜索的命中率的同时,有利于数据包的快速传递且具有一定的资源搜索可信性。     

ATE开关矩阵最短路径搜索算法

 开关矩阵作为信号传递的枢纽,在自动测试设备内部扮演着极其重要的角色。当信号源节点与目标节点之间距离最短时,信号才能最有效地传输。基于开关矩阵的物理模型,结合图论知识,构造了开关矩阵的数学模型。针对通路继电器最少、系统可靠性最高2 种情形,把路径最短问题抽象成无权图和有权图的最短路径搜索问题,分别采用广度优先搜索（BFS）算法和Dijkstra 算法进行研究,并提出改进型算法。通过具体实例,建立模型并应用改进算法予以实现。改进算法应用于ATE 通用适配器的开发研制和自动测试设备软件平台的设计,可实现最佳测试路径的快速自动搜索,具有工程实践价值。     

基于驱动参数建模的可行更改路径搜索和优选方法

为了解决产品设计更改中可行更改路径分析困难的问题,提出了一种基于驱动参数建模的可行更改路径搜索和优选方法.从集合论观点出发描述了产品中的更改传播现象;在传统产品参数建模的基础上构建产品驱动参数关联网络模型,并介绍了产品模型的预处理方法;引入深度优先搜索算法(Depth First Search,DFS)实现可行更改路径的搜索;提出了评价最优更改路径的指标和优选准则指导更改方案优选工作,采用多属性决策方法(Technique for Order Preference by Similarity to an Ideal Solution,TOPSIS)完成最优更改方案的优选;通过开发的原型系统,实例验证了该方法的可行性.