网络分析中求最大流的商空间方法  

The Computation of Maximum Flow in Network Analysis Based on Quotient Space Theory

作　　者：郑诚[1] 张铃[2] 

机构地区：[1]安徽大学计算智能与信号处理教育部重点实验室,合肥230039 [2]安徽大学计算机科学与技术学院,合肥230039

出　　处：《计算机学报》2015年第8期1705-1712,共8页Chinese Journal of Computers

基　　金：国家自然科学基金(61073117;61273302);安徽省自然科学基金(11040606M133);安徽省高校自然科学研究重点项目(KJ2013A020)资助~~

摘　　要：该文研究利用商空间的保真、保假原理给出分析网络的新方法,并以求网络中两点的最大流量为例进行说明,主要工作包括:(1)给出利用保真、保假原理求解问题的基本原则;(2)给出将所研究的问题(求最大流问题)化成"问题求解"形式的方法;(3)利用商空间理论建立对应问题求解的保真、保假原理,并证明对所研究的问题,保真、保假原理均成立;(4)根据保真、保假原理给出求两点最大流量的方法.新方法对求所有的点对点的最大流的计算量由原来需要求n(n-1)/2次点对点的最大流,变成只要求(n-1)次点对点的最大流,显著降低了计算的复杂性.A novel network analysis technique by using＂falsity preserving＂and＂truth preserving＂properties are presented.It is illustrated with computing maximum flow between two points in the network.The main contributions are as follows：（1）The basic principles of the use of falsity preserving and truth preserving on solving problems.（2）The method of transformation from the maximum flow problem into the form of＂problem solving＂.（3）The falsity preserving and truth preserving principle based on quotient space theory are established and proved to be correct on the corresponding problem solving.（4）The computation of maximum flow between two points in the network by using falsity preserving and truth preserving properties.By using this method,the computational complexity of maximum flow among all points is（n-1）times that between two points.However the existing method computational complexity is n（n-1）/2times.

关 键 词：粒计算 商空间 保真原理 商逼近原理 最大流 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]