Ітераційні алгоритми компонування в конструкціях мультимедіа

Abstract

UA: На основі теоретичного узагальнення і робіт у галузі алгоритмізації типових задач конструкторського проектування в автоматизованих системах розроблено ітераційний алгоритм компонування елементів у конструкціях мультимедіа. Як формальну математичну модель використано теорію графів, де кожному конструктивному елементу схеми відповідає вершина, а електричним зв'язкам – ребра графа. Все це дає змогу абстрагуватися від конкретних електричних схем і переходити до їхніх математичних моделей – графів, розробляти ефективні методи пошуку оптимальних конструктивних рішень. RU: На основе теоретического обобщения и работ в области алгоритмизации типовых задач конструкторского проектирования в автоматизированных системах разработан итерационный алгоритм компоновки элементов в конструкциях мультимедиа. В качестве формальной математической модели использована теория графов, где каждому конструктивному элементу схемы соответствует вершина, а электрическим связям – ребра графа. Все это позволяет абстрагироваться от конкретных электрических схем и переходить к их математическим моделям – графам, разрабатывать эффективные методы поиска оптимальных конструктивных решений. EN: On the basis of theoretical generalization and work in the field of algorithmization of typical design engineering problems in automated systems, the authors have developed an iterative algorithm for the layout of elements in multimedia designs. As a formal mathematical model, graph theory was used, where each structural element of the scheme corresponds to a vertex, and to electrical connections - edges of the graph. All this allows us to abstract away from specific electrical circuits and move on to their mathematical models — graphs — to develop effective methods for finding optimal design solutions. The task of the iterative layout algorithm is to select some initial breakdown of the graph with subsequent permutations of vertices or groups from one subgraph to another in order to minimize the number of external edges or maximize the number of internal edges. Analyzing the obtained results, it can be said that the layout algorithms provide a high quality of breaking the graph into subgraphs satisfying the requirements of a minimum of external links, but they require a lot of time than sequential algorithms. Improving the accuracy of the solution is achieved due to a significant complication of the algorithm, which consists in rearranging groups of vertices of the graph. To reduce the iteration time, you should use consistent methods of subgraph formation, as well as group permutations of pairs of vertices that do not intersect each other.