基于多头绒泡菌模型的图论关键问题研究

发布时间：2018-01-04 19:40

本文关键词：基于多头绒泡菌模型的图论关键问题研究　出处：《西南大学》2016年博士论文　论文类型：学位论文

【摘要】：图论问题是数学研究中与应用领域有密切联系的一个分支,其中一些经典问题已经有几十年的研究历史,且依然不断取得进步。由于这些经典问题的解决是实现许多现实应用的基础,而对这些问题解法的任何有益改进,都会对相应的应用领域有巨大的助益。比如最短路径问题和最大流问题,它们在路由、交通、决策、优化等方面的理论和应用中都有很重要的地位。这两类问题的传统算法已经很久没有取得实质性的突破。在单源最短路径树问题中,若不存在负权边,经典的Dijkstra算法的时间复杂度达到O(m+n log n),是该问题最快的算法之一。而当网络中存在负权边时,最好的强多项式算法是Bellman-Ford算法,时间复杂度达到O(nm),最好的弱多项式算法是缩放算法,时间复杂度达到O(√nm log U)。对于最大流问题,比较常用的算法为Dinic算法,时间复杂度为O(n2m)。该问题存在一个被称为流分解障碍的O(nm)时间界,任何利用增载轨的算法都无法突破这个障碍。许多优秀算法的时间复杂度已达到或突破这个界限,但实现起来非常复杂,实际效率也不高,限制了它们在实践中的应用。Dinic算法通过动态树优化可将时间复杂度降为O(nm log n),但动态树是十分复杂的数据结构,实现起来非常困难,实际性能也很差。1998年Goldberg和Rao首次获得突破流分解障碍的二分长度阻塞流算法,将时间复杂度刷新为O min n2/3,m1/2m log(n2/m)log U。该算法同样用到了动态树并且包含了大量的网络变换的操作,因此算法很复杂,实现起来比较困难,实际效率不高。解决图论问题的传统算法一般是基于对图的遍历,此类算法基本已经达到优化的极限。蚁群算法、遗传算法等启发式算法为我们提供了新的思路,那就是基于全局涌现的计算。启发式算法在传统算法无法解决的NP问题中有许多重要的运用,但在最短路径和最大流问题上始终无法取代传统算法,因为它们往往不是确定性算法,无法在确定的时间内得到准确的最优解,而且收敛速度也难以与传统算法相比。2000年,Tero等人揭示了多头绒泡菌生成迷宫中最优路径的特殊能力。多头绒泡菌是一种大型单细胞黏菌生物,按生物学分类归为变形虫门黏菌纲中的绒泡黏菌属,其营养构造,运动和摄食方式和原生动物中的变形虫相似。2007年他们又建立了多头绒泡菌的数学模型,该模型可以解决两点之间的最短路径问题,但效率并不稳定。本文在此基础上将原始的模型改进为具有稳定效率和确定结果的算法,称为变形虫算法,并运用到单源最短路径、最大流问题和一些实际问题中。该算法已经达到甚至超过了目前最好的传统算法。变形虫算法是一种通过正反馈的演化规则建立的非线性动态系统,通过不断演化涌现出最终结果。针对不同的问题,研究和制定不同的规则和限制条件,得到相应的结果。变形虫算法在每次迭代中需要解一个系数矩阵为拉普拉斯矩阵的线性方程组,目前求解线性方程组借助快速矩阵乘法的方法,可以达到O n2.X的时间复杂度,其中2.X=2.3728639,且还在不断进步,有望充分接近O(n2 log n)。同时,针对系数矩阵为拉普拉斯矩阵的特殊线性方程组,可以更快的求解,时间复杂度为O(m log n)。所以变形虫算法的时间复杂度的一般形式为O(km log n),k为迭代次数。本文将重点研究和改进变形虫算法来解决单源最短路径和最大流问题,以及在一些现实问题中的应用,创新的研究成果有以下几个方面:1、证明了多头绒泡菌数学模型的收敛性和正确性,以及它的收敛速度,并将多头绒泡菌的数学模型进行改进和离散化,形成原始的变形虫算法。对于2007年提出的多头绒泡菌模型,其收敛过程一直未得到充分的研究和证明。本文在原始模型的基础上稍作完善,并通过不变集理论证明了它在权值为正数,初始状态非0时,一定收敛于最短路径的解,同时,其收敛速度与网络的结构有关。我们将这一模型离散化,形成变形虫算法的原始版本,通过实验验证,原始变形虫算法是一个解决单源最短路径问题的伪多项式算法,对于整数问题,它的时间复杂度可以写为O U m log2n。原始变形虫算法只是搭建了一个解决问题的算法框架,体现了多头绒泡菌模型的正反馈机制。而针对不同问题,算法还需要进行相应的改进和优化。2、在原始变形虫算法基础上,通过扩展改进,形成解决带负权的单源最短路径问题的变形虫算法,并分析和比较它的求解效率,该算法优于Bellman-Ford算法,同时还具有检测、定位和消除网络中所有的负权环的能力。Bellman-Ford算法可以在O(nm)时间内求解带负权的单源最短路径,并判断网络中是否存在负环。本文在原始变形虫算法基础上,针对负权网络的单源最短路径问题提出改进和优化方案,得到时间复杂度为O(√nm log n)的算法。对于可能存在负权环的网络,Bellman-Ford算法需要到最后一次迭代结束才能判定存在负环,对应于算法的最坏情况,而变形虫算法可以在O n0.Zm log n内检测、定位和消除网络中的所有负权环,并且不破坏网络的连通性,这是其他算法都无法做到的,其中0.Z≈0.65。3、针对最大流问题模型,改进变形虫算法解决最大流问题,并分析和比较它的求解效率,该算法优于Dinic算法,同时还能得到网络的所有最小割。目前网络最大流问题的算法时间复杂度的精确下界还没有被找到,而流分解障碍O(nm)作为该问题中某一类算法的时间复杂度下界,在很长一段时间都没有被突破。直到1998年首次得到O min n2/3,m1/2m log(n2/m)log U的算法。但所有达到或突破O(nm)时间界的算法都需要实现复杂的数据结构或者网络变换操作,实际效率并不高,不具有实用性,较常用的算法仍然是具有O(n2m)时间复杂度的Dinic算法等。本文针对最大流问题设计的变形虫算法时间复杂度为O(log(nU)m log n),且易于实现,没有额外的开销。它是第二个突破流分解障碍的算法,并将该问题的时间复杂度一举拉低到?O(m)程度,且在实际效率上也优于Dinic算法,具有理论和实用价值。同时,它在迭代过程中,将网络自然的按最小割分割成几个部分,在获得最大流的同时也得到网络中的所有最小割。
[Abstract]:The problem of graph theory is a branch which is closely related to the field of application in mathematical research , some of the classical problems have been studied in several decades , and progress has been made . In 2000 , it is difficult to solve the shortest path problem by using heuristic algorithms such as ant colony algorithm and genetic algorithm . At the same time , the time complexity is O ( m log n ) for the special linear equations of the Laplace matrix for the coefficient matrix . This paper presents an algorithm for solving the shortest path problem of a single source . The algorithm is better than the Bellman - Ford algorithm . The algorithm is better than the Bellman - Ford algorithm . In order to solve the problem of maximum flow problem , the algorithm is better than the Dinic algorithm , and the algorithm is better than the Dinic algorithm . But all the algorithms that achieve or break O ( nm ) time limit need to implement complex data structure or network transform operation .

【学位授予单位】：西南大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O157.5

【相似文献】