基于记忆化搜索的分层网络最大流算法  

Maximum Flow Algorithm of Hierarchical Network Based on Memory-aided Search

作　　者：林俊余 朱磊 LIN Jun-Yu;ZHU Lei(School of Computer Science and Intelligence Education,Lingnan Normal University,Zhanjiang 524048,China)

机构地区：[1]岭南师范学院计算机与智能教育学院,湛江524048

出　　处：《计算机系统应用》2023年第6期140-148,共9页Computer Systems & Applications

基　　金：广东省教育厅普通高校特色创新项目(2021KTSCX065)。

摘　　要：当前,路由选择算法、计算机视觉图像切割以及机器学习领域的许多问题都可以归结为求解网络最大流.为了提高基于分层网络最大流算法的效率,提出了一种基于记忆化搜索策略的最大流算法,针对传统EdmondsKarp算法和Dinic算法重复搜索无效路径所导致的额外开销问题,设计了一种能够记录搜索状态的记忆化搜索策略,来避免重复搜索流网络中的无效部分.实例分析表明了记忆化搜索策略的高效性与可行性.最终实验结果表明,基于记忆化搜索的最大流算法执行效率优于传统的Dinic算法.The rooting algorithms,image segmentation in computer vision,and many problems in machine learning can be regarded as problems seeking solutions to the maximum flow of networks.For more efficient maximum flow algorithms based on hierarchical networks,a maximum flow algorithm based on a memory-aided search strategy is put forward.The traditional Edmonds-Karp algorithm and Dinic’s algorithm suffer from extra overhead due to repeated searches of invalid paths.Hence,a memory-aided search strategy that can record search states is proposed to conquer this problem.Experimental results show that the proposed strategy is efficient and feasible,and the proposed algorithm outperforms Dinic’s algorithm.

关 键 词：最大流 流网络 层次网络 记忆化搜索 最短增广链路 

分 类 号：O157.5[理学—数学]