二阶数乘问题的一个最优算法

摘要

研究一个有趣的组合优化问题——二阶数乘问题.问题描述如下:给定n≥2个正整数a1,a2,…,an,设π为{1,2,…,n｝的一个置换,表示该问题的一个解,试图找到一个置换πr以至∑ni=1aπiaπi+1最小,在这里πn+1=π1.给出了一个算法复杂度为O (n logn)的最优算法.