OPTIMIZATION OF THE PROBLEM SOLVING WITH LIMITED RESOURCE
Abstract
The knapsack problem is analyzed on the basis of the mathematical model, which uses the means of multicriterial optimization. The method which defines possible redundancy of the initial data set is offered for the problem. The algorithm of the transition to the task with a changed set of initial data is developed. The algorithm of pareto elements division into subsets with ordered upper and lower criteria borders is executed. The complexity estimation of proposed algorithms is realized and the general approach to the knapsack problem solving is presented.
About the Authors
S. V. Chebakov
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
L. V. Serebryanaya
Белорусский государственный университет информатики и радиоэлектроники
Belarus
Belarus
References
1. Чебаков С.В. // Вести НАН Беларуси. Сер. физ.-мат. наук. 2005. № 2. С. 112-118.
2. Чебаков С.В. // Вести НАН Беларуси. Сер. физ.-мат. наук. 2009. № 3. С. 105-113.
3. Kung H.F., Preparata F.P. // J. of the Association for Computing Machinery. 1975. Vol. 22. P. 469-476.
Review
For citations:
Chebakov S.V., Serebryanaya L.V. OPTIMIZATION OF THE PROBLEM SOLVING WITH LIMITED RESOURCE. Doklady BGUIR. 2016;(8):46-52. (In Russ.)
Views: 315
Email this article 