casos de teste problema 2-SATisfiabilty

Question

Eu escrevi um solucionador SAT para o problema 2-satisfatibilidade, alguém por favor me fornecer um caso de teste com DIZEM 10000 literais que tem apenas um satisfiable atribuição ou seja apenas uma solução

The format can be:(for 3 literals)
2            // No of clauses and then each clause
2 3
1 -2
corresponding to
(b+c).(a+!b)

Answer 1

A cobertura de teste é geralmente difícil, na maioria das vezes, você simplesmente esquecer um fator ou outro.

Eu normalmente procede em poucos passos:

1. Certifique-se de que ele resolve um problema trivial (ou alguns)
2. casos de teste EDGE / condições de limite: 0 cláusula por exemplo
3. Teste casos de erro: entrada mal formatado, problemas com nenhuma solução
4. Teste de Desempenho / Injeção de massa (ver se o programa não falhar sob carga, não vaza, ...)

2) e 3) são praticamente intercambiáveis, 4) só deve vir, se você tem maneiras de investigar este tipo de informação (avaliação comparativa, a memória vazamento detecção ...).

Um ponto importante é que você não deve fazer a engenharia reversa do código para escrever os testes, porque você iria acabar testar seu código, mas não testar que obedece às especificações.

Se é um projeto de casa, as especificações são geralmente informal, mas eles ainda existem (na sua cabeça) e esta é depois deles que você deve produzir os casos de teste.

Answer 2

Será que esta abordagem trabalho?

 (a + b ).(a + !b) 

Esta só pode ser satisified se a é verdade.

 (a + !b).(!a + !b)

só pode ser satisfeita se b é falsa. Daí

  (a + b ).(a + !b).(a + !b).(!a + !b)

Completamente especifica valores para a e b. Podemos agora estender isso para qualquer número de literais.

Para testar o aplicativo, você também pode especificar requriements contraditórias, portanto, algo sem solução.