2-SATisfiabilty 問題のテストケース

Question

2充足可能性問題のSATソルバーを書いたのですが、充足可能な割り当てが1つだけ、つまり解が1つだけある、たとえば10000個のリテラルを含むテストケースを誰か提供してください。

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

テストカバレッジは通常は難しく、ほとんどの場合、何らかの要素を忘れているだけです。

通常、いくつかの手順で作業を進めます。

1. 些細な問題 (またはいくつか) が解決されることを確認してください。
2. エッジケース/境界条件のテスト:たとえば0句
3. テストエラーのケース:不適切な形式の入力、解決策のない問題
4. パフォーマンスのテスト / 大量注入 (プログラムが負荷時にクラッシュしないか、リークがないかなどを確認します...)

2) と 3) はほとんど互換性があり、4) は、この種の情報を調査する方法 (ベンチマーク、メモリ リーク検出など) がある場合にのみ使用する必要があります。

重要な点は、コードをリバース エンジニアリングしてテストを作成しないでください。コードをテストすることになりますが、仕様に従っていることをテストすることはできません。

家庭用プロジェクトの場合、仕様書は通常非公式ですが (頭の中に) 存在しており、その後にテスト ケースを作成する必要があります。

Answer 2

このアプローチの仕事をしていますか？

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

trueの場合にのみsatisifiedすることができます。

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

bがfalseの場合にのみ満足させることができます。したがって

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

完全aとbの値を指定します。私たちは今、リテラル、任意の数のためにこれを拡張することができます。

あなたのアプリをテストするには、あなたも無い溶液で何かそれゆえ、矛盾しrequriementsを指定できます。