Оптимизация логических выражений

@Markus_13 · Регистрация: 20.02.2009

Студворк — интернет-сервис помощи студентам

Собственно, интересует сабж.
Применительно к подобной задаче:
Существует набор элементов и иерархическая структура их фильтрации, к примеру 4х уровневая:
(1ая_опция=1) => (2ая_опция=1) => (3ая_опция=1) => (4ая_опция=1) => набор_элементов_1
(1ая_опция=1) => (2ая_опция=1) => (3ая_опция=1) => (4ая_опция=2) => набор_элементов_2
(1ая_опция=1) => (2ая_опция=1) => (3ая_опция=2) => (4ая_опция=1) => набор_элементов_3
(1ая_опция=1) => (2ая_опция=1) => (3ая_опция=2) => (4ая_опция=2) => набор_элементов_4
(1ая_опция=1) => (2ая_опция=2) => (3ая_опция=1) => (4ая_опция=1) => набор_элементов_5
(1ая_опция=1) => (2ая_опция=2) => (3ая_опция=1) => (4ая_опция=2) => набор_элементов_6
(1ая_опция=1) => (2ая_опция=2) => (3ая_опция=2) => (4ая_опция=1) => набор_элементов_7
...
(1ая_опция=X) => (2ая_опция=X) => (3ая_опция=X) => (4ая_опция=X) => набор_элементов_XXXX

Причем фильтрация вариативная, т.е. если не указана 4ая_опция - фильтрация должна возвращать все дочерние ключи с 3го уровня:
(1ая_опция=1) => (2ая_опция=1) => (3ая_опция=1) => (4ая_опция=null) => набор_элементов_1+набор_элементов_2
Соответственно, если не указана 3яя_опция - должны выводиться все дочерние наборы, начиная со второго уровня.

И естественно, каждый элемент может находиться в нескольких наборах одновременно.

Реализация на данный момент такая:
Для каждого элемента автоматически генерируются логические выражения отвечающие за фильтрацию этого элемента. Все корректно работает, но при этом логические выражения получаются достаточно объемные, в некоторых случаях при составлении выражения вручную - кол-во конъюнкций/дизъюнкций по сравнению с выражением, созданным автоматически, сокращается в 10-15 раз =\

Возможно ли автоматизировать подобный процесс оптимизации?
Или, возможно, есть способ решать подобные задачи совершенно другим путем?

Добавлено через 9 минут

Сообщение от Markus_13

Реализация на данный момент такая:
Для каждого элемента автоматически генерируются логические выражения отвечающие за фильтрацию этого элемента.

Подобное решение обусловлено тем, что кол-во вариантов сочетания опций в неск-ко раз превышает кол-во самих элементов =)

@Igor3D · 05.01.2013, 19:00

Непонятно в чем проблема. Псевдокод

C++
1
2
3
4
5
6
7
8
9
10
11
bool DoFilter( const Element * elem, const CFilter * flt1, const CFilter * flt2, const CFilter * flt3 = 0, const CFilter * flt4 = 0 )
{
  if (!ApplyFilter(elem, flt1)) return false;   // применяем первый фильтр, не прошел - значит false
  if (!flt2) return true;                      // если больше нет фильтров - Ок, true
 
// теперь все то же для второго
  if (!ApplyFilter(elem, flt2)) return false;   
  if (flt3) return true;           
 
и.т.д
...

@Markus_13 · 05.01.2013, 21:51 **[ТС]**

Сообщение от Igor3D

Непонятно в чем проблема.

Если непонятно - можно воздержаться от инклуда 5ти копеек =)
Код совершенно не в тему.

@Mysterious Light · 06.01.2013, 01:48

Вопрос-то от Igor3D на самом деле был не просто так задан: действительно плохо понятно, что именно нужно.

Я так понял, что имеется небольшое количество элементов, среди которых нужно выбрать некоторые по критерию. Сам критерий задаётся ещё меньшим числом фильтров, каждый принимает на каждом элементе одно из 3 значений: 1, 2 и null.
При этом на задана функция вида $https://www.cyberforum.ru/cgi-bin/latex.cgi?(f_1,f_2,\ldots,f_n)\mapsto S$ ,
где n — число фильтров, f1,f2 — значение фильтра 1 или 2, а S — некоторое множество элементов.
Вообще, тип этой функции $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^n\to 2^X$ (слева 2^n элементное множество, справа — булеан множества элементов X).

Вариант №1 без неопределённости

Если бы фильтры могли принимать только значения 1 и 2, то можно было б явно выписать эту самую таблицу из Вашего первого поста. Например, так:

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var table = [
    [1,2,3/*набор 1*/],
    [2,3,5/*набор 2*/],
    [/*набор 3*/],
    [/*набор 4*/],
    /* ... */
    [/*набор 2^n*/]
];
function applyFilters(f) { /* f — массив опций вида [опция_1,опция_2,...,опция_n] */
    var index = 0;
    for(var i=0;i<f.length;++i)
        index = 2*index + (f[i]-1);
    return table[index];
}

Вариант №1 с неопределённостью

Если также допускаем неопределенность, то тогда достаточно просто просуммировать по всем вариантам:

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var table = [...];
function applyFilters(f) { ... }
function applyFiltersCommon(f) {
    var a = 0;
    while(a<f.length && f[a]!==null) ++a;
    // если все опции определены, то перенаправляем вызов
    if(a==f.length) return applyFilters(f);
    // иначе делаем цикл по первой неопределенной опции
    // и аккумулируем результат в переменную-массив
    var result = [];
    for(f[a]=1;f[a]<=2;++f[a])
        result = result.concat(applyFiltersCommon(f));
    // можно на порядок ускорить, представляя массив в виде
    // односвязанного динамического списка
    f[a] = null;
    return result;
}

Обобщения

Впрочем, здесь возможно обобщение: пусть опции принимают значение от 1 до m. Тогда всего будет m^n вариантов, которые можно разместить в таблице, пронумеровав их от 0 до (m^n-1). Тогда метод можно переписать так:

JavaScript
1
2
3
4
5
6
function applyFilters(f) {
    var index = 0;
    for(var i=0;i<f.length;++i)
        index = m*index + (f[i]-1);
    return table[index];
}

Это представление удобно тем, что вариант неопределённости можно мыслить как новый вариант. Например, если опция может принимать 1,2 или null, то полагаем m=3 и радуемся.
Минусы этого подхода в необходимости составлять массив table.
Кстати, его можно сделать n-мерным, тогда не нужно будет index искать.

Описанные варианты хорошо работают, если m,n<5.
Я, вообще-то, хотел по исходному вопросу отписаться. Однако, в виду некоторых соображений я этого не буду делать в ближайшее время. Просмотрите, пожалуйста, варианты, предложенные выше, и скажите, что именно в таком подходе Вас не удовлетворяет.

Постановка задачи: «дано логическое высказывание, необходимо найти форму этого высказывания, кратчайшую в записи».

@Markus_13 · 06.01.2013, 11:30 **[ТС]**

Mysterious Light, спасибо, конечно, но что-то подобное я и сам мог бы сделать))

Видимо, мои социальные навыки еще хуже программерских, и никто не понял что мне нужно =\\

Попробую еще раз расписать подробней...
Представьте что у нас есть структура вроде такой:

PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
$el=array('element1','element2','element3','element4','element5',...........);
$element_sets = array(
    'option1=o1a' = array(
        'option2=o2a' = array(
            'option3=o3a' = array(
                'option4=o4a' = array(
                    $el[1],$el[3],$el[5],
                ),
                'option4=o4b' = array(
                    $el[0],$el[2],$el[1],
                ),
            ),
            'option3=o3b' = array(
                'option4=o4c' = array(
                    $el[2],$el[4],$el[6],
                ),
                'option4=o4b' = array(
                    $el[1],$el[3],$el[7],
                ),
                'option4=o4d' = array(
                    $el[5],$el[6],$el[9],
                ),
            ),
        ),
        'option2=o2b' = array(
            'option3=o3a' = array(
                'option4=o4d' = array(
                    $el[7],$el[8],$el[9],$el[4],
                ),
                'option4=o4a' = array(
                    $el[9],$el[2],
                ),
            ),
            'option3=o3d' = array(
                'option4=o4e' = array(
                    $el[3],$el[8],
                ),
            ),
        ),
        ................
    ),
    .................
);

Кол-во опций, их значения и уровень вложенности могут варьироваться. Кол-во элементов на разных уровнях тоже может варьироваться.
Причем, как я уже писал, необходимо соблюдать иерархию - т.е.:
условие

JavaScript
1
if( (option1=o1a) && (option2=o2a) && (option3=o3a) && (option4=null) )

должно являться суммой вывода от

JavaScript
1
2
    if( (option1=o1a) && (option2=o2a) && (option3=o3a) && (option4=o4a) ) 
    if( (option1=o1a) && (option2=o2a) && (option3=o3a) && (option4=o4b) )

И точно также с уровнем выше:

JavaScript
1
if( (option1=o1a) && (option2=o2a) && (option3=null) && (option4=null) )

=

JavaScript
1
2
3
4
5
6
    if( (option1=o1a) && (option2=o2a) && (option3=o3a) && (option4=o4a) ) 
    if( (option1=o1a) && (option2=o2a) && (option3=o3a) && (option4=o4b) ) 
    
    if( (option1=o1a) && (option2=o2a) && (option3=o3b) && (option4=o4c) ) 
    if( (option1=o1a) && (option2=o2a) && (option3=o3b) && (option4=o4b) ) 
    if( (option1=o1a) && (option2=o2a) && (option3=o3b) && (option4=o4d) )

-----------------------------------------------------------------------------------------
Суть в том что по подобной структуре АВТОМАТИЧЕСКИ генерируются условия вывода по каждому элементу.
К примеру по той структуре что вверху на пхп представлена, для элемента_1 будет сгенерирован подобный код:

JavaScript
1
if ( (option1=="o1a") && (option2=="")  && (option3=="")  && (option4=="") ) || ( (option1=="o1a") && (option2=="o2a")  && (option3=="")  && (option4=="") ) || ( (option1=="o1a") && (option2=="o2a")  && (option3=="o3a")  && (option4=="") ) || ( (option1=="o1a") && (option2=="o2a")  && (option3=="o3a")  && (option4=="o4a") ) || ( (option1=="o1a") && (option2=="o2a")  && (option3=="o3a")  && (option4=="o4b") ) || ( (option1=="o1a") && (option2=="o2a")  && (option3=="o3b")  && (option4=="") ) || ( (option1=="o1a") && (option2=="o2a")  && (option3=="o3b")  && (option4=="o4b") ) el_output.push(elements[1]);

Т.к. я пошел самым легким путем - результирующее логическое выражение является всего лишь суммой всех возможных сочетаний, обуславливающих вывод элемента.
Но если составить выражение вручную - мы напишем что-то вроде этого:

JavaScript
1
if( (option1=="o1a") && (option4!="o4c") && (option4!="o4d") ) el_output.push(elements[1]);

Разница, я думаю, заметна =)
И вся загвоздка собственно в возможности оптимизации сгенерированного выражения или в модернизации текущего метода генерации.

З.Ы. предлагать вывод наборов не нужно, я бы и сам это сделал, это конечно было бы проще, но необходима именно генерация выражений с привязкой на каждый элемент...

З.З.Ы. практическая сторона вопроса меня абсолютно не интересует, я прекрасно понимаю что для современных компьютеров существенной разницы между первым выражением и вторым - нету, и потери в скорости будут минимальны. Но меня интересует именно возможность автоматической генерации/оптимизации подобных логических выражений...

@Mysterious Light · 06.01.2013, 12:37

Сообщение от Markus_13

Суть в том что по подобной структуре АВТОМАТИЧЕСКИ генерируются условия вывода по каждому элементу.

Я всё ещё слабо понимаю, зачем Вам это надо.

Итак, как я понял, такая многомерная таблица (ассоциативный массив) всё-таки имеется. И на основе этого массива автоматически генерируются условия.

Первое, что приходит в голову, это сокращение формул на основе тождеств вида
$https://www.cyberforum.ru/cgi-bin/latex.cgi?xy\vee x\bar y=x \\ xy\vee xz=x(y\vee z) \\ \bar{xy}=\bar x \vee \bar y \\ \bar{x\vee y}=\bar x \bar y$
Поскольку эту самую генерацию предполагается проводить один раз, то нет причин особо следить за памятью и временем исполнения. Поэтому предлагаю использовать поиск в ширину кратчайшей формулы на графе всех формул, в котором дугами отмечены переходы по указанным выше четырем правилам, начиная от «наивной» формулы, которую Вы описали.

Я по-прежнему не понимаю, что значит соблюдение иерархии. Если из 4 опций одна не указана, то в условии фильтрации на соответствующем месте будет конъюнкция опций без одной, то есть если четвертая опция пропущена, то будет (x1 x2 x3) = (x1 x2 x3 x4) v (x1 x2 x3 -x4), где xk=«опция k приняла значение ***».
Проще было б, если опции могли бы принимать только два значения, тогда можно сопоставить значение опции и булеву величину.
Если некотороя опция допускает большее число вариантов, то принципиально мало что меняется, все изменения будут затрагивать только правила, по которым строится граф. Так сколько значений может принимать одна опция?

Идейно такой вариант подходит? Опять же, хотелось бы получить как можно более развёрнутый ответ.

@Markus_13 · 06.01.2013, 13:54 **[ТС]**

Сообщение от Mysterious Light

Если некотороя опция допускает большее число вариантов, то принципиально мало что меняется, все изменения будут затрагивать только правила, по которым строится граф. Так сколько значений может принимать одна опция?

Я же говорил что кол-во возможных значений каждой опции варьируется на разных уровнях структуры, всего возможных значений по каждой опции может быть много...

Сообщение от Mysterious Light

Первое, что приходит в голову, это сокращение формул на основе тождеств вида

Я тоже думал в этом направлении, но на скорую руку никакой толковый алгоритм не смог составить.

Мне кажется что применительно к логическим выражениям того вида, что строится у меня, целесообразно производить преобразование всех сравнений таким образом, чтобы приводить все сравнения к бинарному виду, т.е. (a=b) = x1, и далее производить анализ результата и сокращать выражение...

Но я так и не представляю пока что как можно произвести построение СДНФ формулы в автоматическом режиме =\\

@Mysterious Light · 08.01.2013, 00:27

Пусть задано число n и числа m1,m2,m3,...,mn
Также пусть задан n-мерный массив T размерности m1 x m2 x m4 x ... x mn, элементы которого — некоторые коллекции объектов множества E.
Также пусть e — некоторый элемент из E.
Очевидно, для любого набора (v1,v2,...,vn) из области определения T утверждение «e принадлежит T[v1][v2][v3]...[vn]» является либо истинным, либо ложным.
Если также у нас имеется набор (f1,f2,f3,..,fn) из области определения T, то мы задаём вопрос, какое условие накладывается на этот набор, чтоб утверждение «e принадлежит T[f1][f2][f3]...[fn]» было истинным при любом наборе. Разделение букв f и v нужно для того, чтоб не путать связные и свободные имена (а то начнётся каша в обозначениях, как в статистике, где случайная величина и её значение обозначаются одной буквой).

Дизъюнктивная нормальная форма
Первое, что приходит в голову, написать выражение типа
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\bigvee_k\bigwedge_i x_i(v_i^k)$
здесь k означает номер члена (конъюнкта), i обозначает индекс (от 1 до n), также введена специальный предикат-индикатор:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?x_i(v)=\{f_i=v\}$
который реагирует, когда опция номер i принимает значение v.

В такой форме число конъюнктов будет равно числу коллекций в таблице T, которые содержат e. Подробнее описывать не буду, как строится — понятно, что означает — тоже.

Некоррелируемые формы
Под некоррелируемостью подразумевается то, что при упрощении формулы мы не будем допускать выражения вида (f1=f2), когда сравниваются разные опции. Это допущение жизненно.
Общий вид формы формулы, которую я предлагаю рассмотреть, имеет вид
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\bigvee_k\bigwedge_i x_i(\Delta_i^k)$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?x_i(\Delta)=\{f_i\in\Delta\}$
Поскольку стоит задача найти простую формулу, введём меру простоты:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left| \bigvee_k\bigwedge_i x_i(\Delta_i^k) \right| = \sum_k \sum_i \rho_i(\Delta_i^k)$
Внешняя сумма — по конъюнктам, чем больше конъюнктов, тем сложнее выражение. Вторая сумма — по длине конъюнктов. В некотором смысле, мы хотим также уменшить и число членов в каждом конъюнкте. Более точно, мы просто хотим, чтоб конъюнкты выглядили проще. В каждом конъюнкте всегда будет ровно n членов. Тем не менее, разница может быть:

Code
1
2
(f1=1) and (f2=1) and (f3=2) // {1} {1} {2}
(f1=1 or f1=2) and (f2=2 or f2>4) and (f3=1 or f3=2 or f3=3 or f3=4 or f3=5 or f3=6) // {1,2} {2,4,5,6,...,m2} {1,2,3,4,5,6}

Поэтому введена функция, которая будет оценивать сложность каждого члена, опираясь на множество Δ.
1. Понятно, что если Δ покрывает все возможные значения, то соответствующий член конъюнкта просто можно выкинуть, он пуст.
2. Если Δ одноэлементное, то член конъюнкта имеет вид (fk=vk)
Это можно записать так:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\rho_i(\{1,2,\ldots,m_i\})=0 \\ \rho_i(\{v\})=1$
Кроме этого, можно ввести ряд неочевидных правил, на Ваше усмотрение:
3. Можно спроектировать функцию так, что $https://www.cyberforum.ru/cgi-bin/latex.cgi?\rho(\Delta)=\rho(\neg\Delta)$ , то есть мы позволяем записывать члены в отрицательной форме. Для m=6 демонстрация:

Code
1
2
f=1 or f=2 or f=5 or f=6 // {1,2,5,6}
f!=3 and f!=4 // -{3,4}

4. Можно ввести неравенства, то есть $https://www.cyberforum.ru/cgi-bin/latex.cgi?\forall v_0:\;\rho(\{v|v<v_0\})=1$

Пусть для определённости $https://www.cyberforum.ru/cgi-bin/latex.cgi?\rho_i(\Delta)=\min(|\Delta|,m_i-|\Delta|)$ , где |X| означает количество элементов в X.

Порождения
Всякую формулу в некоррелируемой форме можно представить в виде множества $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{\langle\Delta_1^k,\Delta_2^k,\ldots,\Delta_n^k\rangle\}_k$ .
Обратим внимание на следствия:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?AB\vee AC=A(B\vee C) \\ (A\to B) \to (FAG \to FBG) \\ (A \to B) \to (A \leftrightarrow A\vee B)$
Первое соотношение можно переписать так:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?x_i(\Delta_i^k)\vee x_i(\Delta_i^k')=x_i(\Delta_i^k\cup\Delta_i^k')$
Второе соотношение позволяет нам делать следующее: если мы найдём два конъюнкта, отличающихся только в одном члене с индексом i, то их мы объединяем по первому соотношению, а потом «довешиваем» остальные члены в неизменном виде (они играют роль F и G).
Третье соотношение позволяет нам после объединения двух конъюнктов сохранить их. Здесь в программе лучше всего их пометить как «избыточные».
Я настоятельно рекомендую сохранять их, потому что они позволят максимально упростить выражение. Точнее, один и тот же конъюнкт можно объединять с разными другими конъюнктами несколько раз, поэтому его не стоит выбрасывать.
При оценке сложности формулы избыточные конъюнкты, понятное дело, не следует учитывать, потому что они только помогают генерировать другие, более котороткие формы, и в любой момент могут быть выброшены.

Набросок
Стартуем с ДНФ. Сразу записываем всё в виде множества кортежей множеств. Все конъюнкты неизбыточны.
Начинаем генерировать новые формы, пока этот процесс возможен. Общее число форм конечно.
Процесс генерации будет, скорее всего, рекурсивным.
Попутно оцениваем сложность каждой новой формы, согласно введённой меры.
Когда будет определён минимум, следует восстановить форму в соответствии с правилами, на которых основывается функция ρ.

P.S. Да, знаю, много текста. Может быть, можно было б короче выразить мысль, которая, в сущности, заключается только в описании правил

Новые блоги и статьи Все статьи Все блоги /
Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025