2-Тестовые примеры проблемы удовлетворяемости

Question

Я написал решатель SAT для задачи 2-выполнимости, кто-нибудь, пожалуйста, предоставьте мне тестовый пример, скажем, с 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 равно false.Следовательно

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

Полностью определяет значения для a и b.Теперь мы можем расширить это для любого количества литералов.

Чтобы протестировать свое приложение, вы также можете указать противоречивые требования, следовательно, что-то, не имеющее решения.