O SAT (satisfação booleana) é um problema fundamental na ciência da computação, e seu estudo levou ao desenvolvimento de princípios e técnicas importantes que são amplamente aplicáveis. Aqui está um colapso dos principais princípios:
1. Representando problemas como fórmulas booleanas: *
codificação: A idéia central de usar solucionadores SAT é
codificar Um determinado problema (por exemplo, agendamento, design de circuito, planejamento) em uma fórmula booleana em forma normal conjuntiva (CNF). Isso envolve identificar as variáveis de decisão do problema e representar as restrições nessas variáveis como cláusulas lógicas. A beleza está no fato de que uma grande variedade de problemas pode ser expressa neste formato.
*
forma normal conjuntiva (CNF): Quase todos os solucionadores SAT operam em fórmulas no CNF. O CNF é uma fórmula lógica que é uma conjunção (e) das cláusulas, onde cada cláusula é uma disjunção (ou) de literais. Um literal é uma variável ou sua negação. Por exemplo:`(x ou não y ou z) e (não x ou y)`. Estar no CNF torna o processo de pesquisa mais estruturado e eficiente.
2. Algoritmo de Davis-Putnam-Legemann-Loveland (DPLL): *
Abordagem baseada em pesquisa: O DPLL é o algoritmo fundamental para resolver problemas de SAT. É um algoritmo completo de pesquisa que explora sistematicamente o espaço de possíveis atribuições variáveis.
*
Decisão: O algoritmo escolhe uma variável que atualmente não é atribuída e o atribui `true` ou` false`. Esta escolha cria dois galhos na árvore de busca.
*
Propagação da unidade: Depois de tomar uma decisão, o DPLL realiza a propagação da unidade. Uma cláusula de unidade é uma cláusula que contém apenas um literal não atribuído. Se existir uma cláusula de unidade (por exemplo, `x`), o algoritmo * deve * atribuir a variável` x` ao valor que torna a cláusula verdadeira (neste caso, `x =true`). A propagação da unidade pode cascata, levando a outras atribuições variáveis. Isso é crucial para simplificar o problema e evitar pesquisas desnecessárias.
*
Eliminação literal pura: Um literal puro é um literal que aparece em apenas uma polaridade (positiva ou negativa) em toda a fórmula. Se existir um literal puro, ele pode ser atribuído um valor para tornar todas as cláusulas que o contêm verdadeiro. Isso simplifica a fórmula sem afetar a satisfação.
*
backtracking: Se um ramo da pesquisa levar a um conflito (ou seja, uma cláusula se tornar falsa), o algoritmo *backtracks *. Isso significa desfazer a última decisão e tentar a tarefa oposta. Todo o processo continua até que uma atribuição satisfatória seja encontrada (a fórmula está SAT) ou todas as tarefas possíveis foram esgotadas (a fórmula é insatisfatória).
3. Aprendizagem da cláusula orientada a conflitos (CDCL): *
Aprendendo com conflitos: Os solucionadores SAT modernos são baseados no CDCL, uma extensão do DPLL. A principal inovação é que, quando um conflito é encontrado, o solucionador analisa as razões do conflito e aprende uma nova cláusula (uma cláusula de conflito) que impede que o mesmo conflito ocorra novamente no futuro.
*
Análise de conflito: O processo de análise de conflitos usa o gráfico de implicação (um gráfico que representa as dependências entre atribuições variáveis) para determinar um subconjunto das decisões que levaram ao conflito.
* Aprendizagem da cláusula
: A cláusula de conflito é adicionada à fórmula, normalmente usando o esquema "primeiro ponto de implicação único (UIP)". A cláusula resultante é uma conseqüência lógica da fórmula original, portanto, adicionar não altera a satisfação.
*
backtracking não cronológico (salto de volta): Os solucionadores de CDCL podem voltar de volta não-crronologicamente. Em vez de apenas desfazer a última decisão, eles podem voltar a um nível de decisão anterior responsável pelo conflito. Isso permite que o solucionador explore o espaço de pesquisa com mais eficiência.
* Exclusão da cláusula
: Para impedir que a fórmula cresça demais, solucionadores excluem periodicamente algumas das cláusulas aprendidas. As heurísticas são usadas para decidir quais cláusulas excluirem, equilibrando a necessidade de lembrar informações úteis com a necessidade de manter a fórmula gerenciável.
4. Heurísticas de pedidos variáveis (heurísticas ramificadas): *
Impacto na eficiência: A ordem em que as variáveis são selecionadas para decisão (ramificação) tem um impacto dramático no desempenho dos solucionadores de SAT. Boas heurísticas podem reduzir significativamente o tamanho da árvore de pesquisa.
*
vsids (Estado variável Independent Decaying Sum): Uma heurística popular é vsids. Ele mantém uma pontuação para cada variável, que é incrementada sempre que a variável está envolvida em um conflito. As pontuações são deterioradas periodicamente, dando preferência a variáveis que foram recentemente envolvidas em conflitos. Essa heurística concentra a pesquisa nas partes "ativas" da fórmula.
*
Outras heurísticas: Outras heurísticas consideram a frequência de variáveis em cláusulas, o número de cláusulas não resolvidas contendo uma variável ou usam técnicas de aprendizado de máquina para aprender estratégias de ramificação.
5. Heurísticas de encomenda da cláusula: *
Propagação da unidade orientadora: A ordem em que as cláusulas são consideradas para propagação da unidade também pode afetar o desempenho.
*
Literais assistidos: A maioria dos solucionadores usa uma técnica chamada literais assistidos. Para cada cláusula, dois literais são escolhidos como "assistidos". A propagação da unidade só precisa ser acionada quando um dos literais observados se torna falso. Isso reduz significativamente o número de cláusulas que precisam ser examinadas.
6. Reinicie estratégias: *
escapar dos mínimos locais: Às vezes, os solucionadores de CDCL podem ficar presos em uma parte do espaço de pesquisa difícil de explorar. Reiniciar o solucionador periodicamente pode ajudar a escapar desses mínimos locais.
*
reinicialização baseada em glicose: Os solucionadores modernos geralmente usam estratégias de reinicialização com base na qualidade das cláusulas aprendidas. Por exemplo, a estratégia de reinicialização da glicose reinicia o solucionador com mais frequência quando está aprendendo muitas cláusulas de baixa qualidade.
7. Pré -processamento e inprocessamento: *
Simplificando a fórmula: As técnicas de pré -processamento são aplicadas à fórmula * antes do início do processo de pesquisa principal. Essas técnicas visam simplificar a fórmula removendo cláusulas redundantes, substituindo variáveis e realizando outras transformações lógicas.
*
Inprocessamento: As técnicas de processamento são aplicadas * durante * o processo de pesquisa. Essas técnicas podem simplificar dinamicamente a fórmula com base no estado atual da pesquisa.
*
Exemplos: O pré -processamento e o inprocessamento incluem subsunção (remoção de cláusulas que estão logicamente implícitas por outras cláusulas), resolução (adicionando novas cláusulas à fórmula com base em cláusulas existentes) e eliminação variável (substituindo uma variável por sua definição).
8. Resolução paralela SAT: *
Divida e conquista: Os solucionadores de SAT paralelos exploram o paralelismo inerente ao processo de pesquisa. Eles podem dividir o espaço de pesquisa em várias partes e explorá -las simultaneamente.
*
abordagens do portfólio: Outra abordagem é executar vários solucionadores SAT diferentes (com diferentes configurações de parâmetros) em paralelo e esperar que um deles encontre uma solução rapidamente.
*
Compartilhamento de cláusula: Solvers paralela podem compartilhar cláusulas aprendidas entre diferentes processos para melhorar a eficiência geral da pesquisa.
9. Resolução da teoria (SMT): *
além da lógica booleana: Os solucionadores de SAT são frequentemente usados como um componente central das teorias do módulo de satisfação (SMT). Os solucionadores de SMT podem raciocinar sobre fórmulas que contêm variáveis e restrições de outras teorias, como aritmética, cordas ou matrizes.
*
Combinando SAT com solucionadores específicos da teoria: Os solucionadores de SMT usam uma combinação de técnicas de solução SAT e solucionadores específicos da teoria para determinar a satisfação das fórmulas.
Em resumo, os principais princípios da solução SAT giram em torno de explorar com eficiência o espaço de possíveis atribuições variáveis, aprendendo com conflitos para evitar repetir erros e simplificar a fórmula para reduzir o espaço de pesquisa. Os solucionadores de SAT modernos são ferramentas altamente sofisticadas que podem resolver problemas com milhões de variáveis e cláusulas.
