Я пытаюсь создать алгоритм, который найдет наиболее эффективное упорядочение для устранения узлов в небольшой байесовской сети (представленной DAG). Все узлы являются булевыми и могут принимать два возможных состояния, за исключением узлов без преемников (эти узлы должны иметь одно наблюдаемое значение; в противном случае их отсеивание равнозначно их удалению).
Мой первоначальный план состоял в том, чтобы я рекурсивно выбирал оставшуюся переменную, у которой не было оставшихся предшественников, и для каждого из ее возможных состояний распространял значение через график. Это приведет ко всем возможным топологическим порядкам.
Учитывая топологическое упорядочение, я хотел найти стоимость маргинализации.
Например, этот график:
U --> V --> W --> X --> Y --> Z
имеет только один такой порядок (U, V, W, X, Y, Z).
Мы можем разложить плотность соединений g (U, V, W, X, Y, Z) = f1 (U) f2 (V, U) f3 (W, V) f4 (X, W) f5 (Y, X) f6 (Z, Y)
Таким образом, маргинализация, соответствующая этому порядку, будет
∑ (∑ (∑ (∑ (∑ (∑ (∑ (g (W, X, Y, Z), Z), Y), X), W), V), U) =
∑ (∑ (∑ (∑ (∑ (∑ (∑ (f1 (U) f2 (V, U)) f3 (W, V) f4 (X, W) f5 (Y, X) f6 (Z, Y), Z), Y), X), W), V), U) =
Σ (f1 (U)
Σ (f2 (V, U) * * тысячу двадцать-один
Σ (f3 (W, V)
Σ (f4 (X, W)
Σ (f5 (Y, X)
Σ (f6 (Z, Y), Z) * 1025 *
, Y)
, X)
, Вт)
, V) * 1 029 *
, U)
Для этого графика U --> V можно превратить в символическую функцию V за 4 шага (все U x все V. Учитывая, что V --> W также можно превратить в символическую функцию в 4 шага. Таким образом, в целом потребуется 18 шагов (4 + 4 + 4 + 4 + 2, потому что Z имеет только одно состояние).
Вот мой вопрос: как я могу определить самое быстрое количество шагов, которое эта сумма может быть вычислена для этого заказа?
Большое спасибо за вашу помощь!