Разложение Шеннона по таблице истинности

Мое разложение Шеннона получилось ну сильно неоптимальным, можно было легче сделать через манипуляции с таблицей истинности.
Разложение Шеннона-способ представление функции с помощью подфункций размером уже от (n-1) переменных.
Алгоритм (он у нас для n разбиений, все переменные для разбиения находятся в очереди):

1. Сначала мы берем СДНФ и разбиваем ее на конъюнкции
2. Эти конъюнкции уже разбиваем на те, которые относятся к первой переменной разбиения, которая равна в таблице истинности единице, и те которым соответсвует 0.
3. Запускаем процедуру декомпозиции

Сама идея процедуры очень проста, но реализовано все очень прожорливо, через вектора:

queue <int> variables - очередь, которая хранит в себе все переменные, которые мы выбрали для разбиения.

Мы разбиваем на конъюнкции , где xi=1 (plus) и xi=0 (minus) и смотрим 3 случая:

1. Все вектора конъюнкций не пусты
2. plus вектор пуст
3. minus вектор пуст

В зависимости от этих случаев, мы вызываем рекурсивно снова функцию но уже для конъюнкций для новой переменной разложения (которую мы берем из очереди). Если следующей переменной для разложения нету возвращается окончательный ответ.

В общем на blogspote ограничение на 200 символов, так что по просьбе могу скинуть на хостинг проект.

Read More