【摘 要】
：
最大流问题在许多工程领域和物理、化学、生物以及管理科学和应用数学等科学领域有着广泛的应用.然而随着网络规模的增加,传统的算法无法快速高效地求解最大流问题,算法的实际性能也不能满足许多应用问题的要求.针对求解一个给定的有向网络上最大流问题,本文提出一种新方法——收缩邻居节点集的方法(CNA).该方法旨在通过收缩邻居节点集来有效降低网络规模,使得经典算法及改进算法可以直接使用.首先给出收缩邻居节点集的
【机 构】
：
安徽大学计算机科学与技术学院 合肥230039 安徽大学计算智能与信号处理教育部重点实验室 合肥2
【出 处】
：
第十二届中国Rough集与软计算学术会议、第六届中国Web智能学术研讨会及第六届中国粒计算学术研讨会联合学术会议
论文部分内容阅读
最大流问题在许多工程领域和物理、化学、生物以及管理科学和应用数学等科学领域有着广泛的应用.然而随着网络规模的增加,传统的算法无法快速高效地求解最大流问题,算法的实际性能也不能满足许多应用问题的要求.针对求解一个给定的有向网络上最大流问题,本文提出一种新方法——收缩邻居节点集的方法(CNA).该方法旨在通过收缩邻居节点集来有效降低网络规模,使得经典算法及改进算法可以直接使用.首先给出收缩邻居节点集的条件,接着给出依据收缩条件构建目标网络的算法,最后利用经典算法求解目标网络的最大流以实现初始网络最大流的最优近似.实验结果表明收缩邻居节点集的方法不仅平均能将目标网络的规模降至初始网络的一半,而且能够以非常小的误差求得初始网络的最大流.
其他文献
研究了M-格蕴涵代数作为赋值域的格值模态命题逻辑系统中的演绎定理与替换定理,从而为格值命题逻辑系统的完备性定理奠定了基础.
Recently,the connection between Matrix Theory and Formal Context Analysis (FCA) has been widely explored.However,most of the literatures only paid attention to non-linear decomposition of matrix,and o
粗糙集理论已成功应用于数据挖掘、模式识别、机器学习等领域,但粗糙集理论应用于神经网络结构选择的工作尚未见到.本文提出了一种基于相容粗糙集技术的ELM网络结构选择方法,该方法利用相容依赖度度量神经网络隐含层结点的重要性.实验结果证明本文提出的方法是行之有效的.
云模型是用语言值表示的定性概念与其定量表示之间的不确定性转换模型.基于云模型概念内涵与外延之间的不确定性双向转换机制,通过给出的概念区间映射方法,将两个(或多个)原始概念分别映射到它们共同的交、并区间上,通过云滴隶属度的模糊运算定量实现概念内涵的“软交”、“软并”逻辑运算.
基于粗糙集理论定义的属性约简大都要求约简前后正区域保持不变或者非负区域不变.在概率型决策粗糙集模型下,决策区域和决策规则与属性增减之间并不具备单调性.因此,决策者基于约简后的属性集合所作的决策风险最小就变得非常有意义.针对这种与各个区域无关的基于决策风险最小化的属性约简进行了研究.考虑到不同属性对决策表的决策分类能力不同,提出了基于决策粗糙集模型的属性重要性概念,从而设计了一种有效的基于属性重要性
人脸表情特征选择是人脸表情识别研究领域关注的一个热点.结合量子遗传算法与邻域粗糙集理论,提出一种新的人脸表情特征选择方法FSNRSTQGA (Feature Selection based on Neighborhood Rough Set Theory and Quantum Genetic Algorithm).首先,以邻域粗糙集理论为基础,定义了最优特征集的适应度函数,来评价表情特征子集的选
This paper is intended to improve moving object image processing.Based on rough set theory,a split decision algorithm of image segmentation is proposed.Removal of noise is based on a new filtering def
在粗糙集不确定性度量公式中,模糊熵和模糊度是重要的度量方式.根据粗糙集不确定性度量中模糊熵和新的模糊度公式,提出了在决策信息系统中修正条件信息熵和相对模糊熵的概念,并分别用两种方式证明了熵在属性约简过程中的单调性.然后利用向前添加属性算法进行属性约简,约简结果在RIDAS平台上进行识别率测试,通过实验对比分析了提出的两种新的信息熵与条件信息熵的约简,从而为基于信息熵的属性约简提供了参考.
相对于硬聚类算法,软聚类算法可以更好地表示具有不精确边界的类簇.粗糙集和模糊集均是用于描述不精确数据的有效的数学工具,二者之间互为补充.研究人员已经将粗糙集和模糊集的概念相结合,并应用到聚类算法中.而阴影集的引入可以有效地解决粗糙模糊聚类算法中的阈值选择问题.
随着社会媒体的发展,用户网络将产生大量内容,发现其潜在的社区及主题便于了解网络结构及用户兴趣,进行更深层次的分析和预测.融合内容和链接的主题发现或社区发现概率模型成为完成该任务的主流方法,按模型目标将其分为主题发现模型、主题社区发现模型和社区-主题发现模型.分析各模型的设计背景、基本原理、参数求解及优缺点等,并通过典型模型的定性比较和定量实验分析探索该类模型存在的问题,最后预测来来融合模型的可能研