Методы повышения эффективности алгоритма полного перебора на примере решения задачи о неограниченном ранце ; Methods for improving the efficiency of Brute-force algorithm by the example of solving an Unbounded Knapsack Problem

Универсальным методом точного решения задач дискретной оптимизации, инвариантным к условиям поиска, является алгоритм полного перебора вариантов (BFA). Его широкое использование на практике, ограничивает высокая вычислительная сложность, определяемая размерностью пространства поиска. Это определяет интерес исследователей к поиску подходов к ограничению числа рассматриваемых вариантов решения без потери его точности. В статье рассматривается вопрос повышения эффективности алгоритма полного перебора вариантов при решении задач дискретной оптимизации. На примере задачи о неограниченном ранце (UKP) показана возможность реализации генератора, обеспечивающего исключение вариантов, не удовлетворяющих условиям задачи, без расчета критериальной функции. Проведена оценка реализуемости генераторов и для многопоточных BFA-приложений. Подтверждена эффективность предложенного подхода и для последовательных и для параллельных реализаций. Результаты вычислительных экспериментов совпадают с теоретическими расчетами. Четырех поточное приложение с оптимизированным генератором обеспечивает более чем 30-ти кратное ускорение вычислений. Исследуемый подход может применяться и для других задач дискретной оптимизации. ; A universal method for the exact solution of discrete optimization problems, invariant to search conditions, is the exhaustive search algorithm (Brute Force Algorithm, BFA). Its wide use in practice is limited by the high computational complexity determined by the dimension of the search space. This determines the interest of researchers in finding approaches to limiting the number of considered solutions without losing its accuracy. The issue of increasing the efficiency of the brute force algorithm for solving discrete optimization problems is considered. On the example of the unbounded knapsack problem (Unbounded Knapsack Problem, UKP), we show the possibility of implementing a generator that ensures the exclusion of variants that do not satisfy the conditions of the problem, without calculating the criterion ...