1. Rappresentare problemi come formule booleane:
* Codifica: L'idea principale di utilizzare i solutori SAT è codifica Un determinato problema (ad es. Pianificazione, progettazione di circuiti, pianificazione) in una formula booleana in forma normale congiuntiva (CNF). Ciò comporta l'identificazione delle variabili di decisione del problema e la rappresentazione dei vincoli su queste variabili come clausole logiche. La bellezza sta nel fatto che una vasta gamma di problemi può essere espressa in questo formato.
* Forma normale congiuntiva (CNF): Quasi tutti i risolutori SAT operano su formule in CNF. Il CNF è una formula logica che è una congiunzione (e) delle clausole, in cui ogni clausola è una disgiunzione (o) dei letterali. Un letterale è una variabile o la sua negazione. Ad esempio:`(x o no y o z) e (non x o y)`. Essere in CNF rende il processo di ricerca più strutturato ed efficiente.
2. Algoritmo Davis-Putnam-Logemann-Loveland (DPLL):
* Approccio basato sulla ricerca: DPLL è l'algoritmo di base per risolvere i problemi SAT. È un algoritmo di ricerca completo che esplora sistematicamente lo spazio di possibili assegnazioni variabili.
* Decisione: L'algoritmo sceglie una variabile attualmente non assegnata e la assegna `vera` o` false`. Questa scelta crea due rami nell'albero di ricerca.
* Propagazione dell'unità: Dopo aver preso una decisione, DPLL esegue una propagazione unitaria. Una clausola unitaria è una clausola che contiene solo un letterale non assegnato. Se esiste una clausola unitaria (ad esempio, `x`), l'algoritmo * deve * assegnare la variabile` x` al valore che rende vera la clausola (in questo caso, `x =true`). La propagazione dell'unità può cascata, portando a ulteriori assegnazioni variabili. Questo è cruciale per semplificare il problema ed evitare ricerche inutili.
* Eliminazione letterale pura: Un letterale puro è un letterale che appare in una sola polarità (positiva o negativa) in tutta la formula. Se esiste un letterale puro, può essere assegnato un valore per rendere tutte le clausole contenenti vere. Ciò semplifica la formula senza influire sulla soddisfazione.
* Backtracking: Se un ramo della ricerca porta a un conflitto (cioè una clausola diventa falsa), l'algoritmo *backtracks *. Ciò significa annullare l'ultima decisione e provare l'incarico opposto. L'intero processo continua fino a quando non viene rilevato un incarico soddisfacente (la formula è SAT) o tutti i possibili incarichi sono stati esauriti (la formula non èt).
3. Clausola guidata dai conflitti Apprendimento (CDCL):
* Imparare dai conflitti: I moderni solutori SAT si basano su CDCL, un'estensione di DPLL. L'innovazione chiave è che quando si verifica un conflitto, il solutore analizza le ragioni del conflitto e apprende una nuova clausola (una clausola di conflitto) che impedisce che lo stesso conflitto si verifichi di nuovo in futuro.
* Analisi dei conflitti: Il processo di analisi dei conflitti utilizza il grafico delle implicazioni (un grafico che rappresenta le dipendenze tra assegnazioni variabili) per determinare un sottoinsieme delle decisioni che hanno portato al conflitto.
* Clausola Apprendimento: La clausola di conflitto viene aggiunta alla formula, in genere utilizzando lo schema "Primo punto di implicazione unica (UIP)". La clausola risultante è una conseguenza logica della formula originale, quindi aggiungendola non cambia la soddisfazione.
* Backtracking non cronologico (backjumping): I solutori CDCL possono fare un backtrack non cronologicamente. Invece di annullare l'ultima decisione, possono tornare a un precedente livello di decisione che era responsabile del conflitto. Ciò consente al risolutore di esplorare lo spazio di ricerca in modo più efficiente.
* Eliminazione della clausola: Per evitare che la formula cresca troppo grande, i risolutori eliminano periodicamente alcune delle clausole apprese. L'euristica viene utilizzata per decidere quali clausole eliminare, bilanciando la necessità di ricordare informazioni utili con la necessità di mantenere la formula gestibile.
4. Euristica dell'ordinamento variabile (euristica ramificata):
* Impatto sull'efficienza: L'ordine in cui le variabili sono selezionate per la decisione (ramificazione) ha un impatto drammatico sulle prestazioni dei risolutori SAT. La buona euristica può ridurre significativamente le dimensioni dell'albero di ricerca.
* VSIDS (somma di decadimento indipendente dello stato variabile): Una popolare euristica è VSID. Mantiene un punteggio per ciascuna variabile, che viene incrementata ogni volta che la variabile è coinvolta in un conflitto. I punteggi sono decomposti periodicamente, dando la preferenza alle variabili che sono state recentemente coinvolte in conflitti. Questa euristica focalizza la ricerca sulle parti "attive" della formula.
* Altre euristiche: Altre euristiche considerano la frequenza delle variabili nelle clausole, il numero di clausole irrisolte contenenti una variabile o usano tecniche di apprendimento automatico per apprendere le strategie di ramificazione.
5. Clausola che ordina euristica:
* Propagazione dell'unità guida: L'ordine in cui le clausole sono considerate per la propagazione unitaria può anche influire sulle prestazioni.
* Osservati letterali: La maggior parte dei solutori utilizza una tecnica chiamata letterali osservate. Per ogni clausola, due letterali vengono scelti come "guardati". La propagazione dell'unità deve essere attivata solo quando uno dei letterali osservati diventa falso. Ciò riduce significativamente il numero di clausole che devono essere esaminate.
6. Strategie di riavvio:
* Fuggire i minimi locali: I solutori CDCL a volte possono rimanere bloccati in una parte dello spazio di ricerca che è difficile da esplorare. Il riavvio periodicamente del solutore può aiutare a sfuggire a questi minimi locali.
* Riavvia a base di glucosio: I risolutori moderni utilizzano spesso strategie di riavvio in base alla qualità delle clausole apprese. Ad esempio, la strategia di riavvio del glucosio riavvia il risolutore più frequentemente quando sta imparando molte clausole di bassa qualità.
7. Preprocessing e invasione:
* Semplificazione della formula: Le tecniche di preelaborazione vengono applicate alla formula * Prima di iniziare * il processo di ricerca principale. Queste tecniche mirano a semplificare la formula rimuovendo le clausole ridondanti, sostituendo le variabili ed eseguendo altre trasformazioni logiche.
* Inprocessing: Le tecniche di invasione vengono applicate * durante * il processo di ricerca. Queste tecniche possono semplificare dinamicamente la formula in base allo stato attuale della ricerca.
* Esempi: La preelaborazione e l'insegnamento includono la sottoposizione (rimuovere le clausole che sono logicamente implicite da altre clausole), la risoluzione (aggiungendo nuove clausole alla formula in base alle clausole esistenti) e l'eliminazione variabile (sostituendo una variabile con la sua definizione).
8. Risoluzione del sabato parallelo:
* Dividi e conquista: I solutori SAT paralleli sfruttano il parallelismo inerente al processo di ricerca. Possono dividere lo spazio di ricerca in più parti ed esplorarli contemporaneamente.
* Approcci al portafoglio: Un altro approccio è quello di eseguire più risolutori SAT diversi (con diverse impostazioni di parametri) in parallelo e sperare che uno di loro troverà rapidamente una soluzione.
* Condivisione della clausola: I solutori paralleli possono condividere clausole apprese tra i diversi processi per migliorare l'efficienza della ricerca complessiva.
9. Teoria Risoluzione (SMT):
* oltre la logica booleana: I solutori SAT vengono spesso utilizzati come componente principale dei risolutori SMT del modulo di soddisfazione (SMT). I solutori SMT possono ragionare su formule che contengono variabili e vincoli da altre teorie, come aritmetica, stringhe o array.
* Combinando SAT con risolutori specifici della teoria: I solutori SMT utilizzano una combinazione di tecniche di risoluzione SAT e solutori specifici della teoria per determinare la soddisfazione delle formule.
In sintesi, i principi chiave della risoluzione SAT ruotano attorno all'esplorazione in modo efficiente dello spazio di possibili incarichi variabili, all'apprendimento dei conflitti per evitare di ripetere gli errori e semplificare la formula per ridurre lo spazio di ricerca. I moderni risolutori SAT sono strumenti altamente sofisticati che possono risolvere i problemi con milioni di variabili e clausole.
sistemi © www.354353.com