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

An optimal algorithm for the two-order multiple problem

研究一个有趣的组合优化问题——二阶数乘问题.问题描述如下：给定n≥2个正整数a_1,a_2,…,a_n,设π为{1,2,…,n}的一个置换,表示该问题的一个解,试图找到一个置换π以至∑_（i=1）~n a_（π_i）a_（π_（i＋1））最小,在这里π_（n＋1）=π_1.给出了一个算法复杂度为O（n log n）的最优算法.

In this paper, we present a new and interesting combination optimization problem called two-order multiple problem. The problem is stated as follows. There are n ≥2 integers a1, a2, ..., an, let π be a permutation of {1,2,... ,n} which also shows a solution to the problem. We must try to find the optimal permutation 7r so that the value f o ∑i=1 aπiαπi＋1 is minimal, where πn＋1 =π1. We provide a polynomial-time algorithm with the complexity of O（n log n） for it.