Купер [291] показал, что общая проблема вероятностного вывода в байесовских сетях без ограничений является NP-трудной, и Пол Дагум и Майк Луби [319] показали, что NP-трудной является соответствующая задача аппроксимации. Одной из серьезных проблем при использовании методов кластеризации и устранения переменной является также пространственная сложность. Применение метода определения условий выбора множества разрыва цикла, который был разработан для задач CSP в главе 5, позволяет исключить необходимость построения экспоненциально больших таблиц. В байесовской сети множеством разрыва цикла является множество вершин, позволяющих после их конкретизации свести оставшиеся вершины к полидереву, которое может быть решено с линейными затратами времени и пространства. Поиск ответа на запрос осуществляется путем суммирования по всем конкрети-зациям множества разрыва цикла, поэтому общие требования к пространству всееще остается линейными [1191]. В [323] описан рекурсивный алгоритм обусловливания, который допускает широкий выбор компромиссных методов сокращения затрат пространства/времени.

В настоящее время разработка быстрых алгоритмов аппроксимации для вероятностного вывода в байесовских сетях представляет собой очень активную научную область, которая испытывает положительное влияние со стороны статистики, компьютерных наук и физики. Способ формирования выборок с исключением представляет собой общий метод, давно известный статистикам; он был впервые применен к байесовским сетям Максом Хенрионом [648], который назвал этот метод логическим формированием выборок. Метод взвешивания с учетом правдоподобия, который был разработан Фунгом и Чангом [512], а также Шахтером и Пеотом [1387], представляет собой пример широко известного статистического метода формирования выборок с учетом важности. Результаты крупномасштабного применения метода взвешивания с учетом правдоподобия в области медицинской диагностики опубликованы в [1407]. Ченг и Друздзель [247] описали адаптивную версию метода взвешивания с учетом правдоподобия, которая действует очень успешно, даже если свидетельства имеют крайне низкое априорное правдоподобие.