最大流最小截问题的算法研究与应用

发布时间：2018-07-14 08:58

【摘要】：最大流最小截问题属于一个组合优化问题,经过多年的研究,获得了大量的的研究成果。同时最大流最小截问题在大量实际生活中的网络都取得了广泛的应用,并且很多的的工期优化、流程控制等管理学科的问题以及图像处理中图割问题都可以转化最大流最小截问题模型求解。本文主要研究两种最大流最小截问题的求解算法及其应用,做出了如下成果:1.提出了一种改进最短增广链算法。在改进算法中删除了原网络中在增广过程中达到饱和弧。从而优化了算法中的构建剩余分层网络的过程。实验结果显示:改进算法的效率优于传统算法。2.提出了最大流最小截问题的遗传算法解法。在算法中主要设计了算法中个体编码解码方法、初始群体生成方法、适应度计算方法和选择交叉变异算子。实验结果表明:该算法能够在稳定计算最大流最小截问题,并且算法效率优于传统算法。3.介绍了最大流最小截问题在图割技术中的应用。描述了图割问题与最大流最小截问题模型之间的转换。最后通过实验,对图像进行分割。
[Abstract]:The maximum flow minimization problem belongs to a combinatorial optimization problem. After many years of research, a large number of research results have been obtained. At the same time, the maximum flow minimization problem has been widely used in a large number of real life networks, and a lot of time optimization, The problem of flow control and other management disciplines as well as the graph cutting problem in image processing can be solved by transforming the model of maximum flow and minimum cut problem. In this paper, we mainly study two algorithms and their applications for solving the maximum flow and minimum truncation problem, and make the following results: 1. An improved shortest augmented chain algorithm is proposed. In the improved algorithm, saturation arcs are removed from the original network during the expansion process. Thus, the process of constructing the residual hierarchical network in the algorithm is optimized. The experimental results show that the efficiency of the improved algorithm is better than that of the traditional algorithm. A genetic algorithm (GA) method for solving the maximum flow minimum truncation problem is proposed. In the algorithm, the individual coding and decoding method, the initial population generation method, the fitness calculation method and the selection of crossover mutation operator are designed. The experimental results show that the proposed algorithm is more efficient than the traditional algorithm. The application of maximum flow minimization problem in graph cutting technique is introduced. The transformation between the graph cutting problem and the maximum flow minimum truncation problem is described. Finally, the image is segmented by experiment.
【学位授予单位】：南京邮电大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5;TP18

【相似文献】