Turbal Yu. V. Permanent decomposition algorithm for the combinatorial objects generation = Алгоритм декомпозиції перманенту для генерації комбінаторних об'єктів / Yu. V. Turbal, S. V. Babych, N. E. Kunanets // Радіоелектроніка. Інформатика. Управління. - 2022. - № 4. - С. 119-125. - Бібліогр.: 15 назв. - англ.Розглянуто задачу генерування векторів, що складаються з різних представників заданої множини. Такі проблеми виникають, зокрема, в теорії складання розкладів, при плануванні зустрічей. Окремим випадком цієї задачі є задача генерування перестановок. Мета роботи - розглянути проблему з точки зору постійного та загальновідомого підходу, виходячи з концепції лексикографічного порядку. Метод. У багатьох завданнях виникає необхідність генерувати різноманітні комбінаторні об'єкти: перестановки, комбінації з повтореннями і без них, різноманітні підмножини. Розглянуто новий підхід до генерації комбінаторних об'єктів, який базується на процедурі постійної декомпозиції. Перманент будується для спеціальної матриці інцидентності. Основна ідея цього підходу полягає в включенні до процесу алгебраїчної перманентної декомпозиції за допомогою додаткової функції рядка для запису ідентифікаторів стовпців у відповідні структури даних. У цьому випадку алгебраїчний перманент не обчислюється, а отримуємо конкретний рекурсивний алгоритм генерації комбінаторного об'єкта. Проаналізовано обчислювальну складність цього алгоритму. Результати. В межах PD-підходу розглянуто задачі генерації комбінаторних об'єктів, зокрема, перестановок. Досліджено обчислювальну складність запропонованих алгоритмів у порівнянні з відомими підгодами. Розглянуто варіант програмної реалізації розроблених алгоритмів. Висновок: розглянуто новий підхід до генерації складних комбінаторних об'єктів, що грунтується на процедурі декомпозиції модифікованого перманенту матриці інцидентності за рядком із запам'ятовуванням елементів індексу. Специфіка цього підходу полягає в тому, що певні додаткові умови, що накладаються на відповідні системи різних представників, враховуються на етапі процедур декомпозиції. Досліджено складність розглянутих алгоритмів. У разі більш складних варіантів матриці інцидентності пропонується відповідна модифікація поняття перманенту і, відповідно, процедура його декомпозиції. Індекс рубрикатора НБУВ: В173.112
Рубрики:
Шифр НБУВ: Ж16683 Пошук видання у каталогах НБУВ Повний текст Наукова періодика України
Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"
|