Условием работы алгоритмов глобального логико-вероятностного вывода в алгебраической байесовской сети (АБС) является отсутствие циклов в ее вторичной структуре. Первичная структура, над которой можно построить ациклическую вторичную, называется ациклической. Цель работы — предложить алгоритм выявления ацикличности первичной структуры на основе оценки числа ребер в ее вторичной структуре без непосредственного построения вторичной структуры, а также оценка сложности
этого алгоритма. В работе сформулирован алгоритм выявления ацикличности первичной структуры на основе оценки числа ребер в минимальном графе смежности полным перебором, доказана его корректность, оценена его сложность, предложено улучшение скорости работы этого алгоритма, доказана корректность и оценено время работы улучшенного алгоритма. Также рассмотрены возможности улучшения скорости работы этого алгоритма за счет использования алгоритмов построения элементов третичной полиструктуры АБС.
алгебраические байесовские сети, вероятностные графические модели систем знаний, глобальная структура, графы смежности ацикличность первичной структуры