二阶数乘问题的一个最优算法 |
| |
引用本文: | 万龙.二阶数乘问题的一个最优算法[J].运筹学杂志,2014(3):99-103. |
| |
作者姓名: | 万龙 |
| |
作者单位: | 江西财经大学信息管理学院,南昌330013 |
| |
基金项目: | 江西省自然科学基金项目(No.20142BAB211017),江西财经大学校级课题项目(No.06162015). |
| |
摘 要: | 研究一个有趣的组合优化问题——二阶数乘问题.问题描述如下:给定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)的最优算法.
|
关 键 词: | 二阶数乘 算法复杂度 最优算法 |
An optimal algorithm for the two-order multiple problem |
| |
Authors: | WAN Long |
| |
Abstract: | 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. |
| |
Keywords: | two-order multiple algorithm complexity optimal algorithm |
本文献已被 维普 等数据库收录! |
|