Изучение производительности алгоритма случайного поиска при решении квадратичной задачи о рюкзаке с многомерными ограничениями в контексте оптимизации рендер-конвейера трехмерной графики : доклад, тезисы доклада
доклад, тезисы доклада, статья из сборника материалов конференций
Библиографическое описание:Изучение производительности алгоритма случайного поиска при решении квадратичной задачи о рюкзаке с многомерными ограничениями в контексте оптимизации рендер-конвейера трехмерной графики : доклад, тезисы доклада / В. Н. Мымликов. - [Б. м. : б. и.], 2026. - Текст : непосредственный // Достижения науки и технологий (ДНиТ-V-2026) : сборник научных статей по материалам V Всероссийской (национальной) научной конференции. - Красноярск, 2026. - С. 104-109. - ISBN 9785605323549.
Аннотация:Задача о рюкзаке является одной из самых популярных разновидностей комбинаторных оптимизационных задач с середины 20 века. Будучи NP-полной, она бросает существенный вызов при разработке новых алгоритмических и эвристических решений, сегодня уже существует огромное множество работ, посвященных созданию и тестированию решений для оригинальной версии задачи. Однако помимо классической постановки задачи о рюкзаке существуют также множественные ее вариации, которые уже зачастую менее хорошо изучены. Одной из таковых является квадратичная задача о рюкзаке с многомерными ограничениями. До недавнего времени существовала всего одна посвященная ей работа, и потому изучение эффективности разных алгоритмов к данной постановке является весьма актуальным. Данная работа посвящена изучению производительности алгоритма случайного поиска при работе с указанной вариацией задачи о рюкзаке на синтетическом наборе данных, содержащем примеры с разной размерностью условий. Алгоритм случайного поиска является одним из простейших в реализации, однако он при этом содержит возможность поиска компромисса между качеством решения и скоростью работы за счет определения числа итераций генерирования случайного решения. Одной из основных целей данной работы является определение максимальных показателей качества решения, которое может предоставить алгоритм случайного поиска, находясь в границах работы в реальном времени, либо близком к нему режиме. Представленное исследование является частью проекта по поиску средств оптимизации рендер-конвейера трехмерной графики как варианта решения задачи о рюкзаке.
The knapsack problem has been one of the most popular types of combinatorial optimization problems since the mid-20th century. Today, there is already a vast amount of work devoted to creating and testing solutions for the original version of the problem. However, in addition to the classic backpack problem, there are also many variations that are often less well studied. One such variation is the quadratic backpack problem with multidimensional constraints. This work is devoted to studying the performance of the random search algorithm when working with the specified variation of the knapsack problem on a synthetic dataset containing examples with different dimensionality of conditions. The random search algorithm is one of the simplest to implement, but it also offers the possibility of finding a compromise between solution quality and speed. One of the main goals of this work is to determine the maximum quality indicators of a solution that can be provided by the random search algorithm while operating in real time or in a mode close to it. This study is part of a project to find ways to optimize the 3D graphics render pipeline as a solution to the knapsack problem.
Ключевые слова:knapsack problem, multidimensional knapsack problem, quadratic knapsack problem, random search, задача о рюкзаке, многомерная задача о рюкзаке, квадратичная задача о рюкзаке, случайный поиск
