Модификация метода построения алгоритмов комбинаторной генерации на основе применения производящих функций многих переменных и приближенных вычислений

Аннотация: Предложен модифицированный метод построения алгоритмов комбинаторной генерации на основе деревьев И/ИЛИ, который отличается от оригинального и его модификаций применением комплексного метода получения явных выражений коэффициентов производящих функций многих переменных для нахождения выражения функции мощности комбинаторного множества, в том числе определяемого несколькими параметрами. Также предложенный модифицированный метод отличается применением приближенных вычислений и двоичного поиска для поиска выбранного сына ИЛИ-узла, что позволяет снижать вычислительную сложность алгоритмов генерации по рангу. С целью апробации предложенного модифицированного метода построения алгоритмов комбинаторной генерации разработаны новые алгоритмы ранжирования и генерации по рангу для комбинаторного множества самонепересекающихся решеточных путей на плоскости. В данном случае применение двоичного поиска позволило сократить в среднем количество требуемых вычислительных операций и получить лучшее значение вычислительной сложности по сравнению с исходной версией алгоритма.

Ключевые слова: комбинаторная генерация, производящие функции многих переменных, приближенные вычисления, двоичный поиск, решеточный путь, алгоритм ранжирования, алгоритм генерации по рангу

Библиография статьи: Кручинин Д. В. Модификация метода построения алгоритмов комбинаторной генерации на основе применения производящих функций многих переменных и приближенных вычислений / Д. В. Кручинин // Доклады ТУСУР. – 2022. – Т. 25, № 1. – С. 55–60. DOI: 10.21293/1818-0442-2021-25-1-55-60