Codestil

[StefanUniBonn]

Hier geht es nicht um performance sondern um so Dinge wie lesbarkeit und Anfälligkeit für bugs.

bools solltest du nicht b == 0 verneinen sondern entweder mit not b oder mit !b.

Noch wichtiger: Schreibe nicht b1 & b2 . Das ist ein bitwises und! Verwende b1 and b2 oder b1 && b2.

Ich würde auskommentierten code vermeiden. Seit c++17 gibt es compile time expression, mit denen man das sehr gut Ersetzen kann. Beispiel:

diff --git a/test.cpp b/test.cpp
index eaaccf1..1a37de1 100644
--- a/test.cpp
+++ b/test.cpp
@@ -8,6 +8,8 @@
 #include <algorithm>
 #include "SAT.hpp"

+constexpr bool verbose = false;
+
 SAT backtrackingnaiv(SAT sat, int pos);
 std::vector<int> backtracking(SAT sat);
 void print(std::vector<int> vec);
@@ -31,7 +33,10 @@ std::vector<int> backtracking(SAT sat){                         //setzt für jed
         for (int i = 0; i < var+1; i++){
                 sat.set_belegung(i, 0);
                 bool correct = sat.verify();
-                //std::std::cout << correct << std::endl;
+                if constexpr (verbose)
+                {
+                        std::cout << __FILE__ << ":" << __LINE__ << " " << correct << std::endl;
+                }
                 if(correct == 0){
                         //std::cout << "incorrect" << std::endl;
                         sat.set_belegung(i, 1);

Durch das constexpr wird das ganze if schon zur kompilierzeit weggeworfen. Dann kann man gegebenfalls mehrere outputs an/ausschalten, indem man eine einzelne Variable ändert.

Code dokumentieren ist kein Selbstzweck. Du solltest Code so verständlich wie möglich schreiben. Dafür ist es hilfreich, möglichst passende Namen zu wählen, und falls nötig durch Kommentare zu ergänzen.

        void print();                               //print

wird nie jemanden helfen, der den Code liest. Algemein ist es gut, Namen auszuschreiben. next_improved ist immer noch ein blöder Name, aber hätte mir schon mal deutlich mehr geholfen als nextimp.

Manche Stellen kann man auch einfacher formulieren. z.B. in Clause::verify würde ich die Variable correct einfach weglassen. Du kannst die beiden correct = true einfach jeweils durch return true ersetzen und das return correct am Ende dann durch return false.

[StefanUniBonn]

Ach ja, was ich gerade vergessen hatte: Ich würde empfehlen, else und else if an geeigneten Stellen zu verwenden. Bei

        bool checked = false;
        if (belegung[pos] == 0){
                //std::cout << "b" << std::endl;
                belegung [pos] = 1;
                checked = true;
        }
        if (belegung[pos] == 1 & checked == false){
                //std::cout << "c" << std::endl;
                belegung = next(belegung, pos);
        }

Kann man die Variable checked z.B. komplett weglassen, wenn man das zweite if durch ein else oder ein else if ersetzt (je nachdem, ob du davon ausgehst, dass belegung[pos] sowieso 0 oder 1 ist, oder ob du das nochmal explizit überprüfen möchtest)