最小平均长度回路问题的一个有效算法

摘要

本文提出了求解最小平均长度回路问题的一个有效算法。从本质上来说,这一算法是原始——对偶算法。该算法通过反复求解一系列织合特点更强的子问题,从而有效地求得最优解。我们还证明了算法的复杂性为 O(n^4),并且通过计算大量随机产生的实例并与已有算比较,证明该算法是很有效的。