Open AccessО заполнении растущих деревьев источником, находящемся в корне
Author(s) -
Владимир Владимирович Орлов
Publication year - 2019
Publication title -
vestnik voronežskogo gosudarstvennogo universiteta. seriâ sistemnyj analiz i informacionnye tehnologii
Language(s) - Russian
Resource type - Journals
ISSN - 1995-5499
DOI - 10.17308/sait.2019.3/1306
Subject(s) - psychology
В работе рассмотрена оптимизационная задача о заполнении растущих деревьев источником, находящемся в корне. Построены алгоритмы работы этого источника по заполнению графа минимизирующие время заполнения корневого дерева. Полностью рассмотрен случай, когда количество дуг, исходящих из корня, не превышает 3-х, а мощность источника не превосходит 2. Затем рассмотрены некоторые более общие случаи, когда мощность источника и количество корневых поддеревьев произвольны. Сформулированы и доказаны теоремы о существовании оптимальных параллельных стратегий заполнения дерева для некоторых общих случаев и описаны сами оптимальные стратегии. Предложено улучшение построенного алгоритма заполнения дерева за счёт уменьшения количества переключений мощности источника между корневыми поддеревьями. Для всех результатов приведены иллюстрирующие примеры.