Статья

Название статьи АЛГОРИТМ РАЗБИЕНИЯ МНОЖЕСТВА ПО ЕГО НОМЕРУ НА СОВОКУПНОСТЬ РАВНОМОЩНЫХ ПОДМНОЖЕСТВ
Автор В. М. Глушань, А. В. Зубрицкий
Рубрика РАЗДЕЛ I. АВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯ
Месяц, год 04, 2018
Индекс УДК 004.021
DOI
Аннотация Представлены результаты разработки алгоритма формирования (r, n)-разбиений по их номерам в лексикографической последовательности всех возможных комбинаций. На сегодняшний день существуют различные задачи комбинаторной оптимизации, для которых комбинаторное соединение типа (r, n)-разбиения может являться оптимальным решением. Теоретически оптимальное решение можно найти полным перебором всех (r, n) -разбиений, но количество возможных вариантов экспоненциально растет с увеличением числа элементов. Следовательно, для задач большой размерности необходимо сократить время вычислений, то есть сократить число возможных решений или организовать параллельный вычислительный процесс. В статье приведено обоснование формулы, позволяющей вычислить точное количество всех возможных неповторяющихся (r, n)-разбиений. Опираясь на данную формулу, предложен алгоритм построения разбиений по заданному номеру. Он позволяет проанализировать область решений и использовать методы случайного поиска решений. Работа алгоритма рассмотрена на примере. Разработан лексикографический алгоритм построения (r, n)-разбиений, который является модифицированной комбинацией двух алгоритмов: предложенного ранее рекурсивно-лексикографического алгоритма и алгоритма построения разбиений по заданному номеру. Он предназначен для решения задач оптимизации на комбинаторных объектах с сужаемыми областями поиска для тех случаев, когда мы заранее можем предсказать области оптимальных решений. Таким образом, алгоритм позволяет использовать частичный перебор вместо полного, то есть проводить исследования перспективных областей на наличие оптимального или близкого к оптимальному решения. Данный алгоритм, позволяет решать задачи большей мощности разбиваемого множества, чем рекурсивно-лексикографический алгоритм. Используя приведенную формулу для подсчета числа разбиений, можно разбить область решений на необходимое число подобластей и для каждой из них параллельно использовать предложенный алгоритм, реализовав таким образом параллельный вычислительный процесс.

Скачать в PDF

Ключевые слова Множества; комбинаторное множество; лексикографическая последовательность; оптимизация.
Библиографический список 1. Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации: проблемы, методы решения, исследования. – Киев: Наук. Думка, 2003. – 264 с.
2. Семенова Н.В, Колечкина Л.М. Векторные задачи дискретной оптимизации на комбинаторных множествах: методы исследования и решения: монография. – Киев: Наукова думка, 2009. – 266 с.
3. Гладков Л.А., Гладкова Н.В., Бричеева Ю.В. Решение задачи компоновки схем ЭВА на основе выделения клик // Труды конгресса по интеллектуальным системам и информационным технологиям «IS– IT’13». Научное издание в 4-х т. T. 3. – М.: Физматлит, 2013. – C. 151-153.
4. Гладков Л.А., Шкурко В.А. Решение задачи разбиения графа на подграфы на основе генетического алгоритма // Труды конгресса по интеллектуальным системам и информационным технологиям «IS – IT’14». Научное издание в 4-х т. T. 3. – М.: Физматлит, 2014. – C. 142-146.
5. Курейчик В.М., Кажаров А.А. Роевой интеллект в решении графовых задач // Труды Международной конференции по мягким вычислениям и измерениям (SCM'2013).
– СПб.: 2013. – C. 31-34.
6. Глушань В. М., Лаврик П. В. Распределенные САПР. Архитектура и возможности: монография. – Старый Оскол: ТНТ, 2014. – 188 c.
7. Тест и обзор: Intel Core i7-4770K и Core i5-4670K – новое поколение Haswell. – М., 2013. – Режим достпа: http://www.hardwareluxx.ru/index.php/artikel/hardware/prozessoren/26018-haswell-test-intel-core-i7-4770k-core-i5.html, свободный.
8. Горбатов В.А Основы дискретной математики: учеб. пособие для студентов вузов. – М.: Высш. шк., 1986. – 311 с.
9. Растригин Л.А. Теория и применение случайного поиска. – Рига: Зинатне, 1969. – 309 с.
10. Щербина О.А. Метаэвристические алгоритмы для задач комбинаторной оптимизации (обзор) // Таврический вестник информатики и математики. – 2014. – № 1 (24). – С.56-71.
11. Воеводин В.В., Воеводин Вл. В. Параллельные вычисления. – СПб.: БХВ-Петербург, 2004. – 608 с.
12. Воеводин Вл.В. Распределенная обработка данных // Вторая Сибирская школа-семинар по параллельным вычислениям / под ред. проф. А.В. Старченко. – Томск: Изд-во Том. ун-та, 2004. – 108 c.
13. Закон Амдала. – URL:https://dic.academic.ru/dic.nsf/ruwiki/433588.
14. Закон Амдала и будущее многоядерных процессоров. – URL:https://www.osp.ru/os/ 2009/04/9288815.
15. Глушань В.М., Лаврик П.В. Ограничение быстродействия вычислительных систем в результате совмещения закона Амдала и гипотезы Минского // Труды Конгресса по интеллектуальным системам и информационным технологиям «IS-IT’13». Научное издание в 4-х т. Т. 1. – М.: Физматлит, 2013. – С. 129-137.
16. Липский В. Комбинаторика для программистов: пер. с польск. – М.: Мир, 1988. – 213 с.
17. Курейчик В.М, Глушань В.М., Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. – М.: Радио и связь, 1990. – 216 с.
18. Герасимов В.А. Генерация случайных сочетаний. Генерация сочетаний по его порядковому номеру // RSDN Magasine. – 2010. – № 3.
19. Дубинин И.С., Арапов С.Ю., Тягунов А.Г. Рациональный метод генерации сочетаний для параллельных вычислений в некоторых комбинаторных задачах // Международная конференция студентов, аспирантов и молодых ученых "Информационные технологии, телекоммуникации и системы управления": Сб. докладов. – Екатеринбург: УрФУ, 2015.
– С. 174-178.
20. Тимошевская Н.Е. О нумерации перестановок и сочетаний для организации параллельных вычислений в задачах проектирования вычислительных систем // Известия Томского политехнического университета. – 2004. – Т. 307, № 6. – С. 18-20.
21. Глушань В.М., Зубрицкий А.В. Теоретическое обоснование алгоритма формирования упорядоченных разбиений с равномощными бесповторными выборками // Труды Конгресса по интеллектуальным системам и информационным технологиям «IS&IT'17». Научное издание в 3-х т. Т.2. – Таганрог: Изд-во Ступина С.А. 2017, – С. 104-112.

Comments are closed.