2-SATisfiabilty cas de test de problème

Question

J'ai écrit un solveur pour le problème 2 satisfiability, quelqu'un s'il vous plaît me fournir un test avec 10000 dire littéraux qui n'a qu'une seule mission satisfiable i.e. une seule solution

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

couverture de test est généralement difficile, la plupart du temps, vous simplement oublier un facteur ou d'une autre.

Je procède habituellement en quelques étapes:

1. Assurez-vous qu'il résout un problème trivial (ou certains)
2. Edge cas de test / Conditions aux limites: 0 clause par exemple
3. Erreur de cas de test: entrée mal formaté, problèmes sans solution
4. Test Performance / Mass Injection (voir si le programme ne tombe pas en panne en charge, ne fuit pas, ...)

2) et 3) sont à peu près interchangeables, 4) ne devrait venir si vous avez les moyens d'enquêter sur ce genre d'information (benchmarking, détection des fuites de mémoire ...).

Un point important est que vous ne devriez pas désosser votre code pour écrire des tests, parce que vous finirez par tester votre code, mais pas l'essai qu'il obéit aux spécifications.

Si c'est un projet à domicile, les spécifications sont généralement informelles mais ils existent encore (dans votre tête), ce qui est après eux que vous devez produire les cas de test.

Answer 2

Est-ce que ce travail d'approche?

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

Cela ne peut être SATISIFIED si une chose est vraie.

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

Ne peut être satisfaite si b est faux. Par conséquent

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

spécifie complètement les valeurs pour a et b. Nous pouvons maintenant étendre ce pour un certain nombre de littéraux.

Pour tester votre application, vous pouvez aussi préciser requriements contradictoires, donc quelque chose sans solution.