快速求解最大网络流问题的新算法研究

论文研究-企业存储网格中资源请求任务的模拟与分析 本论文研究的主要目的是为了解决企业存储网格中资源请求任务的模拟与分析问题。通过构造网络级连层次图的方法，来间接求出最大网络流的算法。该算法可以在On2时间内快速求出流经网络N的最大网络流及达最大流时的网络流。 在现实社会中，存在着许多“流”，如交通运输系统中的车流、水利系统中的水流、物资供应系统中的物流、Internet网中的信息流等等。这些流的共同特征是从生产该载流物资的“源”出发，经过一个系统流向另一个消费该物资的“汇”。“源”以固定的速度产生该物资，“汇”以同样的速度消耗该物资。所谓“流”就是该物资在系统中的传送，流的流量就是其传送的速度或物资的输送量。 最大流问题就是确定系统在满足一定约束条件下，流从“源”点到“汇”点所传送载流物资的最大速度或物资在系统中的最大输送量。最大流问题在工程计划、预算、运输管理和网络信息传输等方面都十分有用。特别在信息万变的网络化社会的今天，信息以十分惊人的速度在网络中传送，网络信息的传播和异地处理，以及如何提高Internet网的网速及怎样设定和分配各网络站点的网络速度和网络流量等都与最大网络流问题的处理和解决息息相关。 因此，如何快速求出最大网络流，一直是人们十分关注的问题，特别是计算机网络和网络图论学者多年来潜心研究和探讨的课题。虽然已相继得出一些结论，但仍满足不了信息大爆炸时代的当今社会对信息的传送和处理的需要。 给出的算法可在O(n2)时间内快速求出最大网络流，较之已有的成果，如MPLA算法等找到最大网络流需要O(n´e2)时间，Dinic算法等找到最大网络流时间为O(e´n2)时间，MPM算法等找到最大网络流的时间为O(n3)时间，本算法无疑是一个飞跃，速度提高了一个数量级。 在最大流问题中，O(n´e)时间界是一个自然的障碍（通用算法的下界），在很长一段时间内，O(n´e)的时间界没有被突破。因此，O(n´e)时间被称为最大流问题的流分解障碍。目前对一般的实数容量的最大流问题，最好的通用算法时间复杂度为O(n´e´log(n2e))。 在计算机工程与应用中，最大流问题的解决对信息的传送和处理的需要至关重要。因此，本论文研究的结果将对信息传送和处理的研究和应用产生重要的影响。 本论文研究的结果对计算机工程与应用的影响： 1. 提高了信息传送和处理的速度和效率，满足了当今社会对信息的传送和处理的需要。 2. 提供了一个快速求出最大网络流的算法，解决了最大流问题的流分解障碍。 3. 对计算机网络和网络图论的研究和应用产生了重要的影响。 本论文研究的结果对计算机工程与应用的影响是非常重要的，能够满足当今社会对信息的传送和处理的需要。