Особенности применения алгоритма полного перебора для решения задачи квадратичного назначения ; The features of using a brute force algorithm for solving a quadratic assignment problem

Алгоритм полного перебора вариантов – это универсальный метод решения задач дискретной оптимизации, обеспечивающий нахождение всех возможных комбинаций параметров, соответствующих экстремуму критериальной функции. Основным недостатком алгоритма является высокая вычислительная сложность, препятствующая его использованию для решения практических задач большой размерности. В статье рассматриваются некоторые методы ее снижения при решении задачи квадратичного назначения, не приводящие к потере точности. Кроме традиционного подхода, опирающегося на распараллеливание ресурсоемких вычислений, исследованы способы ускорения процесса генерации вариантов и ограничения их числа. Результаты вычислительных экспериментов подтверждают эффективность предложенного подхода и возможность его использования в последовательных и параллельных реализациях алгоритма перебора. Для последовательного приложения получено более чем 2000-кратное ускорение вычислений, а многопоточное приложение дает рост производительности еще в 2,3 раза при запуске на четырех ядерном процессоре. ; The brute force algorithm of the variants is a universal method for solving discrete optimization problems, which provides finding all possible combinations of parameters corresponding to the extremum of the criterion function. The main disadvantage of the algorithm is its high computational complexity, which prevents its use for solving practical problems of large size. The article discusses some methods for reducing its computational complexity when solving the quadratic assignment problem, which do not lead to loss of accuracy. In addition to the traditional approach based on parallelization of resource-intensive computations, methods to accelerate the process of generating variants and limiting their number have been investigated. The results of computational experiments confirm the effectiveness of the proposed approach and its applicability in sequential and parallel implementations of the algorithm. The sequential application was obtained more than 2000x ...