A distributed message passing algorithm for the capacitated directed Chinese postman problem
A distributed message passing algorithm for the capacitated directed Chinese postman problem
复制标题
一种解决有向有向中国邮递员问题的分布式消息传递算法
DOI：
10.1016/j.compeleceng.2022.107755
复制
发表时间：
2022
影响因子：
4.3
通讯作者：
Yan Zhao
中科院分区：
文献类型：
--
作者：
Guowei Dai;Yuefang Sun;Xiaoyan Zhang;Yan Zhao
消息传递是一类基于概率图模型的分布式迭代算法，它在最小数据结构上每次迭代的计算量很小。置信传播算法作为一种典型的消息传递算法，在编码理论、机器学习和组合优化等领域有着广泛的应用。由于BP算法的分布式和迭代性，它可以在大数据量的网络上快速有效地运行。本文研究了求解有能力约束的有向中国邮递员问题（CDCP）的Min-Sum BP算法的性能。推导了求解CDCP的消息传递迭代过程。作为主要结果，对于任意n重有向图G，如果G的每条边的权都是非负整数，则只要CDCP有唯一的最优解，我们的算法经过O（w <$n2）次迭代就收敛到CDCP的最优解，其中w <$= max {w e：e∈ E（G）}.
Message passing is a class of extremely powerful distributed iterative algorithms based on probabilistic graphic model, in which little computation performed per iteration on minimal data structure. As a prototypical message-passing algorithm, belief propagation (BP) algorithm has wide applications in various fields of coding theory, machine learning and combinatorial optimization. Due to its distributed and iterative nature, BP algorithm can run effectively and fast on large data networks. In this paper, we study the behavior of Min-Sum BP algorithm for the capacitated directed Chinese postman problem (CDCP). We derive the iterative process of message passing for solving CDCP. As the main result, for any weighted digraph G of size n, if the weight on each edge is nonnegative integral, then our algorithm converges to the optimal solution of CDCP after O (w∗ n 2) iterations, provided that CDCP has a unique optimal solution, where w∗= max {w e: e∈ E (G)}.