Построение СКНФ СДНФ

@bodya__ · Регистрация: 06.11.2020

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

Здравствуйте!
Программа заключается в том, чтобы построить СКНФ/СДНФ огромного булевого выражения.
Так как пользователю проблематично руками написать выражение в несколько тысяч знаков был сделан генератор, который по заранее известному количеству переменных и членов в СКНФ/СДНФ "разворачивает" выражение в какое-то большое случайным образом. Далее это выражение подается в функцию построения СКНФ/СДНФ и мы должны получить те же члены, по которым и строилось выражение.
Теперь к проблеме. Проблема заключается в том, что функция легко считает выражения меньше 300 символов, секунд за 20 считает выражение 400 символов, за пару минут считает выражение в 500 символов, а далее подсчет затягивается на часы, терпения посмотреть досчитает ли до конца не хватило, но думаю что досчитает.
Можно ли как-то оптимизировать функцию построения СКНФ/СДНФ и с чем может быть связан такой рост во времени подсчета?
Ниже прикрепляю код функции "разворачивания"(formulaGeneratorSKNF) которая принимает в качестве аргументов количество членов в СКНФ/СДНФ, количество переменных и количество отрицаний и функции построения СКНФ/СДНФ по этому выражению(sknfSearch).

C++

//возвращает список всех допустимых операндов в зависимости от оператора и желаемого значения
vector<pair<int, int>> getSuitableOperands(char op, int wanted) {
    vector<pair<int, int>> ans;
    switch (op) {
    case '*': {
        if (wanted == 1) {
            ans.push_back(make_pair(1, 1));
        }
        else {
            ans.push_back(make_pair(0, 0));
            ans.push_back(make_pair(1, 0));
            ans.push_back(make_pair(0, 1));
        }
    }break;
 
    case '+': {
        if (wanted == 1) {
            ans.push_back(make_pair(1, 0));
            ans.push_back(make_pair(0, 1));
            ans.push_back(make_pair(1, 1));
        }
        else {
            ans.push_back(make_pair(0, 0));
        }
    }break;
 
    case '^': {
        if (wanted == 1) {
            ans.push_back(make_pair(0, 1));
            ans.push_back(make_pair(1, 0));
        }
        else {
            ans.push_back(make_pair(1, 1));
            ans.push_back(make_pair(0, 0));
        }
    }break;
 
    case '!': {
        if (wanted == 1) {
            ans.push_back(make_pair(-1, 0));
        }
        else {
            ans.push_back(make_pair(-1, 1));
        }
    }break;
 
    case '=': {
        if (wanted == 1) {
            ans.push_back(make_pair(0, 0));
            ans.push_back(make_pair(1, 1));
        }
        else {
            ans.push_back(make_pair(0, 1));
            ans.push_back(make_pair(1, 0));
        }
    }break;
 
    case '>': {
        if (wanted == 1) {
            ans.push_back(make_pair(0, 1));
            ans.push_back(make_pair(0, 0));
            ans.push_back(make_pair(1, 1));
        }
        else {
            ans.push_back(make_pair(1, 0));
        }
    }break;
    }
    return ans;
}
 
 
 
 
 
void vecClean(vector<vector<string>>& vec)
{
   
    vector<vector<string>> ans;
    for (int i = 0; i < vec.size();i++) {
        if (vec[i].size() != 0) {
            ans.push_back(vec[i]);
        }
    }
    vec.swap(ans);
}
 
 
bool isOperator(char symbol) {
    int arraySize = sizeof(priorityArray)/sizeof(priorityArray[0]);
 
    for (int i = 0; i < arraySize; i++) {
        if (symbol == priorityArray[i])
            return true;
    }
    return false;
}
 
vector<vector<string>> sknfSearch(int wantedValue, vector<vector<string>> vec, node* node) {
    
    if (isOperator(node->value[0])) {
        //если попали в оператор
        vector<pair<int, int>> pairs = getSuitableOperands(node->value[0], wantedValue);
        
        vector<vector<string>> answer;
 
        if (node->value[0] == '!') {
            answer = sknfSearch(pairs[0].second, vec, node->right);
        }
        else {
            for (int i = 0; i < pairs.size(); ++i) {
                vector<vector<string>> curResult = sknfSearch(pairs[i].second, sknfSearch(pairs[i].first, vec, node->left), node->right);
                answer.insert(answer.end(), curResult.begin(), curResult.end());
            }
        }
        return answer;
 
    }
    else {
        //если попали в переменную
        string valueToPost = node->value;
 
        if (wantedValue == 0)
            valueToPost[0] = 'A';
 
        //если вектор пустой, просто добавим туда одну комбинацию из одной переменной
        if (vec.size() == 0) {
            vector<string> tempVec;
 
            tempVec.push_back(valueToPost);
            vec.push_back(tempVec);
 
            return vec;
 
        }
        else {
            //внешний цикл по комбинациям
            stringstream curVarNumberContainer(node->value.substr(1, node->value.size() - 1));
            int curVarNumber;
            curVarNumberContainer >> curVarNumber;
 
            for (int i = 0; i < vec.size(); ++i) {
                if (vec[i].size() == 0)
                    continue;
                //внутренний цикл по вхождениям переменной в комбинацию
                bool needToPost = true;
                for (int j = 0; j < vec[i].size(); ++j) {
                    stringstream varInVecContainer(vec[i][j].substr(1, vec[i][j].size() - 1));
                    int varInVec;
                    varInVecContainer >> varInVec;
 
                    //если нашли переменную с номером больше текущей, вставляем сюда.
                    if (curVarNumber < varInVec) {
                        vec[i].insert(vec[i].begin() + j, valueToPost);
                        needToPost = false;
                        break;
                    }
                    //если наткнулись на эту же переменную, нужно проверить, в каком виде она входит
                    else if (curVarNumber == varInVec) {
                        
                        //если она уже входит с другим знаком - комбинация дефектная, в мусор
                        if (valueToPost[0] != vec[i][j][0]) {
                            vec[i].clear(); 
                        }
                        needToPost = false;
                        break;
                    }
                }
                if (needToPost)
                    vec[i].push_back(valueToPost);
            }
 
            //очищаем вектор от всех пустых комбинаций.(освобождаем очень много памяти)
            vecClean(vec);
            //если вектор после очистки стал пустым, добавим один пустой элемент. Это нужно для разграничения пустых изначально и "опустошённых" векторов.
            if (vec.empty()) {
                vector<string> temp;
                vec.push_back(temp);
            }
            return vec;
        }
    }
}
//функция возвращает формулу, являющуюся тождественным нулем или единицей.
string complicateConstant(int numOfVars, int numOfVarsTotal, bool constFlag) {
    string answer;
 
    switch (numOfVars) {
    case 3: {
        string variantsList[2] = { "(!(1^((!2+3)*!2+1)>3)*3)", "(!(((3+2*1)^!(3+2*1))>!(3*!2*2)))" };
 
        string var1 = "a" + to_string(rand() % numOfVarsTotal + 1);
        string var2 = "a" + to_string(rand() % numOfVarsTotal + 1);
        string var3 = "a" + to_string(rand() % numOfVarsTotal + 1);
 
        int variant = rand() % 2;
 
        string buf = variantsList[variant];
        for (int i = 0; i < buf.size(); i++) {
            if (buf[i] > 48 && buf[i] < 58) {
                switch (buf[i]) {
                case '1': answer.append(var1); break;
                case '2': answer.append(var2); break;
                case '3': answer.append(var3); break;
                }
                continue;
            }
            answer.append(string(1, buf[i]));
        }
 
        if (constFlag) {
            answer = "!" + answer;
        }
        return answer;
    }break;
    
    case 4: {
        string variantsList[1] = { "(1*3*(3*((1^(2+3^4))^2*4)>!3)*2*3*!2)" };
        string var1 = "a" + to_string(rand() % numOfVarsTotal + 1);
        string var2 = "a" + to_string(rand() % numOfVarsTotal + 1);
        string var3 = "a" + to_string(rand() % numOfVarsTotal + 1);
        string var4 = "a" + to_string(rand() % numOfVarsTotal + 1);
        int variant = 0;
        string buf = variantsList[variant];
 
        for (int i = 0; i < buf.size(); i++) {
            if (buf[i] > 48 && buf[i] < 58) {
                switch (buf[i]) {
                case '1': answer.append(var1); break;
                case '2': answer.append(var2); break;
                case '3': answer.append(var3); break;
                case '4': answer.append(var4); break;
                }
                continue;
            }
            answer.append(string(1, buf[i]));
        }
        if (constFlag) {
            answer = "!" + answer;
        }
        return answer;
    }break;
    }
}
 
 
bool areMembersEqual(vector<string> a, vector<string> b) {
    bool answer = true;
    int memberLength = a.size();
    for (int i = 0; i < memberLength; i++) {
        if (a[i] != b[i]) {
            answer = false;
        }
    }
    return answer;
}
 
 
pair<vector<vector<string>>, string> formulaGeneratorSKNF(int ceilNumOfMembers, int numOfVars, int numOfNegations) {
 
 
    //проверки перед генерацией
    if (ceilNumOfMembers > pow(2, numOfVars)) {
        throw invalid_argument("Количество членов больше возможного");
    }
 
    if (numOfNegations > ceilNumOfMembers * numOfVars) {
        throw invalid_argument("Количество отрицаний не может быть больше суммарного количества переменных в СКНФ");
    }
 
 
    //в этот вектор поместим будущую скнф
    vector<vector<string>> sknf;
 
    //количество уже установленных знаков отрицания
    int negationsSet = 0; 
 
 
    for (int i = 0; i < ceilNumOfMembers; i++) {
        vector<string> member;
        string negation = "!";
        for (int j = 1; j <= numOfVars; j++) {
 
            member.push_back("a" + to_string(j));
            int needNegation = rand() % 5;
            if (needNegation == 1 && negationsSet < numOfNegations) {
                member[member.size() - 1].insert(0, 1, '!');
                negationsSet += 1;
            }
        }
        sknf.push_back(member);
    }
 
    while (negationsSet < numOfNegations) {
        bool isReady = false;
 
        for (int i = 0; i < sknf.size(); i++) {
 
            for (int j = 0; j < sknf[i].size(); j++) {
                if (sknf[i][j][0] != '!' && (rand() % 2)) {
                    negationsSet += 1;
                    if (negationsSet == numOfNegations) {
                        isReady = true;
                        break;
                    }
                    sknf[i][j].insert(0,1, '!');
                }
            }
            if (isReady)
                break;
        }
    } 
    //теперь нужно удалить все дубликаты из скнф чтобы предоставить её на выход. А использовать можно и с дубликатами
    vector<vector<string>> standartizedSKNF;
 
    for (int i = 0; i < sknf.size(); i++) {
        bool needToAdd = true;
        for (int j = 0; j < standartizedSKNF.size(); j++) {
            if (areMembersEqual(sknf[i], standartizedSKNF[j])) {
                needToAdd = false;
            }
        }
        if (needToAdd) {
            standartizedSKNF.push_back(sknf[i]);
        }
    }
    
 
    
 
 
    //теперь усложним
    //усложнение на уровне переменных
    for (int i = 0; i < sknf.size();i++) {
 
        for (int j = 0; j < sknf[i].size(); j++) {
 
            int needComplicate = rand() % 4;
 
            if (needComplicate == 1) {
 
                int zeroOrOne = rand() % 2;
                if (zeroOrOne == 0) {
                    sknf[i][j] += "+" + complicateConstant(3 + rand() % 2, numOfVars, 0);
                }
                else {
                    sknf[i][j] += "*" + complicateConstant(3 + rand() % 2, numOfVars, 1);
                }
                sknf[i][j] = "(" + sknf[i][j] + ")";
            }
        }
    }
 
 
    /*string tempAnswer;
    for (int i = 0; i < sknf.size(); i++) {
        tempAnswer += "(";
        for (int j = 0; j < sknf[i].size(); j++) {
            tempAnswer += sknf[i][j] + "+";
        }
        tempAnswer.pop_back();
        tempAnswer += ")*";
    }
    tempAnswer.pop_back();
    return make_pair(standartizedSKNF, tempAnswer);*/
 
    //усложнение на уровне члена
 
    for (int i = 0; i < sknf.size(); i++) {
        vector<string> buf;
 
        random_device rd;
        default_random_engine rng(rd());
 
        shuffle(sknf[i].begin(), sknf[i].end(), rng);
        int numOfIterations = (sknf[i].size() - rand() % sknf[i].size()) / 2;
 
        for (int j = 0; j < numOfIterations; j++) {
            string newMember;
            int lastIndex = sknf[i].size() - 1;
            //x+y=x^y^x*y мб скобки по краям не нужны
            newMember = "(" + sknf[i][0] + "^" + sknf[i][lastIndex] + "^" + sknf[i][0] + "*" + sknf[i][lastIndex] + ")";
            buf.push_back(newMember);
            sknf[i].pop_back();
            sknf[i].erase(sknf[i].begin());
        }
        buf.insert(buf.end(), sknf[i].begin(), sknf[i].end());
        sknf[i] = buf;
    }
 
 
    //теперь усложнённые члены соединим в строки
    vector <string> compMembSKNF;
    for (int i = 0; i < sknf.size(); i++) {
        string buf = "(";
        for (int j = 0; j < sknf[i].size(); j++) {
            buf.append(sknf[i][j]);
            buf += "+";
        }
        buf[buf.size() - 1] = ')';
        compMembSKNF.push_back(buf);
    }
    //теперь проведём усложнение на уровне формулы. Между членами стоит *
 
    random_device rd;
    default_random_engine rng(rd());
 
    shuffle(compMembSKNF.begin(), compMembSKNF.end(), rng);
    int numOfIterations = (compMembSKNF.size() - rand() % compMembSKNF.size()) / 2;
 
    vector<string> abobus;
    for (int i = 0; i < numOfIterations; i++) {
        string buf;
        int lastIndex = compMembSKNF.size() - 1;
        buf = "((" + compMembSKNF[0] + "+" + compMembSKNF[lastIndex] + ")*(!" + compMembSKNF[0] + "+" + compMembSKNF[lastIndex] + ")*(" + compMembSKNF[0] + "+!" + compMembSKNF[lastIndex] + "))";
        abobus.push_back(buf);
        compMembSKNF.pop_back();
        compMembSKNF.erase(compMembSKNF.begin());
    }
    ///!!!!!!вставил
    abobus.insert(abobus.end(), compMembSKNF.begin(), compMembSKNF.end());
 
 
    string answer;
    for (int i = 0; i < abobus.size(); i++) {
        answer.append(abobus[i]);
        answer += "*";
    }
    answer.pop_back();
    return make_pair(standartizedSKNF, answer);
}
 
int main()
{
    srand(time(NULL));
    //string expression = "a1*(a1+!a2+a3)*(!a1+a3)";
    //cin >> expression;
 
    pair<vector<vector<string>>, string> answer = formulaGeneratorSKNF(3 ,10, 13);
 
 
    //////////////////////
    //return 0;
    //////////////////////
    vector<vector<string>> stash;
    //vector<string> buf{"n"};
    //stash.push_back(buf);
    node* root = new node;
    string calculate;
    cin >> calculate;
    /*calculate = answer.second;
    cout << "Formula:\n";
    cout << calculate << endl;
    cout << "Wanted answer:" << endl;
    for (int i = 0; i < answer.first.size(); i++) {
        for (int j = 0; j < answer.first[i].size(); j++) {
            cout << answer.first[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    cout << "Formula length:" << calculate.length() << endl;*/
 
 
    //inOrderTravers(root);
    cout << "Are braces correct? " << checkBraces(calculate) << endl;
    cout << "SKNF search began." << endl;
    addnode(calculate, root);
    cout << "Tree ready." << endl;
    std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
     stash = sknfSearch(0, stash, root);
    std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
    cout << "Time difference = " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << "[ms]" << std::endl;
    for (int i = 0; i < stash.size(); i++) {
        if (!stash[i].empty()) {
            for (int j = 0; j < stash[i].size(); j++) {
                string buf;
                if (stash[i][j][0] == 'a') {
                    buf += "!a";
                }
                else buf += 'a';
                buf += stash[i][j].substr(1, stash[i][j].size() - 1);
                cout << buf << " ";
            }
            cout << endl;
        }
    }
    return 0;
}

@bodya__ · 08.05.2022, 21:21 **[ТС]**

Скрины работы программы, также бывает такое, что спустя пару часов нагрузка на ЦП становится 0%,возможно это на что-то намекнет.

Новые блоги и статьи
NoSQL базы данных: что это такое и какие существуют bytestream 22.01.2025 В современную эпоху цифровой трансформации объемы данных растут экспоненциально, создавая новые вызовы для традиционных систем управления базами данных. NoSQL (Not Only SQL) представляет собой. . .	Обновление исследования от команды MCM (январь 2025 г.) Programma_Boinc 22.01.2025 Обновление исследования от команды MCM (январь 2025 г. ) Мы продолжаем изучать молекулярные сигнатуры, связанные с раком легких, с текущим фокусом на GCM1, факторе транскрипции, участвующем в. . .	Как работать с Kafka в Go (Golang) bytestream 22.01.2025 Apache Kafka представляет собой распределенную платформу потоковой передачи данных, которая произвела революцию в области обработки событий и интеграции микросервисов. Эта система, изначально. . .	Как использовать RabbitMQ в Go (Golang) bytestream 22.01.2025 RabbitMQ представляет собой надежный и широко используемый брокер сообщений, который играет ключевую роль в построении современных распределенных систем и микросервисной архитектуры. В основе работы. . .	Как преобразовать список списков в простой список в Python bytestream 22.01.2025 При работе с Python разработчики часто сталкиваются с необходимостью обработки сложных структур данных, среди которых особое место занимают вложенные списки. Эти структуры представляют собой списки,. . .	Что такое GUID / UUID и как их создать bytestream 22.01.2025 В мире разработки программного обеспечения существует постоянная потребность в уникальной идентификации объектов, записей и ресурсов. Эта задача становится особенно актуальной в распределенных. . .
Как добавить пустую директорию в репозиторий Git bytestream 22.01.2025 При работе с системой контроля версий Git разработчики часто сталкиваются с ситуацией, когда необходимо сохранить пустую директорию в репозитории. Данная задача может показаться простой на первый. . .	Как валидировать адрес email в JavaScript bytestream 22.01.2025 JavaScript, как основной язык веб-разработки, предоставляет разработчикам множество инструментов для реализации эффективной валидации email-адресов. От простых встроенных решений до сложных. . .	Как заменить все вхождения подстроки в JavaScript bytestream 22.01.2025 Строки в JavaScript представляют собой неизменяемые последовательности символов, что делает их обработку особенно интересной с точки зрения оптимизации и выбора правильного подхода к решению задач. . . .	Управление версиями пакетов в Node.js. В чем разница между тильдой (~) и кареткой (^) в package.json bytestream 22.01.2025 В современной разработке программного обеспечения управление версиями пакетов играет ключевую роль в обеспечении стабильности и надежности проектов. Node. js, как одна из самых популярных платформ для. . .	Аутентификация на сайте с помощью формы bytestream 21.01.2025 В современном цифровом мире безопасная аутентификация становится краеугольным камнем защиты веб-приложений и пользовательских данных. Каждый день миллионы людей используют различные онлайн-сервисы,. . .	Как получить индекс в цикле for в Python bytestream 21.01.2025 При работе с коллекциями данных в Python часто возникает необходимость не только получить доступ к элементам последовательности, но и знать их позицию в процессе итерации. Индексация в циклах. . .

@bodya__ 0 / 0 / 0 Регистрация: 06.11.2020 Сообщений: 4
	08.05.2022, 21:21 [ТС]	2
	Скрины работы программы, также бывает такое, что спустя пару часов нагрузка на ЦП становится 0%,возможно это на что-то намекнет. Миниатюры 0

Опции темы