2-satisfiabilty 문제 테스트 사례

Question

나는 2-satisbility 문제를 위해 SAT 솔버를 작성했습니다. 누군가 만족스러운 과제가 하나만있는 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) 

이것은 A가 참이면 만족할 수 있습니다.

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

B가 거짓 인 경우에만 만족할 수 있습니다. 따라서

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

A와 b에 대한 값을 완전히 지정합니다. 이제 여러 리터럴에 대해 이것을 확장 할 수 있습니다.

앱을 테스트하기 위해 모순 된 시험을 지정할 수도 있으므로 솔루션이없는 무언가를 지정할 수도 있습니다.