3-SAT Solver Python

Jeśli oprzyrządujesz swój kod jakimś strategicznie rozmieszczonym poleceniami print, zobaczysz, że są wykonywane powtarzające się obliczenia. W drugim przypadku testowym podczas przetwarzania klauzuli X2 v ~X3zestaw {'X1', 'X2'}jest dodawany mySetsdwukrotnie. Podczas przetwarzania klauzuli X3 v ~X1zestaw {'X3', 'X1', 'X2'}jest dodawany mySetstrzykrotnie.

W dużych przypadkach może to przyspieszyć zmianę mySetsna a set()zamiast listy w celu wyeliminowania duplikatów. Wtedy wewnętrzne zestawy muszą być frozensets.

mySetsjest zbiorem możliwych rozwiązań, które spełniają wszystkie klauzule, więc zmieniłem jego nazwę na candidates.

Jeśli zainicjujesz, candidatesaby zawierał pojedynczy pusty zestaw, to pierwsza klauzula nie musi być obsługiwana oddzielnie.

Myślę, że możesz przestać w każdej chwili candidatesjest pusty.

Podziel kod na funkcje.

def is_satisfiable(n_vars, clauses):
    candidates = {frozenset()}

    for clause in clauses:
        temp = set()

        for s in candidates:
            for literal in clause:

                if GetReverse(literal) not in s:

                    temp.add(s | {literal})

        candidates = temp
        
        if len(candidates) == 0:
            return False

    return True
        
        
def load_case(f):
    n_vars, n_clauses = f.readline().split()
    clauses = [f.readline().strip().split(' v ') for _ in range(int(n_clauses))]
    return int(n_vars), clauses
    
    
def main(f=sys.stdin):
    num_cases = int(f.readline())

    for i in range(num_cases):
        n_vars, clauses = load_case(f)
        result = is_satisfiable(n_vars, clauses)
        
        print(f"{'satisfiable' if result else 'unsatisfiable'}")

Nazwany jak:

import io

data = """
2
3 3
X1 v X2
~X1
~X2 v X3
3 5
X1 v X2 v X3
X1 v ~X2
X2 v ~X3
X3 v ~X1
~X1 v ~X2 v ~X3 
""".strip()

main(io.StringIO(data))

lub

import sys

main(sys.stdin)        

Oto sugerowana implementacja, która w zasadzie nie zmienia nic w twoim algorytmie, ale

• ma odpowiednie wcięcie
• używa trochę podpowiedzi typu
• używa zestawów literałów i generatorów
• używa _dla „nieużywanych” zmiennych
• dodaje a, parse_clause()ponieważ kod klauzuli jest powtarzany
• używa StringIOdo tych celów a, aby skutecznie wyszydzać stdini używać przykładowych danych wejściowych, które pokazałeś
• używa nazw zgodnych z PEP8 (z podkreśleniami)

from io import StringIO
from typing import List

stdin = StringIO('''2
3 3
X1 v X2
~X1
~X2 v X3
3 5
X1 v X2 v X3
X1 v ~X2
X2 v ~X3
X3 v ~X1
~X1 v ~X2 v ~X3
'''
)


def get_reverse(literal: str) -> str:
    if literal[0] == '~':
        return literal[1:]
    return '~' + literal


def parse_clause() -> List[str]:
    return stdin.readline().strip().split(' v ')


n_cases = int(stdin.readline())
for _ in range(n_cases):
    n_vars, n_clauses = (int(s) for s in stdin.readline().split())
    my_sets = [{c} for c in parse_clause()]

    for _ in range(n_clauses - 1):
        temp_sets = []
        current_clause = parse_clause()

        for s in my_sets:
            for literal in current_clause:
                if get_reverse(literal) not in s:
                    new_set = s.copy()
                    new_set.add(literal)
                    temp_sets.append(new_set)

        my_sets = temp_sets

    if my_sets:
        print('satisfiable')
    else:
        print('unsatisfiable')