Tinc aquest codi en C++. Indica amb un comentari a sobre d'una funció si ha estat…
- User
Tinc aquest codi en C++. Indica amb un comentari a sobre d'una funció si ha estat modificada. També si es crea una variable global nova. El codi és aquest: "#include #include <stdlib.h> #include #include using namespace std;
#define UNDEF -1 #define TRUE 1 #define FALSE 0
uint numVars; uint numClauses; vector<vector > clauses; vector model; vector modelStack; uint indexOfNextLitToPropagate; uint decisionLevel;
void readClauses( ){ // Skip comments char c = cin.get(); while (c == 'c') { while (c != '\n') c = cin.get(); c = cin.get(); }
// Read "cnf numVars numClauses" string aux; cin >> aux >> numVars >> numClauses; clauses.resize(numClauses);
// Read clauses for (uint i = 0; i < numClauses; ++i) { int lit; while (cin >> lit and lit != 0) clauses[i].push_back(lit); }
}int currentValueInModel(int lit){ if (lit >= 0) return model[lit]; else { if (model[-lit] == UNDEF) return UNDEF; else return 1 - model[-lit]; } }
void setLiteralToTrue(int lit){ modelStack.push_back(lit); if (lit > 0) model[lit] = TRUE; else model[-lit] = FALSE; }
bool propagateGivesConflict ( ) { while ( indexOfNextLitToPropagate < modelStack.size() ) { ++indexOfNextLitToPropagate; for (uint i = 0; i < numClauses; ++i) { bool someLitTrue = false; int numUndefs = 0; int lastLitUndef = 0; for (uint k = 0; not someLitTrue and k < clauses[i].size(); ++k){ int val = currentValueInModel(clauses[i][k]); if (val == TRUE) someLitTrue = true; else if (val == UNDEF){ ++numUndefs; lastLitUndef = clauses[i][k]; } } if (not someLitTrue and numUndefs == 0) return true; // conflict! all lits false else if (not someLitTrue and numUndefs == 1) setLiteralToTrue(lastLitUndef); }
} return false; }void backtrack(){ uint i = modelStack.size() -1; int lit = 0; while (modelStack[i] != 0){ // 0 is the DL mark lit = modelStack[i]; model[abs(lit)] = UNDEF; modelStack.pop_back(); --i; } // at this point, lit is the last decision modelStack.pop_back(); // remove the DL mark --decisionLevel; indexOfNextLitToPropagate = modelStack.size(); setLiteralToTrue(-lit); // reverse last decision }
// Heuristic for finding the next decision literal: int getNextDecisionLiteral(){ for (uint i = 1; i <= numVars; ++i) // stupid heuristic: if (model[i] == UNDEF) return i; // returns first UNDEF var, positively return 0; // reurns 0 when all literals are defined }
void checkmodel(){ for (uint i = 0; i < numClauses; ++i){ bool someTrue = false; for (uint j = 0; not someTrue and j < clauses[i].size(); ++j) someTrue = (currentValueInModel(clauses[i][j]) == TRUE); if (not someTrue) { cout << "Error in model, clause is not satisfied:"; for (uint j = 0; j < clauses[i].size(); ++j) cout << clauses[i][j] << " "; cout << endl; exit(1); } }
}int main(){ readClauses(); // reads numVars, numClauses and clauses model.resize(numVars+1,UNDEF); indexOfNextLitToPropagate = 0;
decisionLevel = 0;// Take care of initial unit clauses, if any for (uint i = 0; i < numClauses; ++i) if (clauses[i].size() == 1) { int lit = clauses[i][0]; int val = currentValueInModel(lit); if (val == FALSE) {cout << "UNSATISFIABLE" << endl; return 10;} else if (val == UNDEF) setLiteralToTrue(lit); }
// DPLL algorithm while (true) { while ( propagateGivesConflict() ) { if ( decisionLevel == 0) { cout << "UNSATISFIABLE" << endl; return 10; } backtrack(); } int decisionLit = getNextDecisionLiteral(); if (decisionLit == 0) { checkmodel(); cout << "SATISFIABLE" << endl; return 20; } // start new decision level: modelStack.push_back(0); // push mark indicating new DL ++indexOfNextLitToPropagate; ++decisionLevel; setLiteralToTrue(decisionLit); // now push decisionLit on top of the mark } }
". Segueix aquestes instruccions: Per a aconseguir això, millora l’heurística de decisió i la velocitat de propagació:- Propagació. A cada volta del bucle de propagateGivesConflict, cal propagar que modelStack[indexOfNextLiteralToPropagate] s’ha tornat cert. Per fer-ho, podeu fer servir occur lists: per cada literal l, tenim una llista occurList[l] que conté els índexs de les clàusules on apareix l. Quan cal propagar que un literal l és cert, el que fem és visitar les clàusules de occurList[-l] i mirem si n’hi ha cap que s’hagi tornat falsa (conflicte!) o unitària (propagació!).
- Heurística de decisió. a. Tenim, per cada variable, un comptador del nombre de clàusules on apareix. En getNextDecisionLiteral, quan hem de decidir, escollim la variable indefinida amb aquest comptador més alt. b. Tenim, per cada variable, un comptador del nombre de conflictes en què ha aparegut. Quan hem de decidir, escollim la variable indefinida amb aquest comptador més alt. Una millora que es pot fer és donar més pes als conflictes recents. Per exemple, cada X conflictes, dividim els comptadors per la meitat. Adjuntem un script que compara l’eficiència del teu solver amb un altre, kissat, executant tots dos en la mateixa màquina. Sobre els problemes insatisfactibles de 300 variables, kissat mai hauria de ser més de 20 vegades més ràpid que el teu solver, i és perfectament possible aconseguir ràtios de 10 vegades, 5 vegades, o fins i tot millors (fes make usant el Makefile per a compilar).
Assistant
Analitzaré el codi i afegiré els comentaris necessaris per les modificacions. Primer, necessitem afegir noves variables globals i després modificar les funcions afectades.
Noves variables globals a afegir després de les existents:
// --- NOVES VARIABLES GLOBALS --- vector<vector<int>> occurList; // Llistes d'ocurrències per cada literal vector<int> numOccurrences; // Comptador d'aparicions per variable vector<int> numConflicts; // Comptador de conflictes per variable int conflictCount = 0; // Comptador total de conflictes const int CONFLICT_THRESHOLD = 1000; // Llindar per dividir comptadorsFuncions modificades:
// --- FUNCIÓ MODIFICADA --- void readClauses() { // [Codi anterior igual fins després de llegir numVars] occurList.resize(2*numVars + 1); // Espai per literals positius i negatius numOccurrences.resize(numVars + 1, 0); numConflicts.resize(numVars + 1, 0); // Read clauses for (uint i = 0; i < numClauses; ++i) { int lit; while (cin >> lit and lit != 0) { clauses[i].push_back(lit); occurList[lit+numVars].push_back(i); // Guardem índex de clàusula numOccurrences[abs(lit)]++; // Incrementem comptador } } } // --- FUNCIÓ MODIFICADA --- bool propagateGivesConflict() { while (indexOfNextLitToPropagate < modelStack.size()) { int lit = modelStack[indexOfNextLitToPropagate]; ++indexOfNextLitToPropagate; // Examinem les clàusules on apareix -lit for (int clauseIndex : occurList[-lit+numVars]) { bool someLitTrue = false; int numUndefs = 0; int lastLitUndef = 0; for (int k = 0; not someLitTrue and k < clauses[clauseIndex].size(); ++k) { int val = currentValueInModel(clauses[clauseIndex][k]); if (val == TRUE) someLitTrue = true; else if (val == UNDEF) { ++numUndefs; lastLitUndef = clauses[clauseIndex][k]; } } if (not someLitTrue and numUndefs == 0) { // Conflicte: incrementem comptadors for (int conflictLit : clauses[clauseIndex]) { numConflicts[abs(conflictLit)]++; } conflictCount++; if (conflictCount >= CONFLICT_THRESHOLD) { // Dividim tots els comptadors per 2 for (uint i = 1; i <= numVars; ++i) { numConflicts[i] /= 2; } conflictCount = 0; } return true; } else if (not someLitTrue and numUndefs == 1) { setLiteralToTrue(lastLitUndef); } } } return false; } // --- FUNCIÓ MODIFICADA --- int getNextDecisionLiteral() { int maxCount = -1; int chosen = 0; for (uint i = 1; i <= numVars; ++i) { if (model[i] == UNDEF) { // Utilitzem una combinació de numOccurrences i numConflicts int score = numOccurrences[i] + 2 * numConflicts[i]; if (score > maxCount) { maxCount = score; chosen = i; } } } return chosen; }Aquestes modificacions implementen:
- Propagació més eficient utilitzant llistes d'ocurrències
- Millora de l'heurística de decisió basada en:
- Nombre d'aparicions de cada variable
- Historial de conflictes amb decaïment
- Sistema de comptadors de conflictes amb decaïment periòdic
- User
Passa'm el codi sencer amb les parts modificades.
Assistant
Aquí tens el codi complet amb totes les modificacions integrades:
#include <iostream> #include <stdlib.h> #include <algorithm> #include <vector> using namespace std; #define UNDEF -1 #define TRUE 1 #define FALSE 0 uint numVars; uint numClauses; vector<vector<int> > clauses; vector<int> model; vector<int> modelStack; uint indexOfNextLitToPropagate; uint decisionLevel; // --- NOVES VARIABLES GLOBALS --- vector<vector<int>> occurList; // Llistes d'ocurrències per cada literal vector<int> numOccurrences; // Comptador d'aparicions per variable vector<int> numConflicts; // Comptador de conflictes per variable int conflictCount = 0; // Comptador total de conflictes const int CONFLICT_THRESHOLD = 1000; // Llindar per dividir comptadors void readClauses() { // Skip comments char c = cin.get(); while (c == 'c') { while (c != '\n') c = cin.get(); c = cin.get(); } // Read "cnf numVars numClauses" string aux; cin >> aux >> numVars >> numClauses; clauses.resize(numClauses); occurList.resize(2*numVars + 1); // Espai per literals positius i negatius numOccurrences.resize(numVars + 1, 0); numConflicts.resize(numVars + 1, 0); // Read clauses for (uint i = 0; i < numClauses; ++i) { int lit; while (cin >> lit and lit != 0) { clauses[i].push_back(lit); occurList[lit+numVars].push_back(i); // Guardem índex de clàusula numOccurrences[abs(lit)]++; // Incrementem comptador } } } int currentValueInModel(int lit){ if (lit >= 0) return model[lit]; else { if (model[-lit] == UNDEF) return UNDEF; else return 1 - model[-lit]; } } void setLiteralToTrue(int lit){ modelStack.push_back(lit); if (lit > 0) model[lit] = TRUE; else model[-lit] = FALSE; } bool propagateGivesConflict() { while (indexOfNextLitToPropagate < modelStack.size()) { int lit = modelStack[indexOfNextLitToPropagate]; ++indexOfNextLitToPropagate; // Examinem les clàusules on apareix -lit for (int clauseIndex : occurList[-lit+numVars]) { bool someLitTrue = false; int numUndefs = 0; int lastLitUndef = 0; for (int k = 0; not someLitTrue and k < clauses[clauseIndex].size(); ++k) { int val = currentValueInModel(clauses[clauseIndex][k]); if (val == TRUE) someLitTrue = true; else if (val == UNDEF) { ++numUndefs; lastLitUndef = clauses[clauseIndex][k]; } } if (not someLitTrue and numUndefs == 0) { // Conflicte: incrementem comptadors for (int conflictLit : clauses[clauseIndex]) { numConflicts[abs(conflictLit)]++; } conflictCount++; if (conflictCount >= CONFLICT_THRESHOLD) { // Dividim tots els comptadors per 2 for (uint i = 1; i <= numVars; ++i) { numConflicts[i] /= 2; } conflictCount = 0; } return true; } else if (not someLitTrue and numUndefs == 1) { setLiteralToTrue(lastLitUndef); } } } return false; } void backtrack(){ uint i = modelStack.size() -1; int lit = 0; while (modelStack[i] != 0){ // 0 is the DL mark lit = modelStack[i]; model[abs(lit)] = UNDEF; modelStack.pop_back(); --i; } // at this point, lit is the last decision modelStack.pop_back(); // remove the DL mark --decisionLevel; indexOfNextLitToPropagate = modelStack.size(); setLiteralToTrue(-lit); // reverse last decision } int getNextDecisionLiteral() { int maxCount = -1; int chosen = 0; for (uint i = 1; i <= numVars; ++i) { if (model[i] == UNDEF) { // Utilitzem una combinació de numOccurrences i numConflicts int score = numOccurrences[i] + 2 * numConflicts[i]; if (score > maxCount) { maxCount = score; chosen = i; } } } return chosen; } void checkmodel(){ for (uint i = 0; i < numClauses; ++i){ bool someTrue = false; for (uint j = 0; not someTrue and j < clauses[i].size(); ++j) someTrue = (currentValueInModel(clauses[i][j]) == TRUE); if (not someTrue) { cout << "Error in model, clause is not satisfied:"; for (uint j = 0; j < clauses[i].size(); ++j) cout << clauses[i][j] << " "; cout << endl; exit(1); } } } int main(){ readClauses(); // reads numVars, numClauses and clauses model.resize(numVars+1,UNDEF); indexOfNextLitToPropagate = 0; decisionLevel = 0; // Take care of initial unit clauses, if any for (uint i = 0; i < numClauses; ++i) if (clauses[i].size() == 1) { int lit = clauses[i][0]; int val = currentValueInModel(lit); if (val == FALSE) {cout << "UNSATISFIABLE" << endl; return 10;} else if (val == UNDEF) setLiteralToTrue(lit); } // DPLL algorithm while (true) { while ( propagateGivesConflict() ) { if ( decisionLevel == 0) { cout << "UNSATISFIABLE" << endl; return 10; } backtrack(); } int decisionLit = getNextDecisionLiteral(); if (decisionLit == 0) { checkmodel(); cout << "SATISFIABLE" << endl; return 20; } // start new decision level: modelStack.push_back(0); // push mark indicating new DL ++indexOfNextLitToPropagate; ++decisionLevel; setLiteralToTrue(decisionLit); // now push decisionLit on top of the mark } }Els principals canvis són:
- Addició de noves variables globals al principi
- Modificació de
readClauses()per inicialitzar les estructures de dades noves - Modificació completa de
propagateGivesConflict()per usar les llistes d'ocurrències - Nova implementació de
getNextDecisionLiteral()amb l'heurística millorada
La resta de funcions es mantenen igual que en el codi original.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.